Preference-based leader election in distributed systems

In a distributed system, an algorithm used to select a distinguished node or leader to coordinate some activity in the system is known as a leader election algorithm. While traditional approaches to leader election, based on node ID numbers, are of considerable theoretical interest, we believe that these approaches are not very practical. A leader in a distributed system provides some important service to the system. Therefore, it would be desirable to choose as leader a node that can render this service most efficiently. It is clear that a node with the largest ID will not necessarily make a good leader. In this thesis, we propose and examine socially-inspired leader election schemes that attempt to locate the leader at a good node (from a performance standpoint) in the system. We assume that each node in the system uses locally available information to vote for the various candidates (potential leaders) on the basis of the performance level it would realize under each of them. These votes are combined using an election scheme to determine the elected leader. We present twelve different election schemes and examine the quality of the elected leader in three different system models. We show (via both analysis and simulation) that six of the election schemes elect the optimal leader with a high probability. Finally, efficient algorithms to implement the leader election schemes are developed. We show that most of the election schemes (ten out of the twelve) require at most $O$($n$) messages. The other two schemes require $O$($n\sp2$) messages