%0 Conference Proceedings
%T Monotonic Prefix Consistency in Distributed Systems
%+ Sound Programming of Adaptive Dependable Embedded Systems (SPADES)
%+ Distributed Programming Laboratory (LPD)
%+ Lab for Automated Reasoning and Analysis (LARA)
%+ Inria-EPFL (Inria-EPFL)
%+ Ecole Polytechnique Fédérale de Lausanne (EPFL)
%A Girault, Alain
%A Gössler, Gregor
%A Guerraoui, Rachid
%A Hamza, Jad
%A Seredinschi, Dragos-Adrian
%< avec comité de lecture
%( Lecture Notes in Computer Science
%B FORTE 2018 - 38th International Conference on Formal Techniques for Distributed Objects, Components, and Systems
%C Madrid, Spain
%Y Christel Baier
%Y Luís Caires
%I Springer International Publishing
%3 Formal Techniques for Distributed Objects, Components, and Systems
%V LNCS-10854
%P 41-57
%8 2018-06-18
%D 2018
%R 10.1007/978-3-319-92612-4_3
%Z Computer Science [cs]
%Z Computer Science [cs]/Networking and Internet Architecture [cs.NI]Conference papers
%X We study the issue of data consistency in distributed systems. Specifically, we consider a distributed system that replicates its data at multiple sites, which is prone to partitions, and which is assumed to be available (in the sense that queries are always eventually answered). In such a setting, strong consistency, where all replicas of the system apply synchronously every operation, is not possible to implement. However, many weaker consistency criteria that allow a greater number of behaviors than strong consistency, are implementable in available distributed systems.We focus on determining the strongest consistency criterion that can be implemented in a convergent and available distributed system that tolerates partitions. We focus on objects where the set of operations can be split into updates and queries. We show that no criterion stronger than Monotonic Prefix Consistency (MPC) can be implemented.
%G English
%Z TC 6
%Z WG 6.1
%2 https://inria.hal.science/hal-01824817/document
%2 https://inria.hal.science/hal-01824817/file/469043_1_En_3_Chapter.pdf
%L hal-01824817
%U https://inria.hal.science/hal-01824817
%~ UNIV-RENNES1
%~ UGA
%~ CNRS
%~ INRIA
%~ INPG
%~ INRIA-RHA
%~ IRISA
%~ LIG
%~ INRIA_TEST
%~ TESTALAIN1
%~ IFIP-LNCS
%~ IFIP
%~ INRIA2
%~ IFIP-TC
%~ INRIA-EPFL
%~ IFIP-WG
%~ IFIP-TC6
%~ IFIP-WG6-1
%~ UR1-HAL
%~ LIG-MFML-SPADES
%~ UR1-MATH-STIC
%~ IFIP-FORTE
%~ UR1-UFR-ISTIC
%~ IFIP-DISCOTEC
%~ TEST-UR-CSS
%~ UNIV-RENNES
%~ INRIA-RENGRE
%~ INRIA-300009
%~ IFIP-LNCS-10854
%~ UGA-COMUE
%~ UR1-MATH-NUM
%~ LIG_SIDCH