Electing a Leader in a Synchronous Ring
We consider the problem of electing a leader in a synchronous ring of n processors. We obtain both positive and negative results. One the one hand, we show that if processor ID's are chosen from some countable set, then there is an alorithm which uses only O(n) messages in the worst case. On th...
| Main Authors: | , |
|---|---|
| Published: |
2023
|
| Online Access: | https://hdl.handle.net/1721.1/149087 |
| _version_ | 1826189974905552896 |
|---|---|
| author | Frederickson, Greg N. Lynch, Nancy A. |
| author_facet | Frederickson, Greg N. Lynch, Nancy A. |
| author_sort | Frederickson, Greg N. |
| collection | MIT |
| description | We consider the problem of electing a leader in a synchronous ring of n processors. We obtain both positive and negative results. One the one hand, we show that if processor ID's are chosen from some countable set, then there is an alorithm which uses only O(n) messages in the worst case. On the other hand, we obtain two lower bound results. If the algorithm is restructed to use only comparisons of ID's, then we obtain an Ω(n log n) lower bound for the number of messages required in the worst case. Alternatively, there is a (very fast-growing) function f with the following property. If the number of rounds is required to be bounded by some t in the worst case, and ID's are chosen from any set having at leas f(n,t) elements, then any algorithm requires Ω(n log n) messages in the worst case. |
| first_indexed | 2024-09-23T08:33:06Z |
| id | mit-1721.1/149087 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T08:33:06Z |
| publishDate | 2023 |
| record_format | dspace |
| spelling | mit-1721.1/1490872023-03-30T04:20:54Z Electing a Leader in a Synchronous Ring Frederickson, Greg N. Lynch, Nancy A. We consider the problem of electing a leader in a synchronous ring of n processors. We obtain both positive and negative results. One the one hand, we show that if processor ID's are chosen from some countable set, then there is an alorithm which uses only O(n) messages in the worst case. On the other hand, we obtain two lower bound results. If the algorithm is restructed to use only comparisons of ID's, then we obtain an Ω(n log n) lower bound for the number of messages required in the worst case. Alternatively, there is a (very fast-growing) function f with the following property. If the number of rounds is required to be bounded by some t in the worst case, and ID's are chosen from any set having at leas f(n,t) elements, then any algorithm requires Ω(n log n) messages in the worst case. 2023-03-29T14:26:03Z 2023-03-29T14:26:03Z 1985-07 https://hdl.handle.net/1721.1/149087 32609654 MIT-LCS-TM-277 application/pdf |
| spellingShingle | Frederickson, Greg N. Lynch, Nancy A. Electing a Leader in a Synchronous Ring |
| title | Electing a Leader in a Synchronous Ring |
| title_full | Electing a Leader in a Synchronous Ring |
| title_fullStr | Electing a Leader in a Synchronous Ring |
| title_full_unstemmed | Electing a Leader in a Synchronous Ring |
| title_short | Electing a Leader in a Synchronous Ring |
| title_sort | electing a leader in a synchronous ring |
| url | https://hdl.handle.net/1721.1/149087 |
| work_keys_str_mv | AT fredericksongregn electingaleaderinasynchronousring AT lynchnancya electingaleaderinasynchronousring |