Election Algorithm
An election algorithm can be used in a distributed system to select a single coordinator. When the election is terminated, there is only one node that calls itself the coordinator or declares itself as the leader, and the other nodes know the identity of this coordinator. The problem is to start from a configuration where all processes are in the same state, and despite failures and unreliable proceeses they should finally arrive at a configuration where exactly one node or process is in the state leader and all other process are in the state non-leader. The election problem is often considered in fully connected networks, where every node is connected to every other node so that any node may send a message to any other.
>== Applications ==
The election of a special coordinator is required in general to make a central decision, to initiate or to organize something. A coordinator is needed in distributed systems in particular for
- reorganization and reconfiguration of the system
- centralized solutions (for example centralized mutual exclusion, managing or monitoring a token)
- holding a primary or master copy of replicated data, or selecting a primary backup
An election of "values" instead of coordinators is necessary if sensors offer unreliable data, for instance voting on the value of a sensor. This problem is related to the agreement or consensus problem.
Algorithms
Many algorithms are known for the election problem (for instance from LeLann, Chang-Roberts, Dolev-Klawe-Rodeh, etc.). They are very similar to "FindMax" problems, where the minimal or maximal value among a set of distributed nodes has to be determined. They can be roughly distinguished in those for synchronous systems and those for asynchronous systems. Synchronous systems are of course a bit easier too handle.
Election in Synchronous Networks
Afek and Gafni
In synchronous systems and complete networks with diameter one, there is a trivial algorithm with O(1) rounds and O(n^2) messages. Each node sends messages to all its neighbors, and all nodes elect the node with the highest (or lowest) ID as the leader. In these systems, the election problem is synonymous with the selection a leader in a Clique. A clique is a complete graph with diameter one.
Afek and Gafni showed that the number of messages can be reduced by slowing down the rate in which nodes send messages to their neighbors. This means the message complexity can be reduced only if the time complexity is increased. The algorithm from Afek and Gafni (1985) needs O(log n) rounds, O(n*log n) messages. It works roughly like this: every candidate has a set of links incident to the candidate. In every round each candidate tries to "capture" a bit more from the remaining nodes of this set. Every alive candidate tries to capture 2^n (remaining) nodes in round n. Only nodes which receive all acknowledgements and capture all 2^n nodes survive, the others give up and "quit" the race already. The node with the highest ID who captures all the nodes wins.
Bully Algorithm
One of the classic election algorithms in distributed systems is the Bully Algorithm. It is also an algorithm for complete networks with diameter one, and it is first mentioned by Hector Garcia-Molina in 1982 in his paper "Elections in a Distributed Computing System" (*), together with the "Invitation Election" algorithm. As Garcia-Molina says, it is named Bully because "the node with the highest identification number forces the nodes with smaller identification numbers into accepting it as coordinator". The process with the highest idenfication number or ID among the active nodes always becomes the coordinator.
The first part of the algorithm works as follows: each node in the system is assigned a unique identification number or ID. If a node N notices that the coordinator is no longer active it initiates an election and attempts to contact all nodes with higher priority:
1) If a node N notices that the coordinator is no longer active then it sends an ELECTION message to all processes with higher numbers. 2) If no one responds after a time limit or time-out, N wins the election and becomes coordinator. It can assume that all nodes with higher priority have failed. 3) If one of the nodes with higher number responds, then N gives up and waits until the node with higher number takes over and becomes the new coordinator.
In the second part of the algorithm, the winner must inform all nodes that it is the new coordinator, and sends out a "COORDINATOR" or "I am elected" messages.
Santoro Rotem Algorithm
Nicola Santoro and Doron Rotem proposed in 1985 an algorithm for election in synchronous networks who assumes a simultaneous start (all processes wake-up or start at the same pulse 0) and a known network size. The simple algorithm is described in the book of Gerard Tel (chapter 12.2). It is based on the diameter of the network and the idea that the ID of a node can be used as a measure for the delay time of messages. Each node has a unique ID, and the number of nodes is an upper bound on the network diameter D, which can be determined if the network size is known.
It takes D pulses to flood or broadcast a message through the entire network. If every node with identity/identifier number ID tries to flood the network at the pulse (ID*D), exactly one message is flooded from the node with the smallest identity number ID_min. At that time, all nodes have already indirectly flooded the message "my ID exceeds ID_min" by being quiet - because they have not initiated the flooding of a message.
Each node waits until a message arrives, or the pulse count has reached ID*D - if a message arrives at node i from a node j before the pulse count has reached ID*D (where ID is the number of i and D the diameter), the node j is elected from the node i as a leader - else the node i initiates a flooding itself and becomes the new leader
An example: If we assume that the diameter of the network D=9, then it takes D=9 pulses to flood the entire network. A node with ID=1 would start a flooding a pulse 9, a node with ID=2 would start a flooding at pulse 18. If no message have arrived at pulse 27, the node with ID=3 can be sure no node with lower ID exists, and starts a flooding itself at pulse number ID_min*D=3*9=27. By the pulse 36, all nodes know that the node with ID=3 is the new leader.
Election in Asynchronous Networks
Most algorithms for the election problem in asynchronous networks work with "candidates" who try to capture and invite as many nodes as possible. The candidate which has succeeded in capturing or inviting all nodes becomes the leader.
Invitation Algorithm
The "Invitation Election Algorithm" was discovered by Hector Garcia-Molina in 1982 in his paper "Elections in a Distributed Computing System" (*), together with the "Bully Algorithm". It is based on two main ideas:
1) after a coordinator failure, recovering nodes form single groups 2) coordinators periodically try to combine their group with other groups in order to form larger groups
As Garcia-Molina says, "in the Bully Algorithmus, the active node with the highest priority "forces" all other nodes to refrain from trying to become coordinator", so that the highest priority node wins the election. Instead of forcing nodes, in the Invitation Election Algorithm nodes who wish to become coodinator will "invite" other nodes to join it in forming a new group. A group is a set of nodes that agree on a leader.
The combination and unification to larger groups works like this: periodically each leader sends messages to every other node asking whether that node is a leader, and if other nodes reply that they are leaders, the node pauses for a time inversely proportional to its priority, and then tries to invite the other leaders to join the group. Nodes with lower priority defer sending out their invitations for a longer period in order to prevent all group coordinators from sending out invitations at once. A leader which receives an invitation from a node with higher priority (directly or indirectly) sends an accept message to the proposed leader of the group.
The stepwise unification of groups and fragments in the "Invitation Election Algorithm" is very similar to the GHS algorithm from Gallager, Humblet and Spira. The GHS algorithm is a Distributed Algorithm for finding a minimum weight spanning tree, see Distributed Graph Algorithm. During the computation of the GHS algorithm, initially the collection of fragments contains each node as a one-node fragment, and the fragments are step by step combined with other fragments (the lowest-weight outgoing edge is essential). The algorithm terminates when only one fragment or group remains.
Korach, Moran and Zaks compare these fragments or groups to kingdoms. The process of joining fragments or groups becomes then a unification of kingdoms. In their paper "Tight lower and upper bounds for a class of distributed algorithms for a complete network of processors" (1984) they describe an election algorithm where "a king is trying to increase his kingdom by sending messages towards other kings (possibly through their citizens), asking them to join, together with their kingdoms, his kingdom".
A,B,C (Afek and Gafni) and D,E,F (Singh)
Afek and Gafni (1985) presented a family or sequence of algorithms for the election problem in asynchronous complete networks. They described three algorithms named A, B and C, which differ in the capturing and elimination rules, i.e. in the way that candidates determine their level and in the rules candidates use to eliminate each other. The central element is a variable "level" which is used to estimate the number of nodes the candidates have already captured.
In algorithm A, the level of a candidate is the number of nodes it has captured, whereas in algorithm B the level is the number of candidates it has killed. According to Afek and Gafni (1985), algorithm A achieves a better time complexity while algorithm B achieves a better message complexity. In algorithm C, candidates use a combination of algorithm A and B to attain the time complexity of A (which is linear or O(n)) and message complexity of B.
The algorithm or protocols A, B and C work roughly like this: candidate nodes try to capture other nodes in a sequential manner by sending capture messages on the incident edges one at a time. The goal is to capture all nodes, and a candidate that is successful in capturing all other nodes is elected the leader (this is not necessary the node with the highest ID, as we will see later, only the node with the most captured nodes or killed candidates). A candidate i sends its identity and a variable, level_i, in the capture message to contest with other nodes (level_i is the number of nodes which i has captured or the number of other candidates it has killed so far). If a capture message from i reaches a node j which has not yet been captured, and (level_i, i) >= (level_j, j) (comparison in a lexicographical order) then i captures j, otherwise i is killed. If j is a captured node, then i has to kill j's owner before claiming j. If i is finally successful in capturing and has (if required) killed j's owner, then it increments level_i and proceeds with its conquest by sending a capture message to another node.
These algorithms are early bird algorithms (named after the proverb "the early bird catches the worm"). Normally in elections the node with the highest or lowest ID is elected. In the asynchronous algorithms A, B and C the node with the highest ID might be "killed." If the level of a candidate is the total number of killed candidates, it is possible that the node or process with the highest ID is killed if it has slow connections and if its messages arrive very late - since it is an asynchronous network, the messages may have an arbitrary delay. Other nodes with lower ID but faster connections may have already a higher level because they have killed or captured more nodes earlier. This implies that the node with the highest ID does not always win the election, rather the node with the fastest connections. It is in fact impossible to predict the winner at all, because usually some kind of "race condition" is involved, where the result shows critical dependence on the relative timing of events.
Gurdip Singh (1992) proposed additional algorithms named D, E and F.
Election and Mutual Exlcusion
As Garcia-Molina says, electing a coordinator is similar to the mutual exclusion of a processes if there are no communication failures, because "we can think of being coordinator as having entered a special critical region" (*). He argues that "in the election, the nodes (i.e. processes) compete with each other so that only one node enters the critical region and becomes coordinator".
Yet there are also major differences to the problem of mutual exclusion. Garcia-Molina lists fairness, failure and information (*). In mutual exclusion fairness is important: every node or process should eventually be able to enter the critical section or region. In election problems, the coordinator has no need to let other nodes become coordinator. It does not matter if every node has an equal chance of becoming a leader, as long as there is a leader that has not crashed or failed. Mutual exclusion algorithms usually do not consider the possibility that a process in the critical section is subject to failure, whereas in election protocols coordinator failure is an important problem. An new coordinator must also send information messages about the results of the election to all nodes, but in mutual exclusion, the nodes don't care which node is currently in the critical section.
Election and Wave Algorithms
Wave algorithms and heart beat algorithms can be used with a slight extension to perform an election as well, because they can be used in general to spread and collect information. If all nodes have a unique identification numner or ID, simply the node with the highest or lowest ID must be selected. The corresponding Heart Beat or systolic algorithm is named "FloodMax". The "FloodMax" algorithm works like this: every process maintains a record of the maximal ID seen so far, and in each round, this maximal ID is propagated to all neighbors. If the number of rounds matches the diameter of the network, a node is elected as the new leader if the maximal ID agrees with the node's own ID.
A wave algorithm can be used an election algorithm by adding an additional information phase or additional initiators. The normal echo-algorithm for example has two phases, an expansion or exploration phase and a contraction or echo phase. The first phase can be used to spread information in the system, the second to collect information from the system. The wave algorithm can be used for an election if it is used to collect information about the node with the highest identification number or ID, and if an additional information phase is added where the system is informed about the winner (i.e. the new leader or coordinator). Unfortunately, the echo-algorithm does not work if only node fails or crashes, because it will hang in the second phase.
If we add additional initiators, we can use the principle of wave extinction. Each nodes initiates a wave, and only the wave with the highest ID survives and extinguishes all other waves. The principles of wave-extinction applied to a ring topology is known as Chang-Roberts algorithms. Gerard Tel explains in his book "Distributed Algorithms" how election and wave algorithms are connected with each other (chapter 7.3, page 246): "An algorithm for leader election can be obtained from an arbitrary centralized wave algorithm by the application of a construction called extinction. In the resulting election algorithm each initiator starts a separate wave; the messages of the wave initiated by process p must all be tagged with p in order to distinguish them from the messages of different waves. The algorithm ensures that, no matter how many waves are started, only one wave will run to a decision, namely, the wave of the greatest or smallest initiator. All other waves will be aborted before a decision can take place."
Articles
(*) Hector Garcia-Molina, Elections in a Distributed Computing System, IEEE Transactions on Computers, Vol. C-31, No. 1, January (1982) 48-59
Ephraim Korach, Shlomo Moran, and Shmuel Zaks, Tight lower and upper bounds for a class of distributed algorithms for a complete network of processors, In Proc. of 3rd ACM PODC Symposium on Principles of Distributed Computing, Vancouver (1984) 199-207
Time and Message Bounds of Election in Synchronous and Asynchronous Complete Networks, Yehuda Afek, Eli Gafni, In Proc. of 4th ACM PODC Symposium on the Principles of Distributed Computing, Minaki, Canada (1985) 186-195
Leader Election in Complete Networks, Gurdip Singh, In Proc. of 11th ACM PODC Symposium on the Principles of Distributed Computing, Vancouver, Canada (1992) 179-190
Books
Nancy A. Lynch, Distributed Algorithms, Morgan Kaufmann 1996, ISBN 1558603484
Gerard Tel, Introduction to Distributed Algorithms, Cambridge University Press, 2nd edition, 2001, ISBN 0521794838
