Tight lower bounds for probabilistic solitude verification on anonymous rings

ABSTRACT

A model that captures communication on asynchronous unidirectional rings is formalized. Our model incorporates both probabilistic and nondeterministic features and is strictly more powerful than a purely probabilistic model. Using this model, a collection of tools are developed that facilitate studying lower bounds on the expected communication complexity of Monte Carlo algorithms for language recognition problems on anonymous asynchronous unidirectional rings. The tools are used to establish tight lower bounds on the expected bit complexity of the Solitude Verification problem that asymptotically match upper bounds for this problem. The bounds demonstrate that, for this problem, the expected bit complexity depends subtly on the processors' knowledge of the size of the ring and on whether or not processor-detectable termination is required.

REFERENCES

• 1: ~ABRAHAMSON, K., ADLER. A., GEBHART, R., HIGHAM, L., AND KIRKPATRICK, D. 1986. The bit ~complexity of probabilistic leader election on a unidirectional ring. In Distributed ~4lj~,o- ~rithms on Graphs, Carleton University Press, pp. 1 12. Proc. 1st International Workshop on ~Distributed Algorithms.
• 2: K. Abrahamson , A. Adler , R. Gelbart , L. Higham , D. Kirkpatrick, The bit complexity of randomized leader election on a ring, SIAM Journal on Computing, v.18 n.1, p.12-29, Feb. 1989 [doi>10.1137/0218002]
• 3: ~ABRAHAMSON, K., ADLER, A., HIGHAM, L., AND KIRKPATRICK, D. 1989b. Randomized function ~evaluation on a ring. Dist. Comput., 3, 3, 107 t17.
• 4: Karl Abrahamson , Andrew Adler , Lisa Higham , David G. Kirkpatrick, Optimal Algorithms for Probalistic Solitude Detection On Anomymous Rings, University of British Columbia, Vancouver, BC, Canada, 1990
• 5: ~ABRAHAMSON, K., ADLER, A., H1GHAM~ L., AND KIRKPATRICK, D. 1991. Probabilistic leader ~election on rings of known size. In Workshop on Algorzthms and Data Strttctures. Lecture ~Notes in Computer Science, Vol. 519. Springer-Verlag, New York, pp. 481 495.
• 6: Yehuda Afek, Distributed algorithms for election in unidirectional and complete networks (traversal, synchronous, leader, asynchronous, complexity), 1985
• 7: Yehuda Afek , Yossi Matias, Elections in anonymous networks, University of Maryland at College Park, College Park, MD, 1991
• 8: 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]
• 9: APOSTOL, T. M. 1976. Introduction to Analytic Number Theory. Springer-Verlag, New York.
• 10: ATI'IYA, H., SANTORO, N., AND ZAKS, S. 1987. From rings to complete graphs--t~(n log n) to ~0(n) distributed leader election. Tech. Rep. SCS-TR-109. Carleton Univ.
• 11: Hagit Attiya , Marc Snir, Better computing on the anonymous ring, Journal of Algorithms, v.12 n.2, p.204-238, June 1991 [doi>10.1016/0196-6774(91)90002-G]
• 12: Hagit Attiya , Marc Snir , Manfred K. Warmuth, Computing on an anonymous ring, Journal of the ACM (JACM), v.35 n.4, p.845-875, Oct. 1988 [doi>10.1145/48014.48247]
• 13: Hans L. Bodlaender, A better lower bound for distributed leader finding in bidirectional, asynchronous rings of processors, Information Processing Letters, v.27 n.6, p.287-290, May 13, 1988 [doi>10.1016/0020-0190(88)90215-3 ]
• 14: ~BODLAENDER, H. L. 1988b. New lower bound techniques for distributed leader finding and other ~problems on rings of processors. Tech. Rep. RUU-CS-88-18. Rijksunlversiteit Utrecht, Thc ~Netherlands.
• 15: ~DOLEV, D., KLAWE, M., AND RODEH, M. 1982. An O(n log n) unidirectional distributed algo- ~rithm for extrema finding in a circle. J. Algor. 3, 3, 245 260
• 16: Pavol Duris , Zvi Galil, Two lower bounds in asynchronous distributed computation, Journal of Computer and System Sciences, v.42 n.3, p.254-266, June 1991 [doi>10.1016/0022-0000(91)90002-M]
• 17: Greg N. Frederickson , Nancy A. Lynch, The impact of synchronous communication on the problem of electing a leader in a ring, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.493-503, December 1984 [doi>10.1145/800057.808719]
• 18: ~ITAI, A., AND RODEIt, M. 1981. Symmetry breaking in distributed networks. In Proceedings of the ~22nd Annual ,~vmpostum on Foundations o} Computer Sctence. IEEE, New York, pp. ~150-158.
• 19: ~ACHL, J. 1985. A lower bound for probabdlstic distributed algorithms. Tech. Rep. CS-85-25. ~Univ. of Waterloo, Waterloo, Ontario, Canada.
• 20: Jan K. Pachl , E. Korach , D. Rotem, Lower Bounds for Distributed Maximum-Finding Algorithms, Journal of the ACM (JACM), v.31 n.4, p.905-918, Oct. 1984 [doi>10.1145/1634.1889]
• 21: Paul Walton Purdom, Jr. , Cynthia A. Brown, The analysis of algorithms, Holt, Rinehart & Winston, Austin, TX, 1985
• 22: 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]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Probabilistic computation

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Distributed networks; Network communications

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

General Terms:
Algorithms, Theory

Keywords:
Leader Election, Solitude Verification, anonymous ring, asynchronous unidirectional ring, bit complexity, lower bounds, nondeterminism