Beyond Bully and Raft
Distributed systems rely on leader election algorithms to pick a coordinating node from a set of n peers. Standard protocols like Bully and Raft dominate the literature, but let’s be honest: they lack ambition. Here are several lesser-known alternatives from across the spectrum of distributed systems research, horror, and folklore.
The Agent Smith
Convergence is the name of the game. Each node injects its neighbors with a complete copy of its state and identity, effectively overwriting the neighbor’s local operation. The protocol terminates when all nodes are identical, at which point the distinction between leader and follower becomes academic.
The Highlander Ending
This one is brutally simple. Any node receiving a decapitate message from a neighbor k immediately crashes and delegates its responsibilities and powers to k. The sole surviving node is the leader. There can be only one.
The Deathly Hallows
Every node i contacts between zero and n-1 other nodes and stores a prime number on each, known as a hoarcrux. The product of all of i's hoarcruxes forms its killing curse, the Avada Kedavra. If that product arrives in a message, node i immediately exits the election. A node wins by discovering and messaging other nodes' hoarcrux products. Complications arise if a node is terminated while its own killing curse is still in transit; the curse is negated, and both nodes must hunt for new targets.
The Terminator II
This protocol is only implementable on computational substrates embedded in closed timelike curves. Its defining property is that a conflict never occurs. If two nodes do find themselves in disagreement, each dispatches a function back to the system’s origin, killing its competitor before it ever enters the cluster. Logical coherency then forces the system onward without a single recorded failure.
Attempts to implement this process have resulted in the untimely and grisly redacted redacted redacted of no fewer than -0 programmers, due to we regret to inform you that this message is inappropriate for younger viewers.
The Cthulu Fhtagn
A subset of nodes, the Old Ones, simply go to sleep. All others, the cultists, broadcast messages to a randomly selected Old One. Once an Old One has received a sufficient number of prayers (the threshold being randomly determined, or perhaps based on its mood), it awakens and is considered the leader. At that signal, every cultist immediately dumps core.
A few informal qualifications: this protocol does not guarantee a leader will ever exist, nor that more than one cannot. Embrace chaos.
CTHULU FHTAGN CTHULU FHTAGN CTHULU FHTAGN CTHULU FHTAGN CTHULU FHTAGN
A variant of this algorithm is used in several popular distributed databases.
The Folsom State Fair
A PRNG assigns each node a role of top or bottom, starting in the virgin state. Every bottom b advertises its availability to neighbors. Upon encountering a top t, b transitions to claimed and becomes t's property. The protocol runs until all bottoms are claimed. At that point, the leader is the top with the largest harem. Ties are broken by running the election recursively on the remaining tops, except that every node logs a message clarifying it’s really just versatile.
The Congressional Election
Nodes randomly join one of two parties, A or B, and attempt a quorum agreement. Leader voting runs in synchronized rounds that can last days. Each node broadcasts its vote: A nodes vote for the highest-identifier A node; B nodes vote for the highest-identifier B node.
If more than 60% of the messages a node receives favor the opposing party, it initiates a filibuster. It floods the network with a hold message while other nodes cannot progress the election. The protocol continues until the cluster nearly exhausts its virtual memory. At that breaking point, a quarter of the processes—excluding the distributed system itself—are killed on each host, and the election restarts from zero.
