US4531185A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Centralized synchronization of clocks
Assignee: International Business Machines Corp
•
Filing: 1983-08-31
•
Granted: 1985-07-23
•
Expires: 2003-08-31
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 that there is a previously agreed upon ordered list of all participants. At a specified time in the period, the first processor on the list attempts to synchronize all to its clock. The result of this is either a synchronization of all correct processors and their clocks to be within the desired tolerance or an agreement among all other correct processors that the first node on the list has failed. If the first fails, then the second tries and so on. Assuming at most f faulty components then one of the first f+1 attempts must succeed.
Inventors
- 👤 Joseph Y. Halpern
- 👤 Barbara B. Simons
- 👤 Hovey R. Strong
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-26 21:17
CPC Classifications
G; G06; G06F; G06F15/00; G06F15/16; G06F15/161; G06F1/00; G06F1/04; G06F1/14
Claims Analysis
Total Claims: 10
Claim 1
Independent Claim
122 words
A method for periodically synchronizing local clocks in a network of counterpart communicating CPU's (nodes), both the drift rate between the clocks and the network message transit and processing time being bounded, comprising the steps of: (a) forming an ordered list of node identities and replicating the list at each node; (b) broadcasting a time value with its unforgeable signature to all nodes including itself by the first node on the list; and (c) multiple message exchanging of the time value among the nodes wherein either a value convergence is secured or the next node on the list broadcasts another time value in the manner of the first and submits to a multiple message exchanging, the process repeating until synchronization is achieved.
Claim 2
Independent Claim
122 words
A method for periodically synchronizing local clocks in a network of counterpart communicating CPU's (nodes), both the drift rate between the clocks and the network message transit and processing time being bounded, comprising the steps of: (a) forming an ordered list of node identities and replicating the list at each node; (b) broadcasting a time value with its unforgeable signature to all nodes including itself by the first node on the list; and (c) multiple message exchanging of the time value among the nodes wherein either a value convergence is secured or the next node on the list broadcasts another time value in the manner of the first and submits to a multiple message exchanging, the process repeating until synchronization is achieved.
Claim 3
Dependent Claim
143 words
A fault tolerant method for periodically synchronizing the local clocks in a network of counterpart communicating CPU's (nodes), both the drift rate between the clocks and the network message transit and processing time being bounded, comprising the steps of: (a) forming an ordered list of node identities and replicating the list at each node; (b) broadcasting a time value with its unforgeable signature to all nodes including itself by the first node on the list; and (c) multiple message exchanging of the time value among the nodes wherein: (1) each node accepts the time value as valid and sets its clock forward if the time value is received within an interval predetermined as a function of the number of signatures, (2) otherwise repeating steps (b) and (c) as modified by broadcasting another time value from the next node in the list in order.
Claim 4
Dependent Claim
143 words
A fault tolerant method for periodically synchronizing the local clocks in a network of counterpart communicating CPU's (nodes), both the drift rate between the clocks and the network message transit and processing time being bounded, comprising the steps of: (a) forming an ordered list of node identities and replicating the list at each node; (b) broadcasting a time value with its unforgeable signature to all nodes including itself by the first node on the list; and (c) multiple message exchanging of the time value among the nodes wherein: (1) each node accepts the time value as valid and sets its clock forward if the time value is received within an interval predetermined as a function of the number of signatures, (2) otherwise repeating steps (b) and (c) as modified by broadcasting another time value from the next node in the list in order.
Claim 5
Dependent Claim
25 words
A method according to claim 2, wherein the network includes n nodes and tolerant of up to f faults which do not disconnect the network.
Claim 6
Dependent Claim
56 words
A method according to claim 2, wherein during the broadcasting of a time value and multiple message exchanging steps further includes the steps of creating new clocks and after a period of overlapping existence discarding the old clocks, the difference between the new clock and old clock readings being positive and never exceeding a fixed amount.
Claim 7
Dependent Claim
27 words
A method according to claim 2, wherein for a network of n nodes the number of messages required to reach synchronization is at most n 2 .
Claim 8
Dependent Claim
105 words
A method according to claim 1 or claim 2, wherein the step of broadcasting a time value with its unforgeable signature by node i includes the steps of operating upon the time value message m by way of an encoding function e i such that no processor other than the first node can generate the time value e i [m]; the step of multiple phase message exchanging of the time value among the nodes includes the step upon a node j receiving the message e i [m], decoding the time value m and determining that the node i was the processor that sent the message.
Claim 9
Independent Claim
33 words
A method according to claims 1 or 2, wherein at any given real time, the difference between the times of the local clocks of any two processor nodes is bound by a constant.
Claim 10
Dependent Claim
43 words
A method according to claim 4, wherein the gap between the time at which the first node starts a new clock and the last node starts a new clock is less than a constant multiple of the network message transit and processing time.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1988-07-22 | 1989-01-21 | 1989-07-23 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1992-07-22 | 1993-01-21 | 1993-07-23 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1996-07-22 | 1997-01-21 | 1997-07-23 | $7700.00 | Window Closed / Lapsed |