Authors
Greg N Frederickson, Nancy A Lynch
Publication date
1987/1/1
Journal
Journal of the ACM (JACM)
Volume
34
Issue
1
Pages
98-115
Publisher
ACM
Description
The problem of electing a leader in a synchronous ring of 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 O(n) messages in the worst case. On the other hand, any algorithm that is restricted to use only comparisons of IDs requires Ω(n log n) messages in the worst case. Alternatively, if the number of rounds is required to be bounded by some 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 Ω(n log n) messages in the worst case.
Total citations
Scholar articles
GN Frederickson, NA Lynch - Journal of the ACM (JACM), 1987