Supervision : Marc SHAPIRO

Dependable Eventual Consistency with Replicated Data Types

Eventually consistent replicated databases offer excellent responsiveness and fault-tolerance, but expose applications to the complexity of concurrency and failures. Recent databases encapsulate these problems behind a stronger interface, supporting causal consistency, which protects the application from ordering anomalies, and/or Replicated Data Types (RDTs), which ensure convergent semantics of concurrent updates using object interface. However, dependable algorithms for RDT and causal consistency come at a cost in metadata size. This thesis studies the design of such algorithms with minimized metadata, and the limits of the design space.
Our first contribution is a study of metadata complexity of RDTs. RDTs use metadata to provide rich semantics; many existing RDT implementations incur high overhead in storage space. We design optimized set and register RDTs with metadata overhead reduced to the number of replicas. We also demonstrate metadata lower bounds for six RDTs, thereby proving optimality of four implementations.
Our second contribution is the design of SwiftCloud, a replicated causally-consistent RDT object database for client-side applications. We devise algorithms to support high numbers of client-side partial replicas backed by the cloud, in a fault-tolerant manner, with small metadata. We demonstrate how to support availability and consistency, at the expense of some slight data staleness; i.e., our approach trades freshness for scalability (small metadata, parallelism), and availability (ability to fail-over between data centers). We validate our approach with experiments involving thousands of client replicas.

2011-2016 Publications

• 2016
  • H. Attiya, S. Burckhardt, A. Gotsman, A. Morrison, H. Yang, M. Zawirski : “Specification and Complexity of Collaborative Text Editing”, Int. Symp. on Principles of Distributed Computing (PODC) 2016, vol. PODC 2016, Int. Symp. on Principles of Distributed Computing (PODC) 2016, Chicago, IL, United States, pp. 10 (2016)
  • M. Zawirski, C. Baquero, A. Bieniusa, N. Preguiça, M. Shapiro : “Eventually Consistent Register Revisited”, Int. W. on Principles and Practice of Consistency for Distributed Data (PaPoC), vol. PaPoC 2016, Int. W. on Principles and Practice of Consistency for Distributed Data (PaPoC), London, United Kingdom, pp. 7 (2016)
• 2015
  • M. Zawirski : “Dependable Eventual Consistency with Replicated Data Types”, thesis, defence 01/14/2015, supervision Shapiro, Marc (2015)
  • M. Zawirski, N. Preguiça, S. Duarte, A. Bieniusa, V. Balegas, M. Shapiro : “Write Fast, Read in the Past: Causal Consistency for Client-side Applications”, Middleware 2015, Vancouver, BC, Canada, pp. 75-87, (ACM) (2015)
  • M. Zawirski, N. Preguiça, S. Duarte, A. Bieniusa, V. Balegas, M. Shapiro : “Write Fast, Read in the Past: Causal Consistency for Client-side Applications”, (2015)
• 2014
  • S. Burckhardt, A. Gotsman, H. Yang, M. Zawirski : “Replicated Data Types: Specification, Verification, Optimality”, POPL 2014: 41^st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, San Diego, CA, United States, pp. 271-284, (ACM) (2014)
• 2013
  • M. Zawirski, A. Bieniusa, V. Balegas, S. Duarte, C. Baquero, M. Shapiro, N. Preguiça : “SwiftCloud: Fault-Tolerant Geo-Replication Integrated all the Way to the Client Machine”, (2013)
• 2012
  • A. Bieniusa, M. Zawirski, N. Preguiça, M. Shapiro, C. Baquero, V. Balegas, S. Duarte : “An optimized conflict-free replicated set”, 12 pages (2012)
  • A. Bieniusa, M. Zawirski, N. Preguiça, M. Shapiro, C. Baquero, V. Balegas, S. Duarte : “Brief Announcement: Semantics of Eventually Consistent Replicated Sets”, DISC 2012 - 26^th International Symposium on Distributed Computing, vol. 7611, Lecture Notes in Computer Science, Salvador, Bahia, Brazil, pp. 441-442, (Springer) (2012)
  • M. Saeida Ardekani, M. Zawirski, P. Sutra, M. Shapiro : “The Space Complexity of Transactional Interactive Reads”, HotCDP '12 - 1^st International Workshop on Hot Topics in Cloud Data Processing, Bern, Switzerland, (ACM) (2012)
• 2011
  • M. Shapiro, N. Preguiça, C. Baquero, M. Zawirski : “Conflict-free Replicated Data Types”, SSS 2011 - 13^th International Symposium Stabilization, Safety, and Security of Distributed Systems, vol. 6976, Lecture Notes in Computer Science, Grenoble, France, pp. 386-400, (Springer) (2011)
  • M. Shapiro, N. Preguiça, C. Baquero, M. Zawirski : “Conflict-free Replicated Data Types”, 18 pages (2011)
  • M. Shapiro, N. Preguiça, C. Baquero, M. Zawirski : “Convergent and Commutative Replicated Data Types”, Bulletin- European Association for Theoretical Computer Science n°104, pp. 67-88, (European Association for Theoretical Computer Science; 1999) (2011)
  • M. Shapiro, N. Preguiça, C. Baquero, M. Zawirski : “A comprehensive study of Convergent and Commutative Replicated Data Types”, 50 pages (2011)
  • M. Zawirski, M. Shapiro, N. Preguiça : “Asynchronous rebalancing of a replicated tree”, Conférence Française en Systèmes d'Exploitation (CFSE), Saint-Malo, France, pp. 12 (2011)
  • N. Preguiça, M. Shapiro, M. Zawirski : “Position paper: CRDTs for large-scale incremental processing”, (2011)