A New Fault-tolerant Algorithm for Clock Sychronization
We describe a new fault-tolerant algorithm for solving a variant of Lamport's clock synchronization problem. The algorithm is designed for a system of distributed processes that communicate by sending messages. Each process has its own read only physical clock whose drift rate from real time is...
| Main Authors: | , |
|---|---|
| Published: |
2023
|
| Online Access: | https://hdl.handle.net/1721.1/149075 |
| _version_ | 1826214926929100800 |
|---|---|
| author | Lundelius, Jennifer Lynch, Nancy A. |
| author_facet | Lundelius, Jennifer Lynch, Nancy A. |
| author_sort | Lundelius, Jennifer |
| collection | MIT |
| description | We describe a new fault-tolerant algorithm for solving a variant of Lamport's clock synchronization problem. The algorithm is designed for a system of distributed processes that communicate by sending messages. Each process has its own read only physical clock whose drift rate from real time is very small. By adding a value to its physical clock time, the process obtains its local time. The algorithm solves the problem of maintaining closely synchornized local times, assuming that processes' local times are closely synchronized initially. The algorithm is able to tolerate the failure of just under a third of the participating processes. It maintains synchornization to within a small constant, whose magnitude depends upon the rate of clock drift, the message delivery time, and the initial closeness of synchronization. We also give a characterization of how far the clocks drift from real time. Reintegration of a repaired process can be accomlished using a slight modification of the basic algorithm. A similiar style algorithm can also be used to achieve synchronization initially. |
| first_indexed | 2024-09-23T16:12:37Z |
| id | mit-1721.1/149075 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T16:12:37Z |
| publishDate | 2023 |
| record_format | dspace |
| spelling | mit-1721.1/1490752023-03-30T03:06:43Z A New Fault-tolerant Algorithm for Clock Sychronization Lundelius, Jennifer Lynch, Nancy A. We describe a new fault-tolerant algorithm for solving a variant of Lamport's clock synchronization problem. The algorithm is designed for a system of distributed processes that communicate by sending messages. Each process has its own read only physical clock whose drift rate from real time is very small. By adding a value to its physical clock time, the process obtains its local time. The algorithm solves the problem of maintaining closely synchornized local times, assuming that processes' local times are closely synchronized initially. The algorithm is able to tolerate the failure of just under a third of the participating processes. It maintains synchornization to within a small constant, whose magnitude depends upon the rate of clock drift, the message delivery time, and the initial closeness of synchronization. We also give a characterization of how far the clocks drift from real time. Reintegration of a repaired process can be accomlished using a slight modification of the basic algorithm. A similiar style algorithm can also be used to achieve synchronization initially. 2023-03-29T14:24:57Z 2023-03-29T14:24:57Z 1984-07 https://hdl.handle.net/1721.1/149075 13567033 MIT-LCS-TM-265 application/pdf |
| spellingShingle | Lundelius, Jennifer Lynch, Nancy A. A New Fault-tolerant Algorithm for Clock Sychronization |
| title | A New Fault-tolerant Algorithm for Clock Sychronization |
| title_full | A New Fault-tolerant Algorithm for Clock Sychronization |
| title_fullStr | A New Fault-tolerant Algorithm for Clock Sychronization |
| title_full_unstemmed | A New Fault-tolerant Algorithm for Clock Sychronization |
| title_short | A New Fault-tolerant Algorithm for Clock Sychronization |
| title_sort | new fault tolerant algorithm for clock sychronization |
| url | https://hdl.handle.net/1721.1/149075 |
| work_keys_str_mv | AT lundeliusjennifer anewfaulttolerantalgorithmforclocksychronization AT lynchnancya anewfaulttolerantalgorithmforclocksychronization AT lundeliusjennifer newfaulttolerantalgorithmforclocksychronization AT lynchnancya newfaulttolerantalgorithmforclocksychronization |