Average Execution Time Analysis of a Self-stabilizing Leader Election Algorithm

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(N⁴), 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(N⁴). 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(N²). 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.