Menu
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?
507
Performing leader election with Paxos then becomes as simple as proposing the statement “I am the leader”. If it is accepted, then you are the leader until another node proposes to be the leader.
The follower can run for the leader at any time. Although Multi-Paxos might compromise the efficiency, it can restore services quicker when the leader fails. Therefore, Multi-Paxos has better availability than Raft.
Paxos is an algorithm that enables a distributed set of computers (for example, a cluster of distributed database nodes) to achieve consensus over an asynchronous network. To achieve agreement, one or more of the computers proposes a value to Paxos.
Some early solutions to Byzantine faults include the family of consensus protocols known as Paxos (1989)— it uses the common fault tolerant method of state machine replication involving several roles, a quorum rule, and two “promise” and “accept” phases in which nodes communicate to learn an agreed value.
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.
192
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
