Principled approaches to eventual consistency

Data replication is a fundamental mechanism of distributed systems, for performance, availability and fault tolerance. To sidestep the incompatibility between strong consistency and fault-tolerance, an attractive approach is eventual consistency (EC). EC allows a replica to update without synchronising; concurrent updates are reconciled in the background. However, existing EC algorithms are often ad-hoc and/or unpredictable; conflict resolution requires synchronisation and is complex and error-prone.

A recent insight is that it is possible to design non-trivial and generally useful data types whose concurrent operations commute. These Commutative Replicative Data Types (CRDTs) ensure EC in a simple and sound way, with no synchronisation and no roll-backs. Our challenges so far have been to design a library of useful and interesting CRDTs, and to characterise sufficient conditions for consistency. Many research questions remain open: how do we build interesting, large-scale applications using CRDTs? Is the CRDT approach sufficient, or is some synchronisation always necessary; and if so, how much, and how do we fit the two together? What are the theoretical and practical limits of CRDTs? What complexity bounds and real performance? How do CRDTs relate to commutativity theory, monotonic languages, self-stabilisation, or the consensus hierarchy? How to ensure security and confidentiality while at the same time sharing state?

To apply

We wish to recruit a post-doc interested in pursuing this topic. Candidates should have an excellent academic record. Candidates must have a strong interest in distributed systems. We are especially interested in candidates with a dual expertise in a complementary area, e.g., programming languages, verification, or security.

Please provide a CV, the list of Masters or PhD courses and your marks, an essay relevant to the topic (1 to 4 pages), and at least two references (whom we will contact ourselves for a recommendation). Contacts:

Bibliography

More papers available here.

  • Conflict-free Replicated Data Types. Shapiro, Preguiça, Baquero, Zawirski. Int. Symp. on Stabilization, Safety, and Security of Distributed Systems (SSS), 2011. [ PDF ]
  • Convergent and Commutative Replicated Data Types. Shapiro, Preguiça, Baquero, Zawirski. Bulletin of the European Association for Theoretical Computer Science (EATCS), Number 104, June 2011. [ PDF ]

  • A commutative replicated data type for cooperative editing. Preguiça, Marquès, Shapiro, Leția. Int. Conf. on Distributed Computing Systems (ICDCS), 2009. [ PDF ]
  • Optimistic Replication. Saito, Shapiro. Computing Surveys, vol. 37, n° 1, 2005. [ PDF ]

This research is funded by ANR Project ConcoRDanT.