The weakest failure detector for eventual consistency - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Distributed Computing Année : 2019

The weakest failure detector for eventual consistency

Résumé

In its classical form, a consistent replicated service requires all replicas to witness the same evolution of the service state. If we consider an asynchronous message-passing environment in which processes might fail by crashing, and assume that a majority of processes are correct, then the necessary and sufficient information about failures for implementing a general state machine replication scheme ensuring consistency is captured by the Ω failure detector. This paper shows that in such a message-passing environment, Ω is also the weakest failure detector to implement an eventually consistent replicated service, where replicas are expected to agree on the evolution of the service state only after some (a priori unknown) time. In fact, we show that Ω is the weakest to implement eventual consistency in any message-passing environment, i.e., under any assumption on when and where failures might occur. Ensuring (strong) consistency in any environment requires, in addition to Ω, the quorum failure detector Σ. Our paper thus captures, for the first time, an exact computational difference between building a replicated state machine that ensures consistency and one that only ensures eventual consistency.

Dates et versions

hal-02413314 , version 1 (16-12-2019)

Identifiants

Citer

Swan Dubois, Rachid Guerraoui, Petr Kuznetsov, Franck Petit, Pierre Sens. The weakest failure detector for eventual consistency. Distributed Computing, 2019, 32 (6), pp.479-492. ⟨10.1007/s00446-016-0292-9⟩. ⟨hal-02413314⟩
108 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More