Computing on an anonymous ring
Open Access
- 1 October 1988
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 35 (4) , 845-875
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 ( n 2 ) 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.Keywords
This publication has 9 references indexed in Scilit:
- Language complexity on the synchronous anonymous ringTheoretical Computer Science, 1987
- Electing a leader in a synchronous ringJournal of the ACM, 1987
- Lower Bounds for Distributed Maximum-Finding AlgorithmsJournal of the ACM, 1984
- An O ( n log n ) Unidirectional Algorithm for the Circular Extrema ProblemACM Transactions on Programming Languages and Systems, 1982
- An O(n log n) unidirectional distributed algorithm for extrema finding in a circleJournal of Algorithms, 1982
- Decentralized extrema-finding in circular configurations of processorsCommunications of the ACM, 1980
- Local and global properties in networks of processors (Extended Abstract)1980
- Subword complexities of various classes of deterministic developmental languages without interactionsTheoretical Computer Science, 1975
- The Mathematical Theory of L SystemsDAIMI Report Series, 1974