Premium
Leader election in oriented star graphs
Author(s) -
Shi Wei,
Bouabdallah A.,
Srimani Pradip K
Publication year - 2005
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20052
Subject(s) - star (game theory) , hypercube , computer science , leader election , theoretical computer science , time complexity , a* search algorithm , network planning and design , protocol (science) , algorithm , distributed computing , computer network , mathematics , parallel computing , medicine , mathematical analysis , alternative medicine , pathology
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. © 2005 Wiley Periodicals, Inc. NETWORKS, Vol. 45(2), 169–179 2005