A note on leader election in directed split-stars and directed alternating group graphs

Abstract

A leader node is defined to be any node of the network unambiguously identified by some characteristics. In this paper, we first present a distributed algorithm for finding a leader node of a directed split-star. Moreover, an efficient self-stabilizing leader election algorithm that converges with linear rounds is proposed for directed split-stars. Actually, the distributed algorithm and the self-stabilizing algorithm are also applicable to the problem of directed alternating group graphs. As far as we know, no self-stabilizing leader election algorithm was known for the two graphs.

Keywords:

• leader election problem
• anonymous networks
• split-stars
• alternating group graphs
• self-stabilizing algorithms

2000 AMS Subject Classifications :

• 05C20
• 05C69
• 05C78
• 05C85

Acknowledgements

The author wishes to thank the anonymous referees for their comments and suggestions. This research was partially supported by National Science Council under the Grant NSC97-2221-E-034-012-.