7.7 Leader Election on an Anonymous Ring

Specifications of distributed algorithms refer to the entities that execute the algorithm as processes or processors . Such algorithms often specify an underlying processor model in terms of a finite-state machine. The processor models are classified by how the state transitions are driven ( synchrony ) and whether the processors are labeled.

In the synchronous processor model , the processors proceed in lock step and state transitions are clock-driven. In the asynchronous processor model , state transitions are message-driven. The receipt of a message on a communication link triggers a change in processor state. The processor may send messages to its neighbors, perform some computation, or halt as a result of the incoming message. On any given link between processors, the messages arrive in the order they were sent. The messages incur a finite, but unpredictable, transmission delay.

A system of communicating UNIX processes connected by pipes, such as the ring of Program 7.1, is an example of an asynchronous system. A massively parallel SIMD (single-instruction, multiple-data) machine such as the CM-2 is an example of a synchronous system.

A processor model must also specify whether the individual processors are labeled or whether they are indistinguishable. In an anonymous system , the processors have no distinguishing characteristic. In general, algorithms involving systems of anonymous processors or processes are more complex than the corresponding algorithms for systems of labeled ones.

The UNIX fork function creates a copy of the calling process. If the parent and child were completely identical, fork would not accomplish anything beyond the activities of a single process. In fact, UNIX distinguishes the parent and child by their process IDs, and fork returns different values to the parent and child so that each is aware of the other's identity. In other words, fork breaks the symmetry between parent and child by assigning different process IDs. Systems of UNIX processors are not anonymous because the processes can be labeled by their process IDs.

Symmetry-breaking is a general problem in distributed computing in which identical processes (or processors) must be distinguished to accomplish useful work. Assignment of exclusive access is an example of symmetry-breaking. One possible way of assigning mutual exclusion is to give preference to the process with the largest process ID. Usually, a more equitable method would be better. The voting algorithm of Section 7.6 assigns mutual exclusion to the process that has acquired it the fewest times in the past. The algorithm uses the process ID only in the case of ties.

Leader election is another example of a symmetry-breaking algorithm. Leader election algorithms are used in some networks to designate a particular processor to partition the network, regenerate tokens, or perform other operations. For example, what happens in a token-ring network if the processor holding the token crashes? When the crashed processor comes back up, it does not have a token and activity on the network comes to a standstill. One of the nonfaulty processors must take the initiative to generate another token. Who should decide which processor is in charge?

There are no deterministic algorithms for electing a leader on an anonymous ring. This section discusses the implementation of a probabilistic leader-election algorithm for an anonymous ring. The algorithm is an asynchronous version of the synchronous algorithm proposed by Itai and Roteh [58]. This is a probabilistic algorithm for leader election on an anonymous synchronous ring of size n . The synchronous version of the algorithm proceeds in phases. Each process keeps track of the number of active processes, m . These are the processes still competing for being chosen as the leader.

1. Phase zero

   1. Set local variable m to n .

   2. Set active to TRUE .

2. Phase k

   1. If active is TRUE ,

      1. Choose a random number, x , between 1 and m .

      2. If the number chosen was 1, send a one-bit message around the ring.

   2. Count the number of one-bit messages received in the next n-1 clock pulses as follows .

      1. If only one active process chose 1, the election is completed.

      2. If no active processes chose 1, go to the next phase with no change.

      3. If p processes chose 1, set m to p .

      4. If the process is active and it did not choose 1, set its local active to FALSE .

In summary, on each phase the active processes pick a random number between 1 and the number of active processes. Any process that picks a 1 is active on the next round. If no process picks a 1 on a given round, the active processes try again. The probability of a particular process picking a 1 increases as the number of active processes decreases. On average, the algorithm eliminates processes from contention at a rapid rate. Itai and Roteh showed that the expected number of phases needed to choose a leader on a ring of size n is less than e 2.718, independently of n .

Using the ring of Program 7.1, implement a simulation of this leader-election algorithm to estimate the probability distribution J(n,k) , which is the probability that it takes k phases to elect a leader on a ring of size n .

The implementation has to address two problems. The first problem is that the algorithm is specified for a synchronous ring, but the implementation is on an asynchronous ring. Asynchronous rings clock on the messages received (i.e., each time a process reads a message, it updates its clock). The processes must read messages at the correct point in the algorithm or they lose synchronization. Inactive processes must still write clock messages.

A second difficulty arises because the theoretical convergence of the algorithm relies on the processes having independent streams of random numbers. In practice, the processes use a pseudorandom-number generator with an appropriate seed. The processes are supposedly identical, but if they start with the same seed, the algorithm will not work. The implementation can cheat by using the process ID to generate a seed, but ultimately it should include a method of generating numbers based on the system clock or other system hardware. (The first few sections of Chapter 10 discuss library functions for accessing the system clock and timers.)