### Computing on an anonymous ringComputing on an anonymous ring

Access Restriction
Subscribed

 Author Attiya, Hagit ♦ Snir, Marc ♦ Warmuth, Manfred K. Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1988 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Abstract The computational capabilities of a system of $\textit{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 $\textit{O}(\textit{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 $\textit{O}(\textit{n}$ log $\textit{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;(\textit{n}$ log $\textit{n})$ (for particular $\textit{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. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 1988-10-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 35 Issue Number 4 Page Count 31 Starting Page 845 Ending Page 875

#### Open content in new tab

Source: ACM Digital Library