Optimal Clock Synchronization Under Different Delay Assumptions
The problem of achieving optimal clock synchronization in a communication network with arbitrary topology and perfect clocks (that do not drift) is studied. Clock synchronization algorithms are presented for a large family of delay assumptions. Our algorithms are modular and consist of three major c...
| Main Authors: | , , |
|---|---|
| Published: |
2023
|
| Online Access: | https://hdl.handle.net/1721.1/149223 |
| _version_ | 1826188684700942336 |
|---|---|
| author | Attiya, Hagit Herzberg, Amir Rajsbaum, Sergio |
| author_facet | Attiya, Hagit Herzberg, Amir Rajsbaum, Sergio |
| author_sort | Attiya, Hagit |
| collection | MIT |
| description | The problem of achieving optimal clock synchronization in a communication network with arbitrary topology and perfect clocks (that do not drift) is studied. Clock synchronization algorithms are presented for a large family of delay assumptions. Our algorithms are modular and consist of three major components. The first component holds for any type of delay assumptions; the second component holds for a large, natural family of local delay assumptions; the third component has to be tailored for each specific delay assumption. Optimal clock synchronization algorithms are derived for several types of delay assumptions by appropriately tuning the third component. The delay assumptions include lower and upper delay bounds, no bounds at all, and bounds on the difference of the delay in opposite directions. In addition, our model handles systems where some processors are connected by broadcast networks in which every message arrives to all processors at approximately the same time. A composition theorem allows combinations of different assumptions for different lins or even for the same link; such mixtures are common in practice. Our results acheive the best possible precision in each execution. This notion of optimality is stronger than the more common notion of worst case optimality. The new notion of optimality applied to systems where the worst case behavior of any clock synchronization algorithm is inherently unbounded. |
| first_indexed | 2024-09-23T08:03:08Z |
| id | mit-1721.1/149223 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T08:03:08Z |
| publishDate | 2023 |
| record_format | dspace |
| spelling | mit-1721.1/1492232023-03-30T04:25:00Z Optimal Clock Synchronization Under Different Delay Assumptions Attiya, Hagit Herzberg, Amir Rajsbaum, Sergio The problem of achieving optimal clock synchronization in a communication network with arbitrary topology and perfect clocks (that do not drift) is studied. Clock synchronization algorithms are presented for a large family of delay assumptions. Our algorithms are modular and consist of three major components. The first component holds for any type of delay assumptions; the second component holds for a large, natural family of local delay assumptions; the third component has to be tailored for each specific delay assumption. Optimal clock synchronization algorithms are derived for several types of delay assumptions by appropriately tuning the third component. The delay assumptions include lower and upper delay bounds, no bounds at all, and bounds on the difference of the delay in opposite directions. In addition, our model handles systems where some processors are connected by broadcast networks in which every message arrives to all processors at approximately the same time. A composition theorem allows combinations of different assumptions for different lins or even for the same link; such mixtures are common in practice. Our results acheive the best possible precision in each execution. This notion of optimality is stronger than the more common notion of worst case optimality. The new notion of optimality applied to systems where the worst case behavior of any clock synchronization algorithm is inherently unbounded. 2023-03-29T14:37:44Z 2023-03-29T14:37:44Z 1994-04 https://hdl.handle.net/1721.1/149223 MIT-LCS-TM-504 application/pdf |
| spellingShingle | Attiya, Hagit Herzberg, Amir Rajsbaum, Sergio Optimal Clock Synchronization Under Different Delay Assumptions |
| title | Optimal Clock Synchronization Under Different Delay Assumptions |
| title_full | Optimal Clock Synchronization Under Different Delay Assumptions |
| title_fullStr | Optimal Clock Synchronization Under Different Delay Assumptions |
| title_full_unstemmed | Optimal Clock Synchronization Under Different Delay Assumptions |
| title_short | Optimal Clock Synchronization Under Different Delay Assumptions |
| title_sort | optimal clock synchronization under different delay assumptions |
| url | https://hdl.handle.net/1721.1/149223 |
| work_keys_str_mv | AT attiyahagit optimalclocksynchronizationunderdifferentdelayassumptions AT herzbergamir optimalclocksynchronizationunderdifferentdelayassumptions AT rajsbaumsergio optimalclocksynchronizationunderdifferentdelayassumptions |