Concurrent and Distributed Computing in Java

Chapter 13

Leader Election

13.1 Introduction

Many distributed systems superimpose a logical ring topology on the underlying network to execute control functions. An important control function is that of electing a leader process. The leader can serve as a coordinator for centralized algorithms for problems such as mutual exclusion. Electing a leader in a ring can also be viewed as the problem of breaking symmetry in a system. For example, once a deadlock is detected in the form of a cycle, we may wish to remove one of the nodes in the cycle to remove the deadlock. This can be achieved by electing the leader.

We abstract the leader election problem using the interface Election shown below.

public interface Election extends MsgHandler {      void startElection ();      int getLeader ();//blocks till the leader is known}

Any implementation of Election should provide the method startElection, which is invoked by one or more processes in the system. The method getLeader returns the identity of the leader. If the identity of the leader is not known, then this method blocks until the leader is elected.

The leader election problem is similar to the mutual exclusion problem discussed in Chapter 8. In both problems, we are interested in choosing one of the processes as a privileged process. Coordinator-based or token-based solutions for mutual exclusion are not applicable for the leader election problem, because deciding which process can serve as the coordinator or has the token is precisely ...