Hagit Attiya
Marc Snir
Manfred K. Warmuth
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 θ(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.
- 1 ANGLUIN, D. Local and global properties in networks of processors. In Proceedings of the 12th Annual ACM Symposium on Theory of Computing (Los Angeles, Calif., Apr. 28-30). ACM, New York, 1980, pp. 82-93. Google Scholar
- 2 ATTIYA, H., AND MANSOUR, Y. Language complexity on the synchronous anonymous ring. Theoret. Comput. Sci. 53 (1987), 169-185. Google Scholar
- 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.Google Scholar
- 4 BURNS, J.E. A formal model for message passing systems. Tech. Rep. 9 l, Computer Science Dept., Indiana Univ., Bloomington, Ind., 1980.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 7 FREDERICKSON, G. N., AND LYNCH, N.A. Electing a leader in a synchronous ring. J. ACM 34, l (Jan. 1987), 98-115. Google Scholar
- 8 HIRSHBERG, D. S., AND SINCLAIR, J.B. Decentralized extrema-finding in circular configurations of processors. Commun. ACM 23, 11 (Nov. 1980), 627-628. Google Scholar
- 9 ITAI, A. The circular extrema problem with nondistinct numbers. Unpublished manuscript.Google Scholar
- 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.Google Scholar
- 11 PACHL, J., KORACH, E., AND ROTEM, O. Lower bounds for distributed maximum-finding algorithms. J. ACM 31, 4 (Oct. 1984), 905-918. Google Scholar
- 12 PETERSON, G.L. An O(n lg n) unidirectional algorithm for the circular extrema problem. Trans. Program. Lang. Syst. 4, 4 (1982), 758-762. Google Scholar
- 13 ROZENBERG, G., AND SALOMAA, A. The Mathematical Theory of L Systems. Academic Press, Orlando, Fla., 1980. Google Scholar
- 14 THUE, A. l}ber Unendliche Zeichenreihen. In Videnskapsselskapets Skrifter. I. Mat.-naturv. Klasse. Kristiania, Norway, 1906, pp. 1-20.Google Scholar
- 15 THUE, A. Uber die Gegenseitige Lage Gleicher Teile Gewisser Zeichenreihen. Videnskapsselskapets Skrifter. I. Mat.-naturv. Klasse. Kristiania, Norway, 1912, pp. 1-67.Google Scholar
Index Terms
- Computing on an anonymous ring
Recommendations
On the time and the bit complexity of distributed randomised anonymous ring colouring
We present and analyse a very simple randomised distributed vertex colouring algorithm for ring graphs. Its time complexity is log"2n+o(logn) on average and 2log"2n+o(logn) with probability 1-o(n^-^1). Since each message contains one bit, we deduce the ...
Tight bounds for anonymous adopt-commit objects
SPAA '11: Proceedings of the twenty-third annual ACM symposium on Parallelism in algorithms and architecturesWe give matching upper and lower bounds of Θ(min(log m/log log m, n)) for the space and individual step complexity of a wait-free m-valued adopt-commit object implemented using multi-writer registers for n anonymous processes. While the upper bound is ...
Language complexity on the synchronous anonymous ring
A set of n nondistinct processors, organized as a ring and operating synchronously, have to compute a function of their initial values. Every computable function can be computed with O(n log n) messages, while some functions can be computed with as few ...
Comments