Leader election in oriented star graphs
Leader election in a network plays an important role in the area of distributed algorithm design. Structural properties of the network as well as presence of direction on the edges of the network greatly affects the complexity of the leader election problem, which is primarily measured by the message complexity of the protocol. Our purpose in the present article is to adapt the existing distributed match making concepts to design a linear time leader election algorithm for star graphs. Star graphs have been extensively studied as an attractive alternative for the well-known hypercubes for network design. Linear election algorithms for oriented hypercubes is known; no such algorithm exists for oriented star graphs. (c) 2005 Wiley Periodicals, Inc.
leader election star graphs message complexity distributed match making tournament scheme