Consensus and Leader Election
Notes
- Sometimes in a parallel computation we need one process to act as leader.
- In the Leibniz pi computation, we used the processor with id 1.
- This is problematic is a distributed system for nodes can fail.
- We would like the system to be fault tolerant
- The RAFT algorithm provides a method for leader election
- this handles fault tolerance
- If a leader fails, a new node will be elected
- But in the basic form does not handle Byzantine Faults (members providing false responses)
- In this approach, the distributed system has only one leader responsible for all of the decisions
- The leader regularly sends out a heartbeat message
- This indicates that it is still "alive" and in charge
- If other nodes fail to receive this heartbeat, they will initiate a new leader election
- In the RAFT language, this starts a new term
- A term starts with a leader election
- When successful, the new leader remains in charge until the term ends as above.
- In RAFT each node is in one of three states
- follower - default
- candidate - potential leader
- leader
- All nodes start as a follower.
- But if they don't get a heartbeat from a leader in a required amount of time, they become a candidate.
- The time to wait for a heartbeat is random, normally between 150 and 300 ms.
- A candidate requests votes from other nodes to become a leader
- This is done via a request to vote sent to all elements in the computation
- And nominates the sender as a candidate
- Candidates always vote for themselves
- Followers
- Vote for the first candidate they receive a request to vote from.
- But sets an election timeout
- When a candidate receives a majority of votes, they become a leader.
- Elections in a split vote
- Assume two simultaneously declare themselves to be candidates
- Each receives 1/2 the votes
- Since they can't be elected, they will generate a random wait time and try again
- The random wait time means eventually some candidate will win.
- There is a great Visualization, with links to a great tutorial.