HAL - INRIA :: [inria-00177693, version 2] Designing a commutative replicated data type

inria-00177693, version 2

See detailed view

BibTeX EndNote TEI RefWorks

Designing a commutative replicated data type

Marc Shapiro (

)^a^, 1, Nuno Preguiça (

)^b^, 2

(2007)

Access to full text
PDF

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.

a –	INRIA
b –	FCT - Universidade Nova de Lisboa, Portugal
1:	REGAL (INRIA Rocquencourt)
	INRIA – CNRS : UMR7606 – Université Pierre et Marie Curie - Paris VI
2:	Centro de Investigação em Informática e Tecnologias da Informação (CITI)
	Universidade Nova de Lisboa

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
http://hal.inria.fr/inria-00177693/en/
oai:hal.inria.fr:inria-00177693_v2
From: Rapport De Recherche Inria <>
Submitted on: Wednesday, 10 October 2007 09:02:08
Updated on: Wednesday, 10 October 2007 09:02:31