Anonymous rings

A ring is said to be anonymous if every processor is identical. More formally, the system has the same state machine for every processor.^[3] There is no deterministic algorithm to elect a leader in anonymous rings, even when the size of the network is known to the processes.^[3][6] This is due to the fact that there is no possibility of breaking symmetry in an anonymous ring if all processes run at the same speed. The state of processors after some steps only depends on the initial state of neighbouring nodes. So, because their states are identical and execute the same procedures, in every round the same messages are sent by each processor. Therefore, each processor state also changes identically and as a result if one processor is elected as a leader, so are all the others.

For simplicity, here is a proof in anonymous synchronous rings. It is a proof by contradiction. Consider an anonymous ring R with size n>1. Assume there exists an algorithm "A" to solve leader election in this anonymous ring R.^[3]

Lemma: after round ${\displaystyle k}$ of the admissible execution of A in R, all the processes have the same states.

Proof. Proof by induction on ${\displaystyle k}$.

Base case: ${\displaystyle k=0}$: all the processes are in the initial state, so all the processes are identical.

Induction hypothesis: assume the lemma is true for ${\displaystyle k-1}$ rounds.

Inductive step: in round ${\displaystyle k}$, every process send the same message ${\displaystyle m_{r}}$ to the right and send the same message ${\displaystyle m_{l}}$ to the left. Since all the processes are in the same state after round ${\displaystyle k-1}$, in round k, every process will receive the message ${\displaystyle m_{r}}$ from the left edge, and will receive the message ${\displaystyle m_{l}}$ from the right edge. Since all processes are receiving the same messages in round ${\displaystyle k}$, they are in the same state after round ${\displaystyle k}$.

The above lemma contradicts the fact that after some finite number of rounds in an execution of A, one process entered the elected state and other processes entered the non-elected state.

Randomized (probabilistic) leader election

A common approach to solve the problem of leader election in anonymous rings is the use of probabilistic algorithms. In such approaches, generally processors assume some identities based on a probabilistic function and communicate it to the rest of the network. At the end, through the application of an algorithm, a leader is selected (with high probability).

Asynchronous ring^[3]

O(nlogn) algorithm for asynchronous ring

Since there is no algorithm for anonymous rings (proved above), the asynchronous rings would be considered as asynchronous non-anonymous rings. In non-anonymous rings, each process has a unique ${\displaystyle id}$, and they don't know the size of the ring. Leader election in asynchronous rings can be solved by some algorithm with using ${\displaystyle O(n^{2})}$ messages or ${\displaystyle O(n\log n)}$ messages.

In the ${\displaystyle O(n^{2})}$ algorithm, every process sends a message with its ${\displaystyle id}$ to the left edge. Then waits until a message from the right edge. If the ${\displaystyle id}$ in the message is greater than its own ${\displaystyle id}$, then forwards the message to the left edge; else ignore the message, and does nothing. If the ${\displaystyle id}$ in the message is equal to its own ${\displaystyle id}$, then sends a message to the left announcing myself is elected. Other processes forward the announcement to the left and turn themselves to non-elected. It is clear that the upper bound is ${\displaystyle O(n^{2})}$ for this algorithm.

In the ${\displaystyle O(n\log n)}$ algorithm, it is running in phases. On the ${\displaystyle k}$th phase, a process will determine whether it is the winner among the left side ${\displaystyle 2^{k}}$ and right side ${\displaystyle 2^{k}}$ neighbors. If it is a winner, then the process can go to next phase. In phase ${\displaystyle 0}$, each process ${\displaystyle P}$ needs to determine itself is a winner or not by sending a message with its ${\displaystyle id}$ to the left and right neighbors (neighbor do not forward the message). The neighbor replies an ${\displaystyle ACK}$ only if the ${\displaystyle id}$ in the message is larger than the neighbor's ${\displaystyle id}$, else replies an ${\displaystyle ACK_{fault}}$. If ${\displaystyle P}$ receives two ${\displaystyle ACK}$s, one from the left, one from the right, then ${\displaystyle P}$ is the winner in phase ${\displaystyle 0}$. In phase ${\displaystyle k}$, the winners in phase ${\displaystyle k-1}$ need to send a message with its ${\displaystyle id}$ to the ${\displaystyle 2^{k}}$ left and ${\displaystyle 2^{k}}$ right neighbors. If the neighbors in the path receive the ${\displaystyle id}$ in the message larger than their ${\displaystyle id}$, then forward the message to the next neighbor, otherwise reply an ${\displaystyle ACK_{fault}}$. If the ${\displaystyle 2^{k}}$th neighbor receives the ${\displaystyle id}$ larger than its ${\displaystyle id}$, then sends back an ${\displaystyle ACK}$, otherwise replies an ${\displaystyle ACK_{fault}}$. If the process receives two ${\displaystyle ACK}$s, then it is the winner in phase ${\displaystyle k}$. In the last phase, the final winner will receive its own ${\displaystyle id}$ in the message, then terminates and send termination message to the other processes. In the worst case, each phase there are at most ${\displaystyle {\frac {n}{2^{k}+1}}}$ winners, where ${\displaystyle k}$ is the phase number. There are ${\displaystyle \lceil \log(n-1)\rceil }$ phases in total. Each winner sends in the order of ${\displaystyle 2^{k}}$ messages in each phase. So, the messages complexity is ${\displaystyle O(n\log n)}$.

Rings with unique IDs

In one of the early works, Chang and Roberts^[14] proposed a uniform algorithm in which a processor with the highest ID is selected as the leader. Each processor sends its ID in a clockwise direction. A process receiving a message and compares it with its own. If it is bigger, it passes it through, otherwise it will discard the message. They show that this algorithm uses at most ${\displaystyle O(n^{2})}$ messages and ${\displaystyle O(n\log n)}$ in the average case.
Hirschberg and Sinclair^[15] improved this algorithm with ${\displaystyle O(n\log n)}$ message complexity by introducing a 2 directional message passing scheme allowing the processors to send messages in both directions.

Unoriented mesh

A typical algorithm to solve the leader election in an unoriented mesh is to only elect one of the four corner nodes as the leader. Since the corner nodes might not be aware of the state of other processes, the algorithm should first wake up the corner nodes. A leader can be elected as follows.^[17]

1. Wake-up process: in which ${\displaystyle k}$ nodes initiate the election process. Each initiator sends a wake-up message to all its neighbouring nodes. If a node is not initiator, it simply forwards the messages to the other nodes. In this stage at most ${\displaystyle 3n+k}$ messages are sent.
2. Election process: the election in outer ring takes two stages at most with ${\displaystyle 6(a+b)-16}$ messages.
3. Termination: leader sends a terminating message to all nodes. This requires at most 2n messages.

The message complexity is at most ${\displaystyle 6(a+b)-16}$, and if the mesh is square-shaped, ${\displaystyle O({\sqrt {n}})}$.

Oriented mesh

An oriented mesh is a special case where port numbers are compass labels, i.e. north, south, east and west. Leader election in an oriented mesh is trivial. We only need to nominate a corner, e.g. "north" and "east" and make sure that node knows it is a leader.

Torus

Torus network structure.

A special case of mesh architecture is a torus which is a mesh with "wrap-around". In this structure, every node has exactly 4 connecting edges. One approach to elect a leader in such a structure is known as electoral stages. Similar to procedures in ring structures, this method in each stage eliminates potential candidates until eventually one candidate node is left. This node becomes the leader and then notifies all other processes of termination.^[16] This approach can be used to achieve a complexity of O(n). There also more practical approaches introduced for dealing with presence of faulty links in the network.^[18][19]

Shout

Shout (protocol) builds a spanning tree on a generic graph and elects its root as leader. The algorithm has a total cost linear in the edges cardinality.

Mega-Merger

This technique in essence is similar to finding a Minimum Spanning Tree (MST) in which the root of the tree becomes the leader. The basic idea in this method is individual nodes merge with each other to form bigger structures. The result of this algorithm is a tree (a graph with no cycle) whose root is the leader of entire system. The cost of mega-merger method is ${\displaystyle O(m+n\log n)}$ where m is the number of edges and n is the number of nodes.

Yo-yo

An example of YO-YO procedure. a) The network, b) Oriented network after setup phase, c) YO- phase in which source values are passed, d)-YO phase sending responses from sinks, e) updated structure after -YO phase.

Yo-yo (algorithm) is a minimum finding algorithm consisting of two parts: a preprocessing phase and a series of iterations.^[16] In the first phase or setup, each node exchanges its id with all its neighbours and based on the value it orients its incident edges. For instance, if node x has a smaller id than y, x orients towards y. If a node has a smaller id than all its neighbours it becomes a source. In contrast, a node with all inward edges (i.e., with id larger than all of its neighbours) is a sink. All other nodes are internal nodes.
Once all the edges are oriented, the iteration phase starts. Each iteration is an electoral stage in which some candidates will be removed. Each iteration has two phases: YO- and –YO. In this phase sources start the process to propagate to each sink the smallest values of the sources connected to that sink.

Yo-

1. A source (local minima) transmits its value to all its out-neighbours
2. An internal node waits to receive a value from all its in-neighbours. It calculates the minimum and sends it to out-neighbour.
3. A sink (a node with no outgoing edge) receives all the values and compute their minimum.

-yo

1. A sink sends YES to neighbours from which saw the smallest value and NO to others
2. An internal node sends YES to all in-neighbours from which it received the smallest value and NO to others. If it receives only one NO, it sends NO to all.
3. A source waits until it receives all votes. If all YES, it survives and if not, it is no longer a candidate.
4. When a node x sends NO to an in-neighbour y, the logical direction of that edge is reversed.
5. When a node y receives NO from an out-neighbour, it flips the direction of that link.

After the final stage, any source who receives a NO is no longer a source and becomes a sink. An additional stage, pruning, also is introduced to remove the nodes that are useless, i.e. their existence has no impact on the next iterations.

1. If a sink is leaf, then it is useless and therefore is removed.
2. If, in the YO- phase the same value is received by a node from more than one in-neighbour, it will ask all but one to remove the link connecting them.

This method has a total cost of O(mlogn) messages. Its real message complexity including pruning is an open research problem and is unknown.

Models and runtime

In radio networks, the n nodes may in every round choose to either transmit or receive a message. If no collision detection is available, then a node cannot distinguish between silence or receiving more than one message at a time. Should collision detection be available, then a node may detect more than one incoming message at the same time, even though the messages itself cannot be decoded in that case. In the beeping model, nodes can only distinguish between silence or at least one message via carrier sensing.

Known runtimes for single-hop networks range from a constant (expected with collision detection) to O(n log n) rounds (deterministic and no collision detection). In multi-hop networks, known runtimes differ from roughly O((D+ log n)(log² log n)) rounds (with high probability in the beeping model), O(D log n) (deterministic in the beeping model), O(n) (deterministic with collision detection) to O(n log^3/2 n (log log n)^0.5) rounds (deterministic and no collision detection).