Leader Election Algorithm

What is Leader Election?

In distributed systems, many tasks require coordination. Often, it's simpler and more efficient to designate one node as a leader (or coordinator, master) responsible for making decisions, managing state, or coordinating actions among other nodes (followers).

A Leader Election Algorithm is a process by which nodes in a distributed system agree on which node will assume the leader role. This is crucial when:

• A system starts up and needs an initial leader.
• The current leader fails or becomes unreachable.

The goal is to ensure that, eventually, all non-faulty nodes agree on a single, unique leader.

Common Assumptions: Most algorithms assume each node has a unique ID, and communication between non-failed nodes is reliable (though messages might be delayed).

Bully Algorithm

This algorithm assumes nodes know the IDs and addresses of all other nodes and that messages are eventually delivered. The node with the highest ID among the currently active nodes becomes the leader.

• Trigger: A node `P` detects the leader has failed (e.g., no heartbeat) or starts up.
• Election Process:
  1. `P` sends an ELECTION message to all nodes with IDs higher than its own.
  2. `P` waits for responses (OK or ALIVE messages).
  3. If `P` receives no response from any higher-ID node within a timeout, it considers itself the winner. It declares itself the leader and sends COORDINATOR (or LEADER) messages to all other nodes.
  4. If `P` does receive an OK response from a higher-ID node `Q`, `P` knows it cannot be the leader. It simply waits for `Q` (or another higher node) to eventually send a COORDINATOR message. `Q` takes over the election process from step 1.
• Receiving Messages:
  • If a node receives an ELECTION message from a lower-ID node, it sends back an OK message and starts its own election (if not already started).
  • If a node receives a COORDINATOR message, it recognizes the sender as the new leader.
• Pros: Relatively simple concept. The highest ID node naturally "bullies" its way to leadership.
• Cons: Requires knowing all other node IDs. Can generate significant message traffic if many nodes start elections simultaneously. Assumes reliable message delivery for correctness.

Ring Algorithm

Nodes are arranged in a logical ring (each node knows its successor). It doesn't require knowing all nodes, only the next one. It aims to elect the highest ID node among active participants.

• Trigger: A node `P` detects the leader has failed.
• Election Process:
  1. `P` marks itself as a participant in the election.
  2. `P` creates an ELECTION message containing its own ID: `[P_ID]`.
  3. `P` sends this message to its successor node in the ring.
  4. When a node `Q` receives an ELECTION message `[ID1, ID2, ...]`:
     • It adds its own ID to the list: `[ID1, ID2, ..., Q_ID]`.
     • It marks itself as a participant.
     • It forwards the updated message to its successor.
  5. When the ELECTION message travels all the way around the ring and arrives back at the original initiator `P`:
     • `P` recognizes its own ID in the received list (if it wasn't already there - simple check: first ID matches its own).
     • `P` examines the list of IDs in the message.
     • `P` selects the node with the highest ID from the list as the new leader.
     • `P` creates a COORDINATOR message containing the chosen leader's ID.
     • `P` sends the COORDINATOR message around the ring.
• Receiving Coordinator Message: When a node receives a COORDINATOR message:
  • It records the new leader's ID.
  • It marks itself as no longer a participant (election finished).
  • It forwards the COORDINATOR message to its successor (unless it was the originator).
• Pros: Uses fewer messages typically than Bully (one election message, one coordinator message circulates). Doesn't require knowing all nodes.
• Cons: Message latency depends on ring size. If one node fails, the ring is broken (needs mechanisms to reconstruct the ring, not covered here).

Raft/Paxos Election

These are more complex consensus algorithms where leader election is a core part. They involve concepts like terms (election epochs), candidate states, voting (RequestVote RPCs), achieving a majority quorum, and ensuring log consistency. Visualizing the full Raft/Paxos election is beyond the scope of this simple tool, but the core idea is nodes transition to candidate state, request votes from others within a specific term, and become leader only upon receiving votes from a majority.