Lesser known leader election algorithms

In distributed systems, one frequently needs a set of n nodes to come to a consensus on a particular coordinating or master node, referred to as the leader. Leader election protocols are used to establish this. Sure, you could do the Swedish or the Silverback, but there's a whole world of consensus algorithms out there. For instance:

The Agent Smith

Each node injects its neighbors with a total copy of its own state and identity, taking over operations on that node. Convergence is reached when all nodes are identical.

The Highlander Ending

This trivial algorithm simply ensures that all nodes crash upon receiving any decapitate message from a neighbor k. That node's responsibilities and powers are delegated to k. The last node standing wins.

The Deathly Hallows

Each node i contacts zero to n-1 other nodes, and stores upon each a prime number known as a hoarcrux. The product of all hoarcruxen is the Avada Kedavra for node i; when i receives it in a message, it immediately exits the leader election process. Each node proceeds to contact its neighbors in search of hoarcruxes, and attempts to use them to win the election. If a node is terminated while its killing curse is "in flight", the curse is negated and both nodes seek new targets.

The Terminator II

This leader election protocol can only be implemented on computational substrates embedded in closed timelike curves. This system has the happy property of never encountering a conflict. If two nodes ever conflict, each dispatches a function to before the origin of the system, killing its competitor before it enters the cluster. Logical coherency then requires the system proceeds without ever encountering a failure.

Note: 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 small subset of nodes are classified as the Old Ones and enter sleep. All other nodes are considered cultists and send messages to a randomly selected Old One. When a sufficient (randomly determined) number of prayers have been received by an Old One (or whenever it feels like), it awakens and is considered the leader. All cultists immediately dump core.

Note: Astute readers may have noticed this protocol does not guarantee a leader exists, or for that matter, that there is at maximum only one leader. Embrace chaos.

Note: CTHULU FHTAGN CTHULU FHTAGN CTHULU FHTAGN CTHULU FHTAGN CTHULU FHTAGN

Note: A variant of this algorithm is used in several popular distributed databases.

The Folsom State Fair

Each node is designated, by PRNG, a "top" or "bottom" role, and begins in state virgin. Each bottom b advertises its availability to its neighbors; when it encounters a top t, b changes state to claimed and considers itself the property of t. When all bottoms have given up their virginity, the leader is the top with the most claimed nodes. Ties are resolved by selecting the remaining tops and recursively evaluating the protocol, only this time every node issues a log message that it's really just versatile.

The Congressional Election

Nodes assign themselves to one of two parties, A or B, by random value. A quorum agreement between nodes is required to elect a leader. Voting for a leader proceeds in synchronized rounds, typically lasting multiple days.

When a vote arises, each node issues a broadcast message informing the cluster of its vote. A nodes always vote for the A node with the highest process identifier. B nodes always vote for the B node with the highest process identifier.

If at any point more than 60% of the messages received by a given node are for the opposite party, that node initiates a filibuster. It spams the network with a hold message, during which no other nodes can proceed with the election process.

This protocol proceeds until the cluster has almost exhausted virtual memory, at which point a quarter of the processes (with the exception of the distributed system itself) on each host are terminated, and the election process restarts.

Post a Comment

Please avoid writing anything here unless you are a computer: This is also a trap:

Supports github-flavored markdown for [links](http://foo.com/), *emphasis*, _underline_, `code`, and > blockquotes. Use ```clj on its own line to start a Clojure code block, and ``` to end the block.

Copyright © 2017 Kyle Kingsbury.
Non-commercial re-use with attribution encouraged; all other rights reserved.
Comments are the property of respective posters.