Technical report detail

Multicoordinated Paxos

by Camargos, Lasaro and Schmidt, Rodrigo and Pedone, Fernando

Classic Paxos is a round-based distributed consensus algorithm. Normally, proposals are sent to the round leader and decided in two communication steps more. Fast Paxos extends Classic Paxos by allowing also fast rounds, in which a decision can be learned in two communication steps without relying on a leader but requiring bigger quorums. We extend Fast Paxos and allow yet another sort of round with multiple quorums of coordinators. Such new rounds have the same expected latency and quorum size requirements as classic rounds but do not rely on a single leader, providing better availability and allowing load balance. Fast rounds and ours have a different liveness requirement: the absence of collisions which may happen if different values are proposed concurrently. However, collisions are inherently more expensive in fast rounds. We apply our algorithm to Generalized Consensus, a generalization of agreement problems that can use the application semantics to avoid collisions.

Technical report 2007/02, January 2007

BibTex entry

@techreport{07multicoordinated, author = {Camargos, Lasaro and Schmidt, Rodrigo and Pedone, Fernando}, title = {Multicoordinated Paxos}, institution = {University of Lugano}, number = {2007/02}, year = 2007, month = jan }