ZAWIRSKI Marek
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.
Defence : 01/14/2015
Jury members :
M. Pascal MOLLI, Université de Nantes [Rapporteur]
M. Luis RODRIGUES, INESC-ID Université de Lisbonne [Rapporteur]
M. Carlos Baquero, HASLab, INESC TEC & University of Minho
M. Jerzy Brzeziński, Poznań University of Technology
M. Sebastian Burckhardt, Microsoft Research, Redmond
M. Peter Dickman, Google, Zürich
M. Pierre Sens, LIP6
M. Marc Shapiro, LIP6 [Directeur de thèse]
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: 41st 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 - 26th 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 - 1st 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 - 13th 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)