• Eventually Consistent Register...

Result: Eventually Consistent Register Revisited

Title:
Eventually Consistent Register Revisited
Authors:
Zawirski, Marek, Baquero, Carlos, Bieniusa, Annette, Preguiça, Nuno, Shapiro, Marc
Contributors:
Large-Scale Distributed Systems and Applications (Regal), Laboratoire d'Informatique de Paris 6 (LIP6), Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Departamento de Informática [Minho] (Universidade do Minho Departamento de Informática), Universidade do Minho = University of Minho [Braga], Kaiserslautern University of Technology, NOVA Laboratory for Computer Science and Informatics (NOVA-LINCS), Departamento de Informática (DI), Faculdade de Ciências e Tecnologia = School of Science & Technology (FCT NOVA), Universidade Nova de Lisboa = NOVA University Lisbon (NOVA)-Universidade Nova de Lisboa = NOVA University Lisbon (NOVA)-Faculdade de Ciências e Tecnologia = School of Science & Technology (FCT NOVA), Universidade Nova de Lisboa = NOVA University Lisbon (NOVA)-Universidade Nova de Lisboa = NOVA University Lisbon (NOVA), Google Research Award, ACM Sigops / EuroSys, ACM, European Project: 609551,EC:FP7:ICT,FP7-ICT-2013-10,SYNCFREE(2013)
Source:
Int. W. on Principles and Practice of Consistency for Distributed Data (PaPoC). :7-7
Publisher Information:
CCSD, 2016.
Publication Year:
2016
Collection:
collection:UPMC
collection:CNRS
collection:INRIA
collection:INRIA-ROCQ
collection:INRIA_TEST
collection:TESTALAIN1
collection:LIP6
collection:INRIA2
collection:UPMC_POLE_1
collection:SORBONNE-UNIVERSITE
collection:SU-SCIENCES
collection:SU-TI
collection:ALLIANCE-SU
collection:INRIA-ALLEMAGNE
Subject Terms:
CRDTs, eventual consistency, replicated data types, ACM: C.: Computer Systems Organization, C.2: COMPUTER-COMMUNICATION NETWORKS, C.2.4: Distributed Systems, ACM: F.: Theory of Computation, F.1: COMPUTATION BY ABSTRACT DEVICES, F.1.2: Modes of Computation, F.1.2.3: Parallelism and concurrency, ACM: I.: Computing Methodologies, I.1: SYMBOLIC AND ALGEBRAIC MANIPULATION, I.1.2: Algorithms, [INFO.INFO-OH]Computer Science [cs], Other [cs.OH]
Subject Geographic:
London, United Kingdom
Original Identifier:
HAL: hal-01242700
Document Type:
Conference conferenceObject<br />Conference papers
Language:
English
Relation:
info:eu-repo/semantics/altIdentifier/doi/10.1145/2911151.2911157; info:eu-repo/grantAgreement/EC/FP7/609551/EU/Large-scale computation without synchronisation/SYNCFREE
DOI:
10.1145/2911151.2911157
Access URL:
https://inria.hal.science/hal-01242700
https://inria.hal.science/hal-01242700v1/document
https://inria.hal.science/hal-01242700v1/file/mvreg_arXiv.pdf
https://inria.hal.science/hal-01242700v1/file/bug-run%20%281%29.pdf
https://inria.hal.science/hal-01242700v1/file/bug-run.pdf
https://inria.hal.science/hal-01242700v1/file/lww-run.pdf
https://inria.hal.science/hal-01242700v1/file/lww-run2%20%281%29.pdf
https://inria.hal.science/hal-01242700v1/file/lww-run2.pdf
Rights:
info:eu-repo/semantics/OpenAccess
URL: http://hal.archives-ouvertes.fr/licences/copyright/
Accession Number:
edshal.hal.01242700v1
Database:
HAL

Further Information

In order to converge in the presence of concurrent updates, modern eventually consistent replication systems rely on causality information and operation semantics. It is relatively easy to use semantics of high-level operations on replicated data structures, such as sets, lists, etc. However, it is difficult to exploit semantics of operations on registers, which store opaque data. In existing register designs, concurrent writes are resolved either by the application, or by arbitrating them according to their timestamps. The former is complex and may require user intervention, whereas the latter causes arbitrary updates to be lost. In this work, we identify a register construction that generalizes existing ones by combining runtime causality ordering, to identify concurrent writes, with static data semantics, to resolve them. We propose a simple conflict resolution template based on an application-predefined order on the domain of values. It eliminates or reduces the number of conflicts that need to be resolved by the user or by an explicit application logic. We illustrate some variants of our approach with use cases, and how it generalizes existing designs.