protocolsdistributeddistributed-transactionspaxosconsensus

Why is Paxos leader election not done using Paxos?


The questions below are intended to be serious rather than frivolous. I lack experience in distributed systems, but I do understand how Basic Paxos works and why leader selection is useful. Unfortunately, my understanding is not deep enough to fathom the questions below.

In the paper Consensus on Transaction Commit, page 8 (page 11 of the linked PDF), we have the following statement.

Selecting a unique leader is equivalent to solving the consensus problem.

If this statement is true, and the very purpose of Paxos to achieve consensus, why is Paxos itself not generally used for leader election?

Moreover, the same paper endorses the leader election algorithm described the Stable Leader Election paper.

If the two problems are equivalent, and the same paper endorses a different leader election algorithm, why isn't the other algorithm used for solving the general consensus problem instead of Paxos?


Solution

  • Paxos is used in leader election. In the paxos variants that have leaders (eg. Multi-paxos, Raft), the leader is the node that has its data chosen by the Paxos instance, either that or the leader is elected in its own transition (Some people use the term Paxos instance; I prefer to think of consensus algorithms as choosing the transitions in a distributed finite state machine.)

    All correct consensus algorithms can be mapped to Basic Paxos, but each are optimized for different things. These include Multi Paxos, Raft, ZAB, Vertical Paxos, Cheap Paxos, and Chain Replication. (The latter three—and all consensus algorithms which only need failure_tolerance+1 nodes—also require another consensus system for reconfiguration. But I digress.)

    The Stable Leader Election paper is more than just Paxos: it includes a failure detector (from a cursory glance, it's a lease-based leadership model.) Thus, it is more expensive than Basic Paxos.

    In the systems I maintain that require leaders, the failure detectors will utilize the consensus protocols to depose/elect leaders, but otherwise they are completely separate protocols.