The impact of synchronous communication on the problem of electing a leader in a ring

ABSTRACT

We consider the problem of electing a leader in a synchronous ring of n processors. We obtain both positive and negative results. On the one hand, we show that if processor ID's are chosen from some countable set, then there is an algorithm which uses only O(n) messages in the worst case. On the other hand, we obtain two lower bound results: If the algorithm is restricted to use only comparisons of ID's, then we obtain an &Ohgr;(n log n) lower bound for the number of messages required in the worst case. Alternatively, there is a (very fast-growing) function f with the following property. If the number of rounds is required to be bounded by some t in the worst case, and ID's are chosen from any set having at least f(n,t) elements, then any algorithm requires &Ohgr; (n log n) messages in the worst case.

REFERENCES

• 1: Dana Angluin, Local and global properties in networks of processors (Extended Abstract), Proceedings of the twelfth annual ACM symposium on Theory of computing, p.82-93, April 28-30, 1980, Los Angeles, California, United States [doi>10.1145/800141.804655]
• 2: J. E. Burns, A formal model for message passing systems, TR-91, Indiana University (September 1980).
• 3: C. Berge, Graphs and Hypergraphs, Elsevier Science Ltd, 1985
• 4: Ernest Chang , Rosemary Roberts, An improved algorithm for decentralized extrema-finding in circular configurations of processes, Communications of the ACM, v.22 n.5, p.281-283, May 1979 [doi>10.1145/359104.359108]
• 5: D. Dolev, M. Klawe and M. Rodeh, An O (n log n) unidirectional distributed algorithm for extrema finding in a Circle, J. Algorithms 3,3 (September 1982) 245-260.
• 6: R. G. Gallager , P. A. Humblet , P. M. Spira, A Distributed Algorithm for Minimum-Weight Spanning Trees, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.1, p.66-77, Jan. 1983 [doi>10.1145/357195.357200]
• 7: E. Gafni, M. Loui, P. Tiwari, D. West and S. Zaks, Lower bounds on common knowledge in distributed algorithms (ABSTRACT).
• 8: D. S. Hirschberg , J. B. Sinclair, Decentralized extrema-finding in circular configurations of processors, Communications of the ACM, v.23 n.11, p.627-628, Nov. 1980 [doi>10.1145/359024.359029]
• 9: A. Itai and M. Rodeh,
• 10: G. LeLann, Distributed systems - toward a formal approach, Information Processing 77, North Holland, Amsterdam (1977) 155-160.
• 11: Gary L. Peterson, An O(nlog n) Unidirectional Algorithm for the Circular Extrema Problem, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.4, p.758-762, Oct. 1982 [doi>10.1145/69622.357194]
• 12: M. Snir, On parallel searching, Hebrew University of Jerusalem, Department of Computer Science, RR 83-21 (June 1983).
• 13: M. Snir, Personal communication (1983).
• 14: P. Vitanyi, Distributed elections Archimedean Ring of Processors, This Proceedings.
• 15: Andrew Chi-Chih Yao, Should Tables Be Sorted?, Journal of the ACM (JACM), v.28 n.3, p.615-628, July 1981 [doi>10.1145/322261.322274]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.5 Local and Wide-Area Networks
          Subjects: Token rings

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

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

General Terms:
Algorithms, Theory