Consistency without concurrency control in large, dynamic systems

From WikiLit
Jump to: navigation, search
Publication (help)
Consistency without concurrency control in large, dynamic systems
Authors: Mihai Letia, Nuno Preguiça, Marc Shapiro [edit item]
Citation: ACM SIGOPS Operating Systems Review 44 : 29-34. 2010.
Publication type: Journal article
Peer-reviewed: Yes
DOI: 10.1145/1773912.1773921.
Google Scholar cites: Citations
Link(s): Paper link
Added by Wikilit team: Added on initial load
Article: Google Scholar BASE PubMed
Other scholarly wikis: AcaWiki Brede Wiki WikiPapers
Web search: Bing Google Yahoo!Google PDF
Format: BibTeX
Consistency without concurrency control in large, dynamic systems is a publication by Mihai Letia, Nuno Preguiça, Marc Shapiro.

[edit] Abstract

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.

[edit] Research questions

"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)."

Research details

Topics: Other corpus topics [edit item]
Domains: Computer science [edit item]
Theory type: Design and action [edit item]
Wikipedia coverage: Sample data [edit item]
Theories: "Undetermined" [edit item]
Research design: Design science, Simulation [edit item]
Data source: Simulation results, Wikipedia pages [edit item]
Collected data time dimension: Cross-sectional [edit item]
Unit of analysis: Article, Edit [edit item]
Wikipedia data extraction: Live Wikipedia [edit item]
Wikipedia page type: Article [edit item]
Wikipedia language: Not specified [edit item]

[edit] Conclusion

"It 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."

[edit] Comments

"They 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."

Further notes[edit]