Leader election in complete networks

ABSTRACT

This paper presents protocols for leader election in complete networks. The protocols are message optimal and their time complexities are a significant improvement over currently known protocols for this problem. For asynchronous complete networks with sense of direction, we propose a protocol which requires O(N) messages and O(log N) time. For asynchronous complete network without sense of direction, we show that &Ohgr;(N/log N) is a lower bound on the time complexity of any message optimal election protocol and we present a family of protocols which requires O(Nk) messages and O(N/k) time, log N ≤ k ≤ N. Our results also improve the time complexity of several other related problems such as spanning tree construction, computing a global function, etc.

REFERENCES

• AFL83: Eshrat Arjomandi , Michael J. Fischer , Nancy A. Lynch, Efficiency of Synchronous Versus Asynchronous Distributed Systems, Journal of the ACM (JACM), v.30 n.3, p.449-456, July 1983 [doi>10.1145/2402.322387]
• AG85: Yehuda Afek , Eli Gafni, Time and message bounds for election in synchronous and asynchronous complete networks, Proceedings of the fourth annual ACM symposium on Principles of distributed computing, p.186-195, August 1985, Minaki, Ontario, Canada [doi>10.1145/323596.323613]
• ALSZ89: Attiya, H., Leeuwen, J., Santoro, N., and Zaks, S. Efficient elections in chordal ring networks. Algorithmica, 4, 1989.
• BKWZ87: R. Bar-Yehuda , S. Kutten , Y. Wolfstahl , S. Zaks, Making distributed spanning tree algorithms fault-resilient, 4th Annual Symposium on Theoretical Aspects of Computer Sciences on STACS 87, p.432-444, February 1987, Passau, Germany
• FL87: Frederickson, G. and Lynch, N. The impact of synchronous communication on the problem of electing a leader in a ring. In Proceedings of ACM $ym. on Theory of Computing, 1987.
• KMZ84: E. Korach , S. Moran , S. Zaks, Tight lower and upper bounds for some distributed algorithms for a complete network of processors, Proceedings of the third annual ACM symposium on Principles of distributed computing, p.199-207, August 27-29, 1984, Vancouver, British Columbia, Canada [doi>10.1145/800222.806747]
• Lam78: Leslie Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, v.21 n.7, p.558-565, July 1978 [doi>10.1145/359545.359563]
• LMW86: M C Loui , T A Matsushita , D B West, Election in a complete network with a sense of direction, Information Processing Letters, v.22 n.4, p.185-187, April 1986 [doi>10.1016/0020-0190(86)90025-6]
• Si91: Singh, G. Efficient distributed aJgorithma for le~der election. In IEEE International Conference on Distributed Computing Systems, 1991.
• Si92: Singh, G. Upper and lower bounds for leader election in complete networks. In Technical Report 92-8, Kansas State University, 1992.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

General Terms:
Algorithms