Why is Paxos leader election not done using Paxos?

Question

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?

Samite

My understanding: There can be multiple leaders. Only when consensus is reached we have determined the actual leader. So we chose a leader and a proposal at the same time. The two are not separate. – Winer

Answer 1

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.

Turpin

What are the consensus algorithms optimized for? I.e. which is most fault-tolerant, which is quickest, which allows consensus over the greatest amount of data? – Eric

Answer 2

I didn't read the papers you mentioned above, but I've learned during my studies that Paxos is in fact mostly used only to elect a leader, since the algorithm would be too much overhead to sort every message. And the reason you should use it for leader elections is, that it's 100% partition tolerant. All the other algorithms, which I know, aren't. - But there might be more which fulfil this criteria and I don't know of.

I'll read the papers, but what I could get from the Stable Leader Election paper, is that it's just a concept. They first introduce what it is, and afterwards algorithms how to do it. And when they introduce the algorithms they reference Paxos again. (but that was only scanning through the paper, nothing more).

Craniometer

apache zookeeper which runs the ZAB protocol is a strongly consistent store that is often used for leader elections. – Estray

Answer 3

Paxos is a powerful consensus algorithm suitable for solving more complex coordination problems, but it is generally considered overkill for leader election due to its complexity and performance implications.

Using Basic Paxos is inefficient:

1. multiple concurrent proposers, conflicts and restarts are likey
2. 2 rounds of RPCs for each value chose(Prepare, Accept)

Leader election algorithms that do not necessarily rely on a majority quorum can handle such situations more effectively.

For example: leases

Leases are the most widely used leader election mechanism, they are relatively straightforward to understand and implement, and they offer built-in fault tolerance. Leases work by having a single database that stores the current leader. Then, the lease requires that the leader heartbeat periodically to show that it’s still the leader. If the existing leader fails to heartbeat after some time, other leader candidates can try to take over.

Article