Average Execution Time Analysis of a Self-stabilizing Leader Election Algorithm
- 1 January 2007
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1-7
Abstract
This paper deals with the self-stabilizing leader election algorithm of Xu and Srimani that finds a leader in a tree graph. The worst case execution time for this algorithm is O(N4), where N is the number of nodes in the tree. We show that the average execution time for this algorithm, assuming two different scenarios, is much lower than O(N4). In the first scenario, the algorithm assumes a equiprobable daemon and it only privileges a single node at a time. The average execution time for this case is O(N2). For the second case, the algorithm can privilege multiple nodes at a time. We eliminate the daemon from this algorithm by making random choices to avoid interference between neighbor nodes. The execution time for this case is O(N). We also show that for specific tree graphs, these results reduce even more.Keywords
This publication has 7 references indexed in Scilit:
- SELF-STABILIZING ANONYMOUS LEADER ELECTION IN A TREEInternational Journal of Foundations of Computer Science, 2006
- Uniform dynamic self-stabilizing leader electionIEEE Transactions on Parallel and Distributed Systems, 1997
- An exercise in fault-containment: Self-stabilizing leader electionInformation Processing Letters, 1996
- A Self-Stabilizing Leader Election Algorithm for Tree GraphsJournal of Parallel and Distributed Computing, 1996
- Leader election in uniform ringsACM Transactions on Programming Languages and Systems, 1993
- Self-stabilizationACM Computing Surveys, 1993
- Self-stabilizing systems in spite of distributed controlCommunications of the ACM, 1974