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 metadatas

Cited literature [23 references]  Display  Hide  Download

https://hal.inria.fr/inria-00177693
Contributor : Rapport de Recherche Inria <>
Submitted on : Wednesday, October 10, 2007 - 9:02:08 AM
Last modification on : Thursday, March 21, 2019 - 2:32:35 PM
Long-term archiving on : Friday, November 25, 2016 - 5:55:42 PM

File

RR-6320.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00177693, version 2

Citation

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

Share

Metrics

Record views

597

Files downloads

1442