Delta state replicated data types Almeida, Paulo Sérgio; Shoker, Ali; Baquero, Carlos
Journal of parallel and distributed computing,
January 2018, 2018-01-00, Letnik:
111
Journal Article
Recenzirano
Odprti dostop
Conflict-free Replicated Data Types (CRDTs) are distributed data types that make eventual consistency of a distributed object possible and non ad-hoc. Specifically, state-based CRDTs ensure ...convergence through disseminating the entire state, that may be large, and merging it to other replicas. We introduce Delta State Conflict-Free Replicated Data Types (δ-CRDT) that can achieve the best of both operation-based and state-based CRDTs: small messages with an incremental nature, as in operation-based CRDTs, disseminated over unreliable communication channels, as in traditional state-based CRDTs. This is achieved by defining δ-mutators to return a delta-state, typically with a much smaller size than the full state, that to be joined with both local and remote states. We introduce the δ-CRDT framework, and we explain it through establishing a correspondence to current state-based CRDTs. In addition, we present an anti-entropy algorithm for eventual convergence, and another one that ensures causal consistency. Finally, we introduce several δ-CRDT specifications of both well-known replicated datatypes and novel datatypes, including a generic map composition.
•Definition of delta-state CRDTs and their relation to state CRDTs.•Proofs of conditions to attain equivalence to state based CRDTs.•Anti-entropy algorithm for basic and causally consistent convergence.•Portfolio of delta state CRDTs including optimized sets, and recursive map.
With the advancement of distributed computing systems, an increasing number of collaborative systems are developed to support real-life collaborative work. As a typical representative of ...collaborative systems, collaborative editing systems have been one of the major researches within CSCW(Computer Supported Cooperative Work) areas. In collaborative editing systems, selective undo is a key feature that permits users to undo any operation at anywhere and anytime. Recently, with the extensive popularity of big data and cloud computing, collaborative editing systems increasingly tend to massive-scale collaborations, which have to face new technical challenges. How to support selective undo of string-wise operations has become one of significant challenges in future generation collaborative editing systems. Although CRDT (Commutative Replicated Data Type) is a new generation of collaborative editing algorithms, most CRDT algorithms do not support selective undo of string-wise operations. Currently, existing works take time logarithmic or even linear in the number of operation nodes to undo an operation, which would be suboptimal in which a large amount of operations may accumulate. In addition, how to formally prove the correctness of the algorithm is necessary. This paper proposes an efficient CRDT algorithm that supports integrated do and selective undo of string-wise operations. Formal proofs are provided to prove the correctness of the proposed approach and the intentions preserving of do/undo operations. Theoretical analysis and experimental evaluation show that our algorithm outperforms the existing CRDT algorithms to support selective undo.
While the intersection of blockchains and the Internet of Things (IoT) have received considerable research interest lately, Nakamoto-style blockchains possess a number of qualities that make them ...poorly suited for many IoT scenarios. Specifically, they require high network connectivity and are power-intensive. This is a drawback in IoT environments where battery-constrained nodes form an unreliable ad hoc network such as in digital agriculture. In this paper we present Vegvisir, a partition-tolerant blockchain for use in power-constrained IoT environments with limited network connectivity. It is a permissioned, directed acyclic graph (DAG)-structured blockchain that can be used to create a shared, tamperproof data repository that keeps track of data provenance. We discuss the use cases, architecture, and challenges of such a blockchain.
In collaborative editing systems, selective undo is a fundamental function that allows dispersed users to undo any executed operation in the history. Most selective undo mechanisms have been applied ...in collaborative editing systems with simple objects (plain text or image). However, how to provide a selective undo mechanism for collaborative editing systems with complex objects (feature-based CAD model) has been a technical challenge. This paper proposes a novel CRDT (Conflict-free Replicated Data Type)-based selective undo mechanism for feature-based Co-CAD (Collaborative CAD) systems. Firstly, a selective undo framework is presented to integrate (do/undo) operations. Secondly, three constraint relations of (do/undo) operations are defined and feature-based conflict detection conditions are proposed to detect the three constraint relations. Thirdly, a CRDT-based conflict resolution approach is proposed to integrate (do/undo) operations. Fourthly, collaborative case studies illustrate how the selective undo mechanism works and achieves consistent results. Finally, the complexities in theory are analyzed and the formal proofs are provided to verify the correctness.
•A novel CRDT-based approach is proposed to integrate do/undo Co-CAD modeling operations.•Three constraint relations of (do/undo) operations and feature-based conflict detection conditions.•A conflict resolution approach is presented to resolve the conflicts of concurrent modeling operations.•Case studies of collaborative modeling procedures verify the correctness and feasibility of the method.
Fibromyalgia is a syndrome characterized by chronic generalized pain in addition to different symptoms such as fatigue, sleep disturbances, stiffness, cognitive impairment, and psychological ...distress. Multidisciplinary treatment combining pharmacological and nonpharmacological therapies is advised.
Publications describing randomized controlled trials and long-term extension studies evaluating drug treatment for fibromyalgia were searched in PubMed and Scopus and included in this review.
Different drugs are recommended for the treatment of fibromyalgia by different published guidelines, although only three of them have been approved for this indication by the US FDA, and none have been approved by the European Medicines Agency. According to the available evidence, pregabalin, duloxetine and milnacipran should be the drugs of choice for the treatment of this disease, followed by amitriptyline and cyclobenzaprine. Other drugs with at least one positive clinical trial include some selective serotonin reuptake inhibitors, moclobemide, pirlindole, gabapentin, tramadol, tropisetron, sodium oxybate and nabilone. None of the currently available drugs are fully effective against the whole spectrum of fibromyalgia symptoms, namely pain, fatigue, sleep disturbances and depression, among the most relevant symptoms. Combination therapy is an option that needs to be more thoroughly investigated in clinical trials.
Operation-based Conflict-free Replicated Data Types (op-based CRDTs) are a family of distributed data structures where all operations are designed to commute, so that replica states eventually ...converge. Additionally, op-based CRDTs require that operations be propagated between replicas in causal order. This paper presents a framework for verifying safety properties of CRDT implementations using separation logic. The framework consists of two libraries. One implements a Reliable Causal Broadcast (RCB) protocol so that replicas can exchange messages in causal order. A second “OpLib” library then uses RCB to simplify the creation and correctness proofs of op-based CRDTs. OpLib allows clients to implement new CRDTs as purely-functional data structures, without having to reason about network operations, concurrency control and mutable state, and without having to each time re-implement causal broadcast. Using OpLib, we have implemented 12 example CRDTs from the literature, including multiple versions of replicated registers and sets, two CRDT combinators for products and maps, and two example use cases of the map combinator. Our proofs are conducted in the Aneris distributed separation logic and are formalized in Coq. Our technique is the first work on verification of op-based CRDTs that satisfies both of the following properties: it is
modular
and targets executable
implementations
, as opposed to high-level protocols.
Collaboration plays a key role in distributed applications. As a fundamental vehicle for collaboration, collaborative text editing systems have been an important field within CSCW. More recently, ...with the increasing popularity of cloud computing, collaborative text editing systems move towards large-scale collaborations based on the cloud computing/cloud platform. The computing performance is the key factor of success for large-scale collaborations. CRDT algorithms have been proved to outperform traditional algorithms in publications. However, how to support selective undo has been a challenging issue for existing CRDT algorithms. This paper proposes an efficient CRDT algorithm called ORGAU that provides integrated do and selective undo efficiently. The correctness and operation intentions preserving of the proposed algorithm under an integrated do/undo framework are formally proved. Compared with the typical CRDT algorithms, the proposed algorithm has better computing performance both in theoretical analysis and experimental evaluation while keeping the same space complexity.
•An efficient algorithm called ORGAU with integrated support of do and selective undo.•It has a time complexity lower than typical CRDT algorithms while keeping the same space complexity.•The experiment evaluations show that the proposed algorithm has better computing performance.•Both the correctness and the intention preserving of the proposed algorithm have been formally proved.
•A novel CRDT-based method to maintain eventual consistency for real-time collaborative CAD systems.•A conflict detection mechanism is presented to detect relations of feature-based CAD ...operations.•To ensure the consistency of shared CAD model and preserve the intentions of collaborative designers.•Case studies of collaborative modeling procedures verify the proposed method.
CRDT (Conflict-free Replicated Data Type) has been proposed as an alternative synchronization mechanism for collaborative text editing systems in recent years. However, CRDT-based synchronization methods for collaborative systems with sophisticated objects, such as collaborative CAD (Co-CAD) systems, are rarely investigated in previous literatures. How well CRDT-based synchronization methods for Co-CAD systems could perform remains unknown. This paper presents a novel CRDT-based synchronization method to maintain eventual consistency for the feature-based CAD model. Firstly, three operation relations are defined as the dependency-conflict relation, the mutual exclusive relation and the compatible relation in context of the feature-based CAD systems. Secondly, a feature-based conflict detection mechanism is proposed to detect the three relations. Thirdly, a feature-based conflict resolution approach under the CRDT framework is presented to solve the conflicts. Fourthly, the time complexity and the space complexity are analyzed in theory. Finally, case studies of collaborative modeling procedures verify the correctness and feasibility of the proposed method.
Distributed storage systems employ replication to improve performance and reliability. To provide low latency data access, replicas are often required to accept updates without coordination with each ...other, and the updates are then propagated asynchronously. This brings the critical challenge of conflict resolution among concurrent updates. Conflict-free Replicated Data Type (CRDT) is a principled approach to addressing this challenge. However, existing CRDT designs are tricky, and hard to be generalized to other data types. A design framework is in great need to guide the systematic design of new CRDTs. To address this challenge, we propose RWF - the Remove-Win design Framewerk for CRDTs. RWF leverages the simple but powerful remove-win strategy to resolve conflicting updates, and provides generic design for a variety of data container types. Two exemplar implementations following RWF are given over the Redis data type store, which demonstrate the effectiveness of RWF. Performance measurements of our implementations further show the efficiency of CRDT designs following RWF.
Commutative Replicated Data Types (CRDTs) are a promising new class of data structures for large-scale shared mutable content in applications that only require eventual consistency. The WithOut ...Operational Transforms (WOOT) framework is the first CRDT for collaborative text editing introduced by Oster et al. (In: Conference on Computer Supported Cooperative Work (CSCW). ACM, New York, pp 259–268, 2006a). Its eventual consistency property was verified only for a bounded model to date. While the consistency of many other previously published CRDTs had been shown immediately with their publication, the property for WOOT remained open for 14 years. We use a novel approach identifying a previously unknown sort-key based protocol that simulates the WOOT framework to show its consistency. We formalize the proof using the Isabelle/HOL proof assistant to machine-check its correctness.
PDF
