Browse wiki

Jump to: navigation, search
Consistency without concurrency control in large, dynamic systems
Abstract Replicas of a commutative replicated data Replicas of a commutative replicated data type {(CRDT)} eventually converge without any complex concurrency control. We validate the design of a non-trivial {CRDT}, a replicated sequence, with performance measurements in the context of Wikipedia. Furthermore, we discuss how to eliminate a remaining scalability bottleneck: Whereas garbage collection previously required a system-wide consensus, here we propose a flexible two-tier architecture and a protocol for migrating between tiers. We also discuss how the {CRDT} concept can be generalised, and its limitations.t can be generalised, and its limitations.
Added by wikilit team Added on initial load  +
Collected data time dimension Cross-sectional  +
Comments They use edit history of three Wikipedia pThey use edit history of three Wikipedia pages in a simulation/experiment on how well their system for mutable shared data works. "Research design": "Design science" and "simulation. "Data source" should perhaps be "simulation results" and "Wikipedia pages" "Collected data time dimension": "longitudinal" as it is the edit history. "longitudinal" as it is the edit history.
Conclusion It is well known that commutativity simpliIt is well known that commutativity simplifies consistency maintenance, as it removes the need for complex concurrency control, allowing updates to execute in arbitrary orders while guaranteeing that replicas converge to the same result. However, the issue of designing shared data types for commutativity was neglected. We presented the Commutative Replicated Data Type or CRDT, designed to make concurrent updates commute. CRDTs enable increased performance and scalability compared to classical approaches. We proposed a CRDT called Treedoc that maintains an ordered set of atoms while providing insert and delete operations. To overcome the challenges of practicality and scalability, we explored some innovative solutions. Each atom has a unique, system-wide, compact identification that does not change between rebalances. Garbage collection is a requirement in practice; it is disruptive and requires consensus, but it has lower precedence that updates, and it is not in the critical path of applications. We side-step the nonscalability of consensus by dividing sites into two tiers with different roles.sites into two tiers with different roles.
Data source Simulation results  + , Wikipedia pages  +
Doi 10.1145/1773912.1773921 +
Google scholar url http://scholar.google.com/scholar?ie=UTF-8&q=%22Consistency%2Bwithout%2Bconcurrency%2Bcontrol%2Bin%2Blarge%2C%2Bdynamic%2Bsystems%22  +
Has author Mihai Letia + , Nuno Preguiça + , Marc Shapiro +
Has domain Computer science +
Has topic Other corpus topics +
Pages 29-34  +
Peer reviewed Yes  +
Publication type Journal article  +
Published in ACM SIGOPS Operating Systems Review +
Research design Design science  + , Simulation  +
Research questions After a brief summary of the CRDT concept After a brief summary of the CRDT concept and of the Treedoc design (Section 2), the contributions of this paper are as follows: • We validate the design with performance measurements of a demanding Wikipedia benchmark (Section 3). • For scalability, we propose a flexible two-tier architecture: A small, stable core supports both updates and consensus. It coexists with a unlimited, uncontrolled, dynamic nebula supporting only updates (Section 4). • We present a novel protocol that allows a nebula site to catch up with the with the core’s past consensuses, in order to send its updates to the core, and possibly to migrate into the core (Section 5).ibly to migrate into the core (Section 5).
Revid 11,122  +
Theories Undetermined
Theory type Design and action  +
Title Consistency without concurrency control in large, dynamic systems
Unit of analysis Article  + , Edit  +
Url http://dx.doi.org/10.1145/1773912.1773921  +
Volume 44  +
Wikipedia coverage Sample data  +
Wikipedia data extraction Live Wikipedia  +
Wikipedia language Not specified  +
Wikipedia page type Article  +
Year 2010  +
Creation dateThis property is a special property in this wiki. 15 March 2012 20:25:37  +
Categories Other corpus topics  + , Computer science  + , Publications  +
Modification dateThis property is a special property in this wiki. 30 January 2014 20:53:35  +
hide properties that link here 
  No properties link to this page.
 

 

Enter the name of the page to start browsing from.