Composing and decomposing op-based CRDTs with semidirect products
Operation-based Conflict-free Replicated Data Types (CRDTs) are eventually consistent replicated data types that automatically resolve conflicts between concurrent operations. Op-based CRDTs must be designed differently for each data type, and current designs use ad-hoc techniques to handle concurrent operations that do not naturally commute. We present a new construction, the semidirect product of op-based CRDTs, which combines the operations of two CRDTs into one while handling conflicts between their concurrent operations in a uniform way. We demonstrate the construction’s utility by using it to construct novel CRDTs, as well as decomposing several existing CRDTs as semidirect products of simpler CRDTs. Although it reproduces common CRDT semantics, the semidirect product can be viewed as a restricted kind of operational transformation, thus forming a bridge between these two opposing techniques for constructing replicated data types.
Thu 8 DecDisplayed time zone: Auckland, Wellington change
10:30 - 12:00 | ICFP and SASCOVID Time Papers In Person at Seminar Room LG004 Chair(s): Peter Thiemann University of Freiburg, Germany | ||
10:30 30mTalk | Composing and decomposing op-based CRDTs with semidirect products COVID Time Papers In Person Matthew Weidner Carnegie Mellon University, Heather Miller Carnegie Mellon University, USA, Christopher Meiklejohn Carnegie Mellon University Link to publication DOI | ||
11:00 30mTalk | Improving Thread-Modular Abstract Interpretation COVID Time Papers In Person Michael Schwarz Technische Universität München, Simmo Saan University of Tartu, Estonia, Helmut Seidl Technische Universität München, Kalmer Apinis University of Tartu, Estonia, Julian Erhard Technical University of Munich, Vesal Vojdani University of Tartu Link to publication DOI | ||
11:30 30mTalk | Static Analysis of Endian Portability by Abstract InterpretationVirtual COVID Time Papers In Person David Delmas Airbus & Sorbonne Université, Abdelraouf Ouadjaout Sorbonne Université, Antoine Miné Sorbonne Université Link to publication DOI |