Fast Genuine Generalized Consensus

Pierre Sutra 1, 2 Marc Shapiro 1, 2
1 Regal - Large-Scale Distributed Systems and Applications
LIP6 - Laboratoire d'Informatique de Paris 6, Inria Paris-Rocquencourt
Abstract : Consensus (agreeing on a sequence of commands) is central to the operation and performance of distributed systems. A well-known solution to consensus is Fast Paxos. In a recent paper, Lamport enhances Fast Paxos by leveraging the commutativity of concurrent commands. The new primitive, called Generalized Paxos, reduces the collision rate, and thus the latency of Fast Paxos. However if a collision occurs, Generalized Paxos needs four communication steps to recover, which is slower than Fast Paxos. This paper presents FGGC, a novel consensus algorithm that reduces recovery delay when a collision occurs to one. FGGC tolerates f < n/2 replicas crashes, and during failure-free runs, processes learn commands in two steps if all commands commute, and three steps otherwise; this is optimal. Moreover, as long as no fault occurs, FGGC needs only f + 1 replicas to progress.
Type de document :
Communication dans un congrès
SRDS 2011 - 30th IEEE Symposium on Reliable Distributed Systems, Oct 2011, Madrid, Spain. IEEE Computer Society, pp.255--264, 2011, 〈10.1109/SRDS.2011.38〉
Liste complète des métadonnées

Littérature citée [18 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00932839
Contributeur : Marc Shapiro <>
Soumis le : vendredi 17 janvier 2014 - 17:52:20
Dernière modification le : vendredi 25 mai 2018 - 12:02:03
Document(s) archivé(s) le : vendredi 18 avril 2014 - 11:53:19

Fichier

FGGC-SRDS-2011.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Pierre Sutra, Marc Shapiro. Fast Genuine Generalized Consensus. SRDS 2011 - 30th IEEE Symposium on Reliable Distributed Systems, Oct 2011, Madrid, Spain. IEEE Computer Society, pp.255--264, 2011, 〈10.1109/SRDS.2011.38〉. 〈hal-00932839〉

Partager

Métriques

Consultations de la notice

343

Téléchargements de fichiers

132