Gauntlet 11: Distributed Consensus via Bully Algorithm
Distributed clusters must elect a single coordinator node to avoid split-brain disasters. In Garcia-Molina's Bully Algorithm, when a leader failure is detected, nodes query higher-numbered peers. If no higher peer responds, the inquiring node declares itself coordinator and broadcasts victory.
# Bully election query:
higher_peers = [p for p in peers if p.id > self.id and p.is_alive]
if not higher_peers:
self.declare_coordinator()
# Gauntlet 11: Distributed Consensus via Bully Algorithm In distributed systems (like Cassandra, Raft, or Elasticsearch), having multiple nodes simultaneously believe they are the write coordinator causes **Split-Brain**: conflicting writes corrupt state beyond repair. 👑🗳️ Hector Garcia-Molina's classic **Bully Algorithm** guarantees consensus across nodes with unique integer IDs: 1. When any node detects that the active leader has crashed, it initiates an **Election**. 2. It sends an `ELECTION` message to every node in the cluster that has a **higher ID**. 3. If no higher node responds (or all higher nodes are dead), this node "bullies" the rest of the cluster: it crowns itself **Coordinator** and broadcasts a victory message to all lower-ID nodes. 4. If a higher node is alive, that higher node takes over the election and continues the process upward. ```python # The highest active node ID always wins: higher_alive = [node for node in cluster if node.id > self.id and node.is_alive] ``` ## Pop Quiz Why is the consensus algorithm named the "Bully" Algorithm? - [ ] The active node with the highest numerical ID always bullies lower-ranked nodes into submission and assumes leadership. - [ ] Nodes forcefully terminate unresponsive worker processes via kernel SIGKILL signals. - [ ] It overloads network interfaces with UDP flood packets to intimidate peer sockets. - [ ] Because election requests bypass firewall permissions. ## Real-World Challenge Implement `ClusterNode(node_id: int, cluster: dict)`: - `start_election()`: Contacts all alive nodes with `id > self.node_id`. If none are alive, calls `become_coordinator()`. Otherwise, passes election to higher nodes. - `become_coordinator()`: Sets `current_leader = self.node_id` on all alive cluster nodes. - Verify that if Leader Node 5 dies, Node 2's election cleanly promotes Node 4. <details> <summary>Solution</summary> ```python class ClusterNode: def __init__(self, node_id: int, cluster_ref: dict): self.node_id = node_id self.cluster = cluster_ref # id -> ClusterNode self.is_alive = True self.current_leader = None def start_election(self): # Query all higher-ranked nodes higher_alive_nodes = [ peer for peer_id, peer in self.cluster.items() if peer_id > self.node_id and peer.is_alive ] if not higher_alive_nodes: # We are the highest living node in the cluster self.become_coordinator() else: # Pass the torch to the highest living nodes for higher_peer in higher_alive_nodes: higher_peer.start_election() def become_coordinator(self): for peer_id, peer in self.cluster.items(): if peer.is_alive: peer.current_leader = self.node_id # Verification nodes = {} for i in [1, 2, 3, 4, 5]: nodes[i] = ClusterNode(i, nodes) # 1. Initial election started by lowest node 1 -> highest node 5 becomes leader nodes[1].start_election() for n in nodes.values(): assert n.current_leader == 5 # 2. Node 5 crashes nodes[5].is_alive = False # Node 2 discovers leader is dead and triggers election nodes[2].start_election() # Node 4 must be elected as the new cluster coordinator for node_id, node in nodes.items(): if node.is_alive: assert node.current_leader == 4, f"Node {node_id} has leader {node.current_leader}" ``` </details>