HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

Designing a commutative replicated data type

Abstract : Commuting operations greatly simplify consistency in distributed systems. This paper focuses on designing for commutativity, a topic neglected previously. We show that the replicas of any data type for which concurrent operations commute converges to a correct value, under some simple and standard assumptions. We also show that such a data type supports transactions with very low cost. We identify a number of approaches and techniques to ensure commutativity. We re-use some existing ideas (non-destructive updates coupled with invariant identification), but propose a much more efficient implementation. Furthermore, we propose a new technique, background consensus. We illustrate these ideas with a shared edit buffer data type.
Complete list of metadata

Cited literature [23 references]  Display  Hide  Download

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Wednesday, October 10, 2007 - 9:02:08 AM
Last modification on : Friday, January 21, 2022 - 3:21:31 AM
Long-term archiving on: : Friday, November 25, 2016 - 5:55:42 PM


Files produced by the author(s)


  • HAL Id : inria-00177693, version 2


Marc Shapiro, Nuno Preguiça. Designing a commutative replicated data type. [Research Report] RR-6320, INRIA. 2007. ⟨inria-00177693v2⟩



Record views


Files downloads