Leader election
Leader election algorithms are designed to be economical in terms of total bytes transmitted, and time.
The algorithm suggested by Gallager, Humblet, and Spira[1] for general undirected graphs has had a strong impact on the design of distributed algorithms in general, and won the Dijkstra Prize for an influential paper in distributed computing.
A general method that decouples the issue of the graph family from the design of the leader election algorithm was suggested by Korach, Kutten, and Moran.
[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.
Assume there exists an algorithm "A" to solve leader election in this anonymous ring R.[3] Proof.
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.
Itai and Rodeh[7] introduced an algorithm for a unidirectional ring with synchronized processes.
At the end of each phase, each processor calculates the number of candidates c and if it is equal to 1, it becomes the leader.
To determine the value of c, each candidate sends a token (pebble) at the start of the phase which is passed around the ring, returning after exactly n time units to its sender.
This algorithm achieves leader election with expected message complexity of O(nlogn).
[11] In typical approaches to leader election, the size of the ring is assumed to be known to the processes.
In the case of anonymous rings, without using an external entity, it is not possible to elect a leader.
[13] 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.
An oriented mesh is a special case where port numbers are compass labels, i.e. north, south, east and west.
There also more practical approaches introduced for dealing with presence of faulty links in the network.
In the case of unoriented hypercubes, a similar approach can be used but with a higher message complexity of
Based on this scheme, the highest priority candidate eventually knows that all nodes in the system are dummies except itself, at which point it knows it is the leader.
[16] The Shout protocol builds a spanning tree on a generic graph and elects its root as leader.
The result of this algorithm is a tree (a graph with no cycles) whose root is the leader of the entire system.
[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.
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.
Its real message complexity including pruning is an open research problem and is unknown.
In radio network protocols, leader election is often used as a first step to approach more advanced communication primitives, such as message gathering or broadcasts.
[22] The very nature of wireless networks induces collisions when adjacent nodes transmit at the same time; electing a leader allows to better coordinate this process.
While the diameter D of a network is a natural lower bound for the time needed to elect a leader, upper and lower bounds for the leader election problem depend on the specific radio model studied.
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.
In the beeping model, nodes can only distinguish between silence or at least one message via carrier sensing.
