### Electing a leader in a synchronous ringElecting a leader in a synchronous ring

Access Restriction
Subscribed

 Author Frederickson, Greg N. ♦ Lynch, Nancy A. Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1987 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Abstract The problem of electing a leader in a synchronous ring of $\textit{n}$ processors is considered. Both positive and negative results are obtained. On the one hand, if processor IDS are chosen from some countable set, then there is an algorithm that uses only $\textit{O}(\textit{n})$ messages in the worst case. On the other hand, any algorithm that is restricted to use only comparisons of IDs requires $&OHgr;(\textit{n}$ log $\textit{n})$ messages in the worst case. Alternatively, if the number of rounds is required to be bounded by some $\textit{t}$ in the worst case, and IDs are chosen from any set having at least ƒ(n, t) elements, for a certain very fast-growing function ƒ, then any algorithm requires $&OHgr;(\textit{n}$ log $\textit{n})$ messages in the worst case. 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 1987-01-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 34 Issue Number 1 Page Count 18 Starting Page 98 Ending Page 115

#### Open content in new tab

Source: ACM Digital Library