Yet Another Modular Technique for Efficient Leader Election
by Stefan Dobrev and Peter Ruzicka

Abstract:

   In this paper we present a general and still flexible modular technique
for the design of efficient leader election algorithms in N-node networks.
Our approach can be viewed as a generalization of the previous method
introduced by Korach, Kutten and Moran [KKM90].
We show how well-known O(N) message leader election algorithms in oriented
hypercubes and tori [Pet85, Mans97, Tel95a, Tel95b] can be derived by
our technique. This is in contrast with NlogN message lower bound for
the approach in [KKM90].
   Moreover, our technique can be used to design new linear leader election
algorithms for unoriented butterflies and cube connected cycles, 
thus demonstrating its usefulness. This is an improvement over the 
O(NlogN) solutions obtained from the general leader election algorithm
[GHS83]. These results are of interest, since tori and corresponding 
chordal rings were the only known symmetric topologies for which linear leader
election algorithms in unoriented case were known [Mans97, Tel95a].