Are Wait-free Algorithms Fast?
The time complexity of wait-free algorithms in "normal" executions, where no failures occure and processes operate at approximately the same speed, is considered. A lower bound of log n on the time complexity of any wait-free algorithm that achieves approximate agreements among n processes...
| Main Authors: | , , |
|---|---|
| Published: |
2023
|
| Online Access: | https://hdl.handle.net/1721.1/149170 |
| _version_ | 1826207650524692480 |
|---|---|
| author | Attiya, Hagit Lynch, Nancy A. Shavit, Nir |
| author_facet | Attiya, Hagit Lynch, Nancy A. Shavit, Nir |
| author_sort | Attiya, Hagit |
| collection | MIT |
| description | The time complexity of wait-free algorithms in "normal" executions, where no failures occure and processes operate at approximately the same speed, is considered. A lower bound of log n on the time complexity of any wait-free algorithm that achieves approximate agreements among n processes is proved. In contrast, there exists a non-wait-free algorithm that solves this problem in constant time. This implies an Ω(log n) time separation between the wait-free and non-wait-free computation models. On the positive side, we present an O(log n) time wait-free approximate agreement algorithm; the complexity of this algorithm is within a small constant of the lower bound. |
| first_indexed | 2024-09-23T13:52:49Z |
| id | mit-1721.1/149170 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T13:52:49Z |
| publishDate | 2023 |
| record_format | dspace |
| spelling | mit-1721.1/1491702023-03-30T03:35:18Z Are Wait-free Algorithms Fast? Attiya, Hagit Lynch, Nancy A. Shavit, Nir The time complexity of wait-free algorithms in "normal" executions, where no failures occure and processes operate at approximately the same speed, is considered. A lower bound of log n on the time complexity of any wait-free algorithm that achieves approximate agreements among n processes is proved. In contrast, there exists a non-wait-free algorithm that solves this problem in constant time. This implies an Ω(log n) time separation between the wait-free and non-wait-free computation models. On the positive side, we present an O(log n) time wait-free approximate agreement algorithm; the complexity of this algorithm is within a small constant of the lower bound. 2023-03-29T14:34:34Z 2023-03-29T14:34:34Z 1991-03 https://hdl.handle.net/1721.1/149170 23361408 MIT-LCS-TM-442 application/pdf |
| spellingShingle | Attiya, Hagit Lynch, Nancy A. Shavit, Nir Are Wait-free Algorithms Fast? |
| title | Are Wait-free Algorithms Fast? |
| title_full | Are Wait-free Algorithms Fast? |
| title_fullStr | Are Wait-free Algorithms Fast? |
| title_full_unstemmed | Are Wait-free Algorithms Fast? |
| title_short | Are Wait-free Algorithms Fast? |
| title_sort | are wait free algorithms fast |
| url | https://hdl.handle.net/1721.1/149170 |
| work_keys_str_mv | AT attiyahagit arewaitfreealgorithmsfast AT lynchnancya arewaitfreealgorithmsfast AT shavitnir arewaitfreealgorithmsfast |