Leader Election: Gallager-Humblet-Spira (GHS) algorithm

GHS is an algorithm to elect a leader in the arbitrary network. It is based on building a minimal spanning tree (MST) of the network, and then based on it electing a leader.

Algorithm for building MST is very similar to the Kruskal's algorithm, although it has some specifics for the nodes distributed in the arbitrary networks. For example, the nodes have to communicate with each other in order to detect connected components, merge etc. After the MST is built, one of the nodes is chosen to be a leader. The notification is sent to all other nodes in the MST.

Basically, the goal of this algorithm is to identify the nodes in the network, and the elect a leader in the known field.


Algorithm of building MST is very interesting:

1. Nodes are organized into fragment. Initial fragment size is 1 and contains only single node. On every new step, fragments are merged, so now the fragment size increases.
2. Each fragment (ie each node in the fragment) keeps next information: it's level and name. Level is a number of merges with same-size fragments, name usually is the name (weight) of the edge that connected the fragments.
3. When 2 fragments of the same level are found, they are connected into single fragment, the level of this fragment is increased by 1.
4. When 2 fragments of different size are found, the fragment with smaller level is merged into the fragment of larger level. The level information is changed in the merged fragment (ie fragment with lower level). Lower level means smaller size, thus smaller number of nodes need to be updated with new level information.
5. When there is no fragment that is connected to the existing fragment via some edge, the MST is built.

Algorithm uses number of different messages to identify neighbor fragments that could be connected. The messages to find the minimal weight edge and run by nodes are test, reject or accept. Another messages are connect the fragment, change root etc.

The message complexity of the algorithm is 2E + 5N log N, ie O(E + N log N).

There is an alternative algorithm to the GHS, which however sends more messages. It is based on wave message and extinction. Each node sends a message with it's id to each connected node. Each connected node keeps the currently active wave, that is the minimal id it has received. Whenever such node updates it currently active wave value, it sends a message with it to its connected nodes. Thus, the wave with minimal id keeps going through each node, while all other waves are terminated eventually. After all nodes sends update with currently active wave equal to the minimal id, algorithm is ready to elect the leader.