Leader Election for Auto Recovery

systemdesign

ETCD
Kubernetes

Orchestrator and Leader Election

In distributed systems, orchestration is responsible for managing server life cycles—such as spinning up new instances when one goes down.

Problem

• If a server goes down → Orchestrator spins up a new one.
• But if the orchestrator itself goes down → System fails to recover.

Solution: Leader-Follower Setup

To address orchestrator failure, we use leader election.

Leader-Follower Architecture:

• Run multiple orchestrator nodes, each with the orchestration logic.
• One node is elected as the leader.
• The leader performs orchestration tasks (e.g., spinning up new servers).
• The followers stay in standby, ready to take over if the leader fails.

This setup ensures high availability and fault tolerance for the orchestrator module.

Common Tools:

• etcd, Consul, Zookeeper – provide leader election and coordination mechanisms.
• Raft or Paxos algorithms – used for consensus and leader election.

Leader Election Algorithms

Many tasks in DS require one of the processes act as the coordinator. Election algorithms are techniques for a distributed system of $N$ processes to elect a coordinator(leader).

An example of this is the Berkeley algorithm for clock synchronization, in which the coordinator has to initiate the synchronization and tell the processes their offsets. A coordinator can be chosen amongst all processes through leader election.

Common Leader Election Algorithms

1. Bully Algorithm
   • Any node can initiate an election.
   • Highest-ID node wins and becomes the leader.
   • Simple but assumes reliable communication.
   • Works well in systems where IDs can be ranked (e.g., IP address).
2. Ring Algorithm
   • Nodes are arranged in a logical ring.
   • A token or election message is passed; the node with the highest ID becomes the leader.
   • No central coordinator needed.

INFO

Leader Election Algorithms and Consensus Algorithms

Leader Election for Auto Recovery

Feature	Leader Election	Consensus
Goal	Pick one leader	Agree on a value/log
Fault Tolerance	Handles leader failure	Handles node/network failure
Examples	Bully, Ring, Raft election	Paxos, Raft, PBFT
Real-World Systems	Kubernetes, Zookeeper	etcd, Consul, Blockchain systems

Bully Algorithm

What is a bully election algorithm?

It’s called “bully” because the node with the highest ID forces others to acknowledge it as the leader.

Assumption

1. Every node has a unique ID(number or IP)
2. Every node knows the ids of all other nodes
3. Communication between nodes is reliable(Messages are eventually delivered)
4. Node can detect leader failures(e.g. via heartbeat or timeout)

Core Concepts

• Node IDs: Higher IDs have higher “priority”.
• Election Trigger: A node triggers an election if it detects that the leader has failed (e.g., not responding).
• Election Messages: A node sends messages to all nodes with higher IDs asking them to take over.
• Responses:
  • If no one replies → it becomes the new leader.
  • If any higher-ID node replies → it gives up and waits for a result.
• Leader Announcement: The new leader broadcasts a COORDINATOR message to all nodes.

Steps in the Bully Algorithm

1. Leader Failure
   • Node 3 detects that the current leader (e.g., node 5) is not responding.
2. Election Starts
   • Node 3 sends an ELECTION message to all higher-ID nodes (4, 5).
3. Wait for Response
   • If node 4 or 5 is alive, it will respond with an OK message and then start its own election.
   • If no one responds, node 3 declares itself the leader
4. Coordinator Announcement
   • Whoever wins the election (highest alive node) sends a COORDINATOR message to all nodes to declare leadership.

• Node 3 starts an election → sends ELECTION:3 to nodes 4 and 5
• Node 5 replies with OK:5, starts its own election
• Node 5 sends ELECTION:5 to no one (since it’s the highest)
• Node 5 declares itself leader → sends COORDINATOR:5 to all

Leader Election for Auto Recovery

---

Common Consensus Algorithms:

Let’s take a crack at understanding distributed consensus

Ensure all nodes agree on a single value or sequence of operations, even with failures or network issues.

1. Paxos
   • A theoretical foundation for consensus in asynchronous systems.
   • Very robust but hard to implement and understand.
   • Roles: proposers, acceptors, learners.
2. Raft
   • A more understandable and practical alternative to Paxos.
   • Combines leader election, log replication, and safety guarantees.
   • Widely used (e.g., in etcd, Consul).
3. Viewstamped Replication
   • Similar to Paxos/Raft.
   • Uses views (epochs) and replication to achieve consensus.
   • Used in systems like VMware’s fault-tolerant storage.
4. PBFT (Practical Byzantine Fault Tolerance)
   • Works in the presence of Byzantine faults (malicious actors).
   • Tolerates up to f faulty nodes in a network of 3f+1 nodes.
   • Used in some blockchains and permissioned distributed ledgers.