Efficient leader election in asynchronous networks of the order three

Abstract

Election is the problem of choosing a unique processor as the leader of a network. Such an election is very important in token regeneration in token ring, token bus, and FDDI networks, for concurrency control, to replace a malfunctioning or crashed central lock coordinator in a distributed data system, and to replace a primary site in a replicated file system. A network of processors is said to be of the order k if each of the processors is connected to exactly k processors. There are several known election algorithm for bounded degree asynchronous networks of the order two. In general, the algorithms for all these networks require a message complexity of 0(n log n) messages. There are also election algorithms for asynchronous mesh networks, which are of the order four, that require 0(n) messages. A natural question arises, therefore, if there exits any election algorithm with message complexity 0(n) for a network of the order three. In this thesis, we develop a network and an algorithm that answer the question in the affirmative.