sign in
english version rss feed

inria-00177693, version 2

Designing a commutative replicated data type

Marc Shapiro () a1, Nuno Preguiça () b2

N° RR-6320 (2007)

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.

  • Domain : Computer Science/Computation and Language
    Computer Science/Distributed, Parallel, and Cluster Computing
    Computer Science/Data Structures and Algorithms
  • Keywords : Data replication – optimistic replication – commutative operations
  • Internal note : RR-6320
  • Available versions :  v1 (2007-10-09) v2 (2007-10-10)
 
  • inria-00177693, version 2
  • oai:hal.inria.fr:inria-00177693
  • From: 
  • Submitted on: Wednesday, 10 October 2007 09:02:08
  • Updated on: Wednesday, 10 October 2007 09:02:31
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...