Q2Distributed System

In many distributed architectures, a single node is mathematically designated as the "Coordinator" or "Master" (e.g., the JobTracker in Hadoop, or the master node in a database cluster). If this master server violently loses power or its network cable is severed, the entire cluster is instantly paralyzed. An Election Algorithm is the aggressive mathematical protocol executed by the surviving nodes to instantly, autonomously elect a new, unambiguous Coordinator to restore architectural order.

Engineered by Garcia-Molina, the Bully Algorithm is a highly aggressive, hierarchical protocol. It mathematically assumes every single node possesses a unique, hardcoded integer ID, and all nodes know the IDs of all other nodes.

The Execution Trace

• 1. Detection: Node 4 mathematically detects that the Master (Node 7) has crashed because it stops responding to heartbeat pings.
• 2. The Aggression: Node 4 instantly blasts an ELECTION message, but strictly ONLY to nodes with a mathematically higher ID than itself (Nodes 5, 6, and 7).
• 3. The Bullying: If Node 5 and 6 are alive, they instantly reply with an OK message to Node 4, violently forcing Node 4 to shut up and drop out of the election. Node 5 and 6 then blast their own ELECTION messages to higher nodes.
• 4. The Victor: Node 6 blasts an ELECTION to Node 7. Node 7 is dead, so it receives zero replies. Because Node 6 mathematically receives no OK messages, it definitively proves it is the highest surviving ID.
• 5. The Proclamation: Node 6 aggressively blasts a COORDINATOR message to ALL lower-numbered nodes (1, 2, 3, 4, 5), violently forcing them to accept it as the new absolute Master.

Message Complexity

The worst-case mathematical scenario occurs if the lowest ID node detects the crash first. It blasts messages to everyone, they blast to everyone, resulting in a catastrophic $O(N^2)$ message complexity. In a 1,000-node cluster, this will generate nearly a million network packets, causing a massive broadcast storm.

A highly structured, network-efficient algorithm that completely ignores the physical network topology, mapping all nodes into a rigid, mathematical logical circle ($0\to 1\to 2\to ...\to N\to 0$).

The Execution Trace

• 1. Detection: Node 2 detects the Master (Node 7) is dead.
• 2. The Token Build: Node 2 generates an ELECTION message packet, writes its own ID [2] inside, and violently fires it to its next logical neighbor (Node 3).
• 3. The Circulation: Node 3 receives [2], mathematically appends its own ID, generating [2, 3], and fires it to Node 4. Node 4 adds its ID: [2, 3, 4].
• 4. Dead Node Bypass: When the message reaches Node 6, it attempts to fire it to Node 7 (the dead Master). The TCP connection fails. Node 6 mathematically skips Node 7 and fires it directly to Node 0.
• 5. The Resolution: Eventually, the massive message packet circulates all the way back to the originator (Node 2). Node 2 mathematically scans the list of all surviving IDs in the packet. It selects the absolute highest integer.
• 6. The Proclamation: Node 2 changes the message type to COORDINATOR and circulates it one final time around the ring to inform all nodes of the new Master.

Message Complexity

The Ring algorithm is vastly superior for network health. It mathematically requires exactly $2(N-1)$ messages (one full circulation for the election, one for the proclamation). It completely prevents $O(N^2)$ broadcast storms, though it takes slightly longer to complete.