Access Restriction

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

   Open content in new tab
Source: ACM Digital Library