TY - GEN
T1 - Fast genuine generalized consensus
AU - Sutra, Pierre
AU - Shapiro, Marc
PY - 2011/12/14
Y1 - 2011/12/14
N2 - 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.
AB - 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.
KW - algorithms
KW - consensus
KW - distributed systems
KW - fault-tolerance
KW - reliability
UR - https://www.scopus.com/pages/publications/83155184610
U2 - 10.1109/SRDS.2011.38
DO - 10.1109/SRDS.2011.38
M3 - Conference contribution
AN - SCOPUS:83155184610
SN - 9780769544502
T3 - Proceedings of the IEEE Symposium on Reliable Distributed Systems
SP - 255
EP - 264
BT - Proceedings - 2011 30th IEEE International Symposium on Reliable Distributed Systems, SRDS 2011
T2 - 2011 30th IEEE International Symposium on Reliable Distributed Systems, SRDS 2011
Y2 - 4 October 2011 through 7 October 2011
ER -