Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

The computational capabilities of a system of n indistinguishable (anonymous) processors arranged on a ring in the synchronous and asynchronous models of distributed computation are analyzed. A precise characterization of the functions that can be computed in this setting is given. It is shown that any of these functions can be computed in O(n2) messages in the asynchronous model. This is also proved to be a lower bound for such elementary functions as AND, SUM, and Orientation. In the synchronous model any computable function can be computed in O(n log n) messages. A ring can be oriented and start synchronized within the same bounds. The main contribution of this paper is a new technique for proving lower bounds in the synchronous model. With this technique tight lower bounds of &thgr;(n log n) (for particular n) are proved for XOR, SUM, Orientation, and Start Synchronization. The technique is based on a string-producing mechanism from formal language theory, first introduced by Thue to study square-free words. Two methods for generalizing the synchronous lower bounds to arbitrary ring sizes are presented.

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: H. Attiya , Y. Mansour, Language complexity on the synchronous anonymous ring, Theoretical Computer Science, v.53 n.2-3, p.169-185, Aug. 1987 [doi>10.1016/0304-3975(87)90062-4]
• 3: ATTIYA, H., SNIR, M., AND WARMUTH, M. Computing on an anonymous ring. Tech. Rep. UCSC- CRL-85-3. Computer Research Laboratory, Univ. of California, Santa Cruz, Santa Cruz, Calif., Nov. 1985.
• 4: BURNS, J.E. A formal model for message passing systems. Tech. Rep. 9 l, Computer Science Dept., Indiana Univ., Bloomington, Ind., 1980.
• 5: DOLEV, D., KLAWE, M., AND RODEH, M. An O(n log n) unidirectional distributed algorithm for extrema-finding in a circle. J. Algorithms 3, 3 (Sept. 1982), 245-260.
• 6: EHRENFEUCHT, A., LEE, K. P., AND ROZENBERG, G. Subword complexity of various classes of deterministic developmental languages without interactions. Theoret. Comput. Sci. I (1975), 59-75.
• 7: Greg N. Frederickson , Nancy A. Lynch, Electing a leader in a synchronous ring, Journal of the ACM (JACM), v.34 n.1, p.98-115, Jan. 1987 [doi>10.1145/7531.7919]
• 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: ITAI, A. The circular extrema problem with nondistinct numbers. Unpublished manuscript.
• 10: MORAN, S., AND WARMUTH, M. Gap theorems for distributed computations. Tech. Rep. UCSC- CRL-86-1, Computer Research Laboratory, Univ. of California, Santa Cruz, Santa Cruz, Calif., Jan. 1986.
• 11: 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]
• 12: 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]
• 13: Grzegorz Rozenberg , Arto Salomaa, Mathematical Theory of L Systems, Academic Press, Inc., Orlando, FL, 1980
• 14: THUE, A. l}ber Unendliche Zeichenreihen. In Videnskapsselskapets Skrifter. I. Mat.-naturv. Klasse. Kristiania, Norway, 1906, pp. 1-20.
• 15: THUE, A. Uber die Gegenseitige Lage Gleicher Teile Gewisser Zeichenreihen. Videnskapsselskapets Skrifter. I. Mat.-naturv. Klasse. Kristiania, Norway, 1912, pp. 1-67.

INDEX TERMS

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

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

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Relations between models
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency
      F.1.3 Complexity Measures and Classes
          Subjects: Relations among complexity measures
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.2 Grammars and Other Rewriting Systems
          Subjects: Parallel rewriting systems (e.g., developmental systems, L-systems)

General Terms:
Algorithms, Theory, Verification