A MODULAR TECHNIQUE FOR THE DESIGN OF EFFICIENT DISTRIBUTED LEADER FINDING ALGORITHMS1
by E. Korach, S. Kutten and S. Moran
Computer Science Department Technion, Israel Institute of Technology
Haifa, Israel 32000
ABSTRACT
A general, modular technique for designing efficient leader finding algorithms in distributed,
asynchronous networks is developed. This technique reduces the relatively complex problem of
efficient leader finding to a simpler problem of efficient serial traversing of the corresponding
network. The message complexity of the resulting leader finding algorithms is bounded by
( f (n) + n) (log2k + 1) [or ( f (m) + n) (log2k + 1)], where n is the number of nodes in the
network [m is the number of edges in the network], k is the number of nodes that start the
algorithm, and f (n) [ f (m)] is the message complexity of traversing the nodes [edges] of
the network. This technique does not require that the FIFO discipline is obeyed by
the links. The local memory needed for each node, besides the memory needed for the traversal
algorithm, is logarithmic in the maximal identity of a node in the network. This result
achieves in a unified way the best known upper bounds on the message complexity of
leader finding algorithms for circular, complete and general networks. It is also shown to
be applicable to other classes of networks, and in some cases the message complexity of the
resulted algorithms is better by a constant factor than that of previously known algorithms.