US4584643A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Decentralized synchronization of clocks
Assignee: International Business Machines Corp
•
Filing: 1983-12-09
•
Granted: 1986-04-22
•
Expires: 2003-12-09
Abstract
Abstract A method for synchronizing clocks in a distributed computing system in the presence of faults. The condition to be renewed guarantees that all clocks of correct processors never deviate by more than some maximum amount. This condition is achieved by periodically resynchronizing the clocks so that the correct clocks do not deviate by more than some minimum deviation. In the process of resynchronization, a correct clock is never adjusted by more than a maximum amount during a period and it is never set back. The method requires ascertaining whether a valid time value message has been received within a specified period. A message is valid if it was received within an interval predetermined as a function of the number of signatures from other processors appending the message. If the valid message has not been received within the current period, then the local processor originates and broadcasts to all processors exactly one time value message and appends thereto its unforgeable signature. On the other hand if a valid message has been received, then the local processor appends its unforgeable signature to the message and passes exactly the one message on by broadcasting to all processors. As part of the protocol involving broadcasting of a message, each processor resets the time for expected resynchronization and updates its local clock.
Inventors
- 👤 Joseph Y. Halpern
- 👤 Barbara B. Simons
- 👤 Hovey R. Strong
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-28 08:04
CPC Classifications
G; G06; G06F; G06F1/00; G06F1/04; G06F1/14
Claims Analysis
Total Claims: 13
Claim 1
Independent Claim
207 words
A decentralized method for periodically synchronizing local clocks in a network of counterpart message sending and receiving CPU's, both the drift rate between the clocks and the network message transit and processing times between sending and receiving CPU's being bounded, comprising the steps at each CPU in the network of: (a) ascertaining whether a time value message has been received at the CPU within a current synchronizing interval; (b) if said message has not been received within said interval, then originating and broadcasting to all network connected CPU's exactly one time value message, appending thereto its unforgeable signature, resetting the expected time of next resynchronization, and updating its local clock; (c) ascertaining whether any locally received message is valid according to whether said message was received within a period determined as a function of the number of signatures appending the message; and (d) if said received message is valid, then appending thereto the unforgeable signature of the CPU to the received message, and passing exactly the one received message on by broadcasting to all network connected CPU's, resetting the expected time of next resynchronization, and updating its local clock; otherwise, returning the CPU to a wait state in the event that the received message is not valid.
Claim 2
Dependent Claim
207 words
A decentralized method for periodically synchronizing local clocks in a network of counterpart message sending and receiving CPU's, both the drift rate between the clocks and the network message transit and processing times between sending and receiving CPU's being bounded, comprising the steps at each CPU in the network of: (a) ascertaining whether a time value message has been received at the CPU within a current synchronizing interval; (b) if said message has not been received within said interval, then originating and broadcasting to all network connected CPU's exactly one time value message, appending thereto its unforgeable signature, resetting the expected time of next resynchronization, and updating its local clock; (c) ascertaining whether any locally received message is valid according to whether said message was received within a period determined as a function of the number of signatures appending the message; and (d) if said received message is valid, then appending thereto the unforgeable signature of the CPU to the received message, and passing exactly the one received message on by broadcasting to all network connected CPU's, resetting the expected time of next resynchronization, and updating its local clock; otherwise, returning the CPU to a wait state in the event that the received message is not valid.
Claim 3
Dependent Claim
22 words
A method according to claim 1, wherein the network is tolerant of any number of faults which do not disconnect the network.
Claim 4
Dependent Claim
52 words
A method according to claim 1, wherein during the broadcasting of a time value message further includes the steps of creating new clocks and after a period of overlapping existence discarding old clocks, the difference between the new clock and the old clock readings being positive and never exceeding a fixed amount.
Claim 5
Dependent Claim
27 words
A method according to claim 1, wherein for a network of n nodes, the number of messages required to reach synchronization is at most n 2 .
Claim 6
Dependent Claim
31 words
A method according to claim 1, wherein at any given real time, the difference between the times of the local clocks of any two counterpart CPU's is bounded by a constant.
Claim 7
Dependent Claim
242 words
A decentralized method for periodically synchronizing local clocks in a network of counterpart communicating processors, both the drift rate (ρ) between the clocks and the network message transit and processing times (tdel) between sending and receiving processors being bounded, comprising the steps at each processor of: (a) ascertaining whether a time value message has been received within a current synchronizing interval; (b) if said message has not been received within said interval, then originating and broadcasting to all processors exactly one time value message ("the time is t"), appending to said message its unforgeable signature, resetting the expected time of next resynchronization, and updating its local clock; (c) ascertaining whether a received message is valid according as to whether said message was received within the current synchronizing interval, said validity being determined as a function of the number of signatures appending the message, all messages generated from any first to any second processor being numbered consecutively such that a second processor receiving a message numbered k ignores said message until all messages having a numerical value k have been received; and (d) if said received message is valid, then appending thereto the unforgeable signature of the processor and passing exactly the one message on by broadcasting to all processors, resetting the expected time of next resynchronization (et) according to the received message and updating its local clocks; otherwise, if the received message is not valid, the processor returns to a wait state.
Claim 8
Dependent Claim
242 words
A decentralized method for periodically synchronizing local clocks in a network of counterpart communicating processors, both the drift rate (ρ) between the clocks and the network message transit and processing times (tdel) between sending and receiving processors being bounded, comprising the steps at each processor of: (a) ascertaining whether a time value message has been received within a current synchronizing interval; (b) if said message has not been received within said interval, then originating and broadcasting to all processors exactly one time value message ("the time is t"), appending to said message its unforgeable signature, resetting the expected time of next resynchronization, and updating its local clock; (c) ascertaining whether a received message is valid according as to whether said message was received within the current synchronizing interval, said validity being determined as a function of the number of signatures appending the message, all messages generated from any first to any second processor being numbered consecutively such that a second processor receiving a message numbered k ignores said message until all messages having a numerical value k have been received; and (d) if said received message is valid, then appending thereto the unforgeable signature of the processor and passing exactly the one message on by broadcasting to all processors, resetting the expected time of next resynchronization (et) according to the received message and updating its local clocks; otherwise, if the received message is not valid, the processor returns to a wait state.
Claim 9
Dependent Claim
34 words
A method according to claim 6, wherein if after the occurrence of the duration of tdel a message with a number less than k has not been received, then message number k is ignored.
Claim 10
Dependent Claim
48 words
A method according to claim 6, wherein if a message has not been received within said interval, the step of resetting local clocks includes the steps of incrementing a current interval counter curint:=curint+1, and resetting the next scheduled time of synchronization et:=et+per, where per designates the synchronization period.
Claim 11
Dependent Claim
58 words
A method according to claim 6, wherein the step of ascertaining whether a received message saying "the time is t" is valid includes the steps of testing whether t=et and whether (t-s*dmax)<c, where s is the number of unforgeable signatures appending the received message, dmax is the maximum deviation of clocks, and c is the correct clock time.
Claim 12
Dependent Claim
57 words
A method according to claim 6, wherein in a completely connected network of processors with no link failures, said network being characterized by dmax=tdel+ρper, where ρ is the maximum rate of drift between correct clocks, per is the synchronization period, tdel is the worst case transmission and processing delay and dmax is the maximum deviation of clocks.
Claim 13
Dependent Claim
18 words
A method according to claim 6, wherein each correct processor sends n synchronization messages during each synchronization interval.
References Cited (Backward Citations)
US3400371A
Cited
US3602900A
Cited
US3761884A
Cited
US3940743A
Cited
US4021784A
Cited
US4223380A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1989-04-21 | 1989-10-21 | 1990-04-22 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1993-04-21 | 1993-10-21 | 1994-04-22 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1997-04-21 | 1997-10-21 | 1998-04-22 | $7700.00 | Window Closed / Lapsed |