US5041966A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Partially distributed method for clock synchronization
Assignee: NEC Corp
•
Filing: 1988-10-05
•
Granted: 1991-08-20
•
Expires: 2008-10-05
Abstract
Abstract In a distributed system comprising a plurality of processors coupled to one another, each processor comprises a controllable clock circuit which indicates a local time. Clock synchronization methods are based on the idea in which randomly selected M processors out of the total N processors cooperate to adjust the controllable clock circuits of all processors in the distributed system. Three types of methods are described. In a first one of the methods, all processors randomly selects M processors, respectively, at time instants which are different from one another, and each processor adjusts its own controllable clock circuit to an average of the local times of the selected M processors. In a second method, each processor transmits its own local time to randomly selected M processors and adjusts its own controllable clock circuit to the average of received local times. In a third method, all processors adjust their controllable clock circuits to the average of received local times issued by randomly selected M processors. Fault tolerance against each processor is taken into account in their methods. Their methods can be applied to a sufficient large distributed system because of a small number of messages exchanged among processors.
Inventors
- 👤 Syoichiro Nakai
- 👤 Satoshi Hasegawa
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-27 05:16
CPC Classifications
G; G06; G06F; G06F1/00; G06F1/04; G06F1/12
Claims Analysis
Total Claims: 16
Claim 1
Independent Claim
228 words
In a distributed system comprising first through N-th processors connected together, where N represents a first predetermined natural number which is not less than three, said first through N-th processors including first through N-th controllable clock circuits, respectively, and an n-th processor including an n-th controllable clock circuit indicating an n-th local time instant, where n represents each of 1 through N, a method of synchronizing said first through N-th controllable clock circuits comprising the steps of: setting in an n-th timer circuit of said n-th processor an adjusting time interval which is randomly selected from a predetermined time interval, when said n-th controllable clock circuit indicates a predetermined time instant; randomly selecting a plurality of processors as selected processors from said first through N-th processors when said n-th time circuit indicates that said adjusting time interval has lapsed, where said selected processors are equal in number to a second predetermined natural number which is not less than two but is less than said first predetermined natural number; reading, as readout time instants, said local time instants indicated by said controllable clock circuits of each of the respective said selected processors; calculating an average time instant of said readout time instants; calculating a time difference between said n-th local time instant and said average time instant; and adjusting said n-th controllable clock circuit by using said time difference.
Claim 2
Dependent Claim
228 words
In a distributed system comprising first through N-th processors connected together, where N represents a first predetermined natural number which is not less than three, said first through N-th processors including first through N-th controllable clock circuits, respectively, and an n-th processor including an n-th controllable clock circuit indicating an n-th local time instant, where n represents each of 1 through N, a method of synchronizing said first through N-th controllable clock circuits comprising the steps of: setting in an n-th timer circuit of said n-th processor an adjusting time interval which is randomly selected from a predetermined time interval, when said n-th controllable clock circuit indicates a predetermined time instant; randomly selecting a plurality of processors as selected processors from said first through N-th processors when said n-th time circuit indicates that said adjusting time interval has lapsed, where said selected processors are equal in number to a second predetermined natural number which is not less than two but is less than said first predetermined natural number; reading, as readout time instants, said local time instants indicated by said controllable clock circuits of each of the respective said selected processors; calculating an average time instant of said readout time instants; calculating a time difference between said n-th local time instant and said average time instant; and adjusting said n-th controllable clock circuit by using said time difference.
Claim 3
Dependent Claim
232 words
In a distributed system comprising first through N-th processors connected together, where N represents a first predetermined natural number which is not less than three, said first through N-th processors including first through N-th controllable clock circuits, respectively, and an n-th processor including an n-th controllable clock circuit indicating an n-th local time instant, where n represents each of 1 through N, a method of synchronizing said first through N-th controllable clock circuits comprising the steps of: setting in an n-th timer circuit of said n-th processor an adjusting time interval which is randomly selected from a predetermined time interval, when said n-th controllable clock circuit indicates a predetermined time instant; randomly selecting a plurality of processors as selected processors from said first through N-th processors when said n-th timer circuit indicates that said adjusting time interval has lapsed, where said selected processors are equal in number to a second predetermined natural number which is not less than two but is less than said first predetermined natural number; reading, as readout time instants, said local time instants indicated by said controllable clock circuits of each of the respective said selected processors; calculating a plurality of time differences between said n-th local time instant and each of said readout time instants; calculating a mean time of said plurality of time differences; and adjusting said n-th controllable clock circuit by using said mean time.
Claim 4
Dependent Claim
232 words
In a distributed system comprising first through N-th processors connected together, where N represents a first predetermined natural number which is not less than three, said first through N-th processors including first through N-th controllable clock circuits, respectively, and an n-th processor including an n-th controllable clock circuit indicating an n-th local time instant, where n represents each of 1 through N, a method of synchronizing said first through N-th controllable clock circuits comprising the steps of: setting in an n-th timer circuit of said n-th processor an adjusting time interval which is randomly selected from a predetermined time interval, when said n-th controllable clock circuit indicates a predetermined time instant; randomly selecting a plurality of processors as selected processors from said first through N-th processors when said n-th timer circuit indicates that said adjusting time interval has lapsed, where said selected processors are equal in number to a second predetermined natural number which is not less than two but is less than said first predetermined natural number; reading, as readout time instants, said local time instants indicated by said controllable clock circuits of each of the respective said selected processors; calculating a plurality of time differences between said n-th local time instant and each of said readout time instants; calculating a mean time of said plurality of time differences; and adjusting said n-th controllable clock circuit by using said mean time.
Claim 5
Dependent Claim
223 words
In a distributed system comprising first through N-th processors connected together, where N represents a first predetermined natural number which is not less than three, said first through N-th processors including first through N-th controllable clock circuits, respectively, and an n-th processor including an n-th controllable clock circuit indicating an n-th local time instant, where n represents each of 1 through N, a method of synchronizing said first through N-th controllable clock circuits comprising the steps of: randomly selecting a plurality of processors as selected processors from said first through said N-th processors when said n-th controllable clock circuit indicates a predetermined time instant, said selected processors being equal in number to a second predetermined natural number which is not less than two but is less than said first predetermined natural number; transmitting said n-th local time instant to said selected processors as a transmitted time instant; calculating a plurality of time differences between said n-th local time instant and each of the respective said transmitted time instants, when said transmitted time instant is received; memorizing said time differences as memorized times; calculating a mean time of said memorized times when said n-th controllable clock circuit indicates a time instant which is a predetermined time interval after said predetermined time instant; and adjusting said n-th controllable clock circuit by using said mean time.
Claim 6
Dependent Claim
223 words
In a distributed system comprising first through N-th processors connected together, where N represents a first predetermined natural number which is not less than three, said first through N-th processors including first through N-th controllable clock circuits, respectively, and an n-th processor including an n-th controllable clock circuit indicating an n-th local time instant, where n represents each of 1 through N, a method of synchronizing said first through N-th controllable clock circuits comprising the steps of: randomly selecting a plurality of processors as selected processors from said first through said N-th processors when said n-th controllable clock circuit indicates a predetermined time instant, said selected processors being equal in number to a second predetermined natural number which is not less than two but is less than said first predetermined natural number; transmitting said n-th local time instant to said selected processors as a transmitted time instant; calculating a plurality of time differences between said n-th local time instant and each of the respective said transmitted time instants, when said transmitted time instant is received; memorizing said time differences as memorized times; calculating a mean time of said memorized times when said n-th controllable clock circuit indicates a time instant which is a predetermined time interval after said predetermined time instant; and adjusting said n-th controllable clock circuit by using said mean time.
Claim 7
Dependent Claim
263 words
In a distributed system comprising first through N-th processors connected together, where N represents a first predetermined natural number which is not less than three, said first through N-th processors including first through N-th controllable clock circuits, respectively, and an n-th processor including an n-th controllable clock circuit indicating an n-th local time instant, where n represents each of 1 through N, a method of synchronizing said first through N-th controllable clock circuits comprising the steps of: generating a random number which has one of a plurality of predetermined logic values; selecting said random number as a selected number when said n-th controllable clock circuit indicates a first predetermined time instant; transmitting said n-th local time instant to said first through N-th processors as a transmitted time instant when said n-th controllable clock circuit indicates a second predetermined time instant, said second predetermined time instant being a first predetermined time interval after said first predetermined time instant and said selected number equals a particular one of said predetermined logic values; calculating a plurality of time differences between said n-th local time instant and each of the respective said transmitted time instants, when said transmitted time instant is received; memorizing said time differences as memorized times; calculating a mean time of said memorized times when said n-th controllable clock circuit indicates a third predetermined time instant which is a second predetermined time interval after said first predetermined time instant, said second predetermined time interval being longer than said first predetermined time interval; and adjusting said n-th controllable clock circuit by using said mean time.
Claim 8
Dependent Claim
263 words
In a distributed system comprising first through N-th processors connected together, where N represents a first predetermined natural number which is not less than three, said first through N-th processors including first through N-th controllable clock circuits, respectively, and an n-th processor including an n-th controllable clock circuit indicating an n-th local time instant, where n represents each of 1 through N, a method of synchronizing said first through N-th controllable clock circuits comprising the steps of: generating a random number which has one of a plurality of predetermined logic values; selecting said random number as a selected number when said n-th controllable clock circuit indicates a first predetermined time instant; transmitting said n-th local time instant to said first through N-th processors as a transmitted time instant when said n-th controllable clock circuit indicates a second predetermined time instant, said second predetermined time instant being a first predetermined time interval after said first predetermined time instant and said selected number equals a particular one of said predetermined logic values; calculating a plurality of time differences between said n-th local time instant and each of the respective said transmitted time instants, when said transmitted time instant is received; memorizing said time differences as memorized times; calculating a mean time of said memorized times when said n-th controllable clock circuit indicates a third predetermined time instant which is a second predetermined time interval after said first predetermined time instant, said second predetermined time interval being longer than said first predetermined time interval; and adjusting said n-th controllable clock circuit by using said mean time.
Claim 9
Dependent Claim
265 words
In a distributed system comprising first through N-th processors connected together, where N represents a first predetermined natural number which is not less than three, said first through N-th processors including first through N-th controllable clock circuits, respectively, and an n-th processor including an n-th controllable clock circuit indicating an n-th local time instant, where n represents each of 1 through N, the improvement wherein said n-th processor comprises: generating means for generating adjusting time interval which is randomly selected from a predetermined time interval when said n-th controllable clock circuit indicates a predetermined time instant; measuring means responsive to said adjusting time interval for measuring a lapsed time after said predetermined time instant, said measuring means producing a time out signal when said lapsed time is equal to said adjusting time interval; selecting means responsive to said time out signal for randomly selecting a plurality of processors as selected processors from said first through N-th processors, said selected processors being equal in number to a second predetermined natural number which is not less than two but which is less than said first predetermined natural number; reading means for reading, as readout time instants, a plurality of local time instants, each said local time instant indicated by a controllable clock circuit of the respective said selected processors; average calculating means for calculating an average time instant of said readout time instants; difference calculating means for calculating a time difference between said n-th local time instant and said average time instant; and adjusting means for adjusting said n-th controllable clock circuit by using said time difference.
Claim 10
Dependent Claim
265 words
In a distributed system comprising first through N-th processors connected together, where N represents a first predetermined natural number which is not less than three, said first through N-th processors including first through N-th controllable clock circuits, respectively, and an n-th processor including an n-th controllable clock circuit indicating an n-th local time instant, where n represents each of 1 through N, the improvement wherein said n-th processor comprises: generating means for generating adjusting time interval which is randomly selected from a predetermined time interval when said n-th controllable clock circuit indicates a predetermined time instant; measuring means responsive to said adjusting time interval for measuring a lapsed time after said predetermined time instant, said measuring means producing a time out signal when said lapsed time is equal to said adjusting time interval; selecting means responsive to said time out signal for randomly selecting a plurality of processors as selected processors from said first through N-th processors, said selected processors being equal in number to a second predetermined natural number which is not less than two but which is less than said first predetermined natural number; reading means for reading, as readout time instants, a plurality of local time instants, each said local time instant indicated by a controllable clock circuit of the respective said selected processors; average calculating means for calculating an average time instant of said readout time instants; difference calculating means for calculating a time difference between said n-th local time instant and said average time instant; and adjusting means for adjusting said n-th controllable clock circuit by using said time difference.
Claim 11
Dependent Claim
266 words
In a distributed system comprising first through N-th processors connected together, where N represents a first predetermined natural number which is not less than three, said first through N-th processors including first through N-th controllable clock circuits, respectively, and an n-th processor including an n-th controllable clock circuit indicating an n-th local time instant, where n represents each of 1 through N, the improvement wherein said n-th processor comprises: generating means for generating an adjusting time interval which is randomly selected from a predetermined time interval when said n-th controllable clock circuit indicates a predetermined time instant; measuring means responsive to said adjusting time interval for measuring a lapsed time after said predetermined time instant, said measuring means producing a time out signal when said lapsed time is equal to said adjusting time interval; selecting means responsive to said time out signal for randomly selecting a plurality of processors as selected processors from said first through N-th processors, said selected processors being equal in number to a second predetermined natural number which is not less than two but which is less than said first predetermined natural number; reading means for reading, as readout time instants, a plurality of local time instants, each said local time instant indicated by a controllable clock circuit of the respective said selected processors; difference calculating means for calculating a plurality of time differences between said n-th local time instant and said readout time instants; mean calculating means for calculating a mean time of said time differences; and adjusting means for adjusting said n-th controllable clock circuit by using said mean time.
Claim 12
Dependent Claim
266 words
In a distributed system comprising first through N-th processors connected together, where N represents a first predetermined natural number which is not less than three, said first through N-th processors including first through N-th controllable clock circuits, respectively, and an n-th processor including an n-th controllable clock circuit indicating an n-th local time instant, where n represents each of 1 through N, the improvement wherein said n-th processor comprises: generating means for generating an adjusting time interval which is randomly selected from a predetermined time interval when said n-th controllable clock circuit indicates a predetermined time instant; measuring means responsive to said adjusting time interval for measuring a lapsed time after said predetermined time instant, said measuring means producing a time out signal when said lapsed time is equal to said adjusting time interval; selecting means responsive to said time out signal for randomly selecting a plurality of processors as selected processors from said first through N-th processors, said selected processors being equal in number to a second predetermined natural number which is not less than two but which is less than said first predetermined natural number; reading means for reading, as readout time instants, a plurality of local time instants, each said local time instant indicated by a controllable clock circuit of the respective said selected processors; difference calculating means for calculating a plurality of time differences between said n-th local time instant and said readout time instants; mean calculating means for calculating a mean time of said time differences; and adjusting means for adjusting said n-th controllable clock circuit by using said mean time.
Claim 13
Dependent Claim
250 words
In a distributed system comprising first through N-th processors connected together, where N represents a first predetermined natural number which is not less than three, said first through N-th processors including first through N-th controllable clock circuits, respectively, and an n-th processor including an n-th controllable clock circuit indicating an n-th local time instant, where n represents each of 1 through N, the improvement wherein said n-th processor comprises: selecting means for randomly selecting a plurality of processors as selected processors from said first through N-th processors when said n-th controllable clock circuits indicate a predetermined time instant, said selected processors being equal in number to a second predetermined natural number which is not less than two but is less than said first predetermined natural number; transmitting means for transmitting said n-th local time instant to said selected processors as a transmitted time instant; difference calculating means for calculating a plurality of time differences between said n-th local time instant and each of the respective said transmitted time instants, when said transmitted time instant is received; memorizing means for memorizing said time differences as memorized times; measuring means for measuring a lapsed time after said predetermined time instant, said measuring means producing a time out signal when said lapsed time is equal to a predetermined time interval; mean calculating means responsive to said time out signal for calculating a mean time of said memorized times; and adjusting means for adjusting said n-th controllable clock circuit by using said mean time.
Claim 14
Dependent Claim
250 words
In a distributed system comprising first through N-th processors connected together, where N represents a first predetermined natural number which is not less than three, said first through N-th processors including first through N-th controllable clock circuits, respectively, and an n-th processor including an n-th controllable clock circuit indicating an n-th local time instant, where n represents each of 1 through N, the improvement wherein said n-th processor comprises: selecting means for randomly selecting a plurality of processors as selected processors from said first through N-th processors when said n-th controllable clock circuits indicate a predetermined time instant, said selected processors being equal in number to a second predetermined natural number which is not less than two but is less than said first predetermined natural number; transmitting means for transmitting said n-th local time instant to said selected processors as a transmitted time instant; difference calculating means for calculating a plurality of time differences between said n-th local time instant and each of the respective said transmitted time instants, when said transmitted time instant is received; memorizing means for memorizing said time differences as memorized times; measuring means for measuring a lapsed time after said predetermined time instant, said measuring means producing a time out signal when said lapsed time is equal to a predetermined time interval; mean calculating means responsive to said time out signal for calculating a mean time of said memorized times; and adjusting means for adjusting said n-th controllable clock circuit by using said mean time.
Claim 15
Dependent Claim
289 words
In a distributed system comprising first through N-th processors connected together where N represents a first predetermined natural number which is not less than three, said first through N-th processors including first through N-th controllable clock circuits, respectively, and an n-th processor including an n-th controllable clock circuit indicating an n-th local time instant, where n represents each of 1 through N, the improvement wherein said n-th processors comprises: generating means for generating a random number which has one of a plurality of predetermined logic values; selecting means for selecting said random number as a selected number when said n-th controllable clock circuit indicates a first predetermined time instant; transmitting means for transmitting said n-th local time instant to said first through N-th selected processors as a transmitted time instant when said n-th controllable clock circuit indicates a second predetermined time instant, said second predetermined time instant being a first predetermined time interval after said first predetermined time instant, and said selected number equals a particular one of said predetermined logic values; difference calculating means for calculating a plurality of time differences between said n-th local time instant and each of the respective said transmitted time instants, when said transmitted time instant is received; memorizing means for memorizing said time differences as memorized times; measuring means for measuring a lapsed time after said first predetermined time instant, said measuring means producing a time out signal when said lapsed time is equal to a second predetermined time interval which is longer than said first predetermined time interval; means calculating means responsive to said time out signal for calculating a mean time of said memorized times; and adjusting means for adjusting said n-th controllable clock circuit by using said mean time.
Claim 16
Dependent Claim
289 words
In a distributed system comprising first through N-th processors connected together where N represents a first predetermined natural number which is not less than three, said first through N-th processors including first through N-th controllable clock circuits, respectively, and an n-th processor including an n-th controllable clock circuit indicating an n-th local time instant, where n represents each of 1 through N, the improvement wherein said n-th processors comprises: generating means for generating a random number which has one of a plurality of predetermined logic values; selecting means for selecting said random number as a selected number when said n-th controllable clock circuit indicates a first predetermined time instant; transmitting means for transmitting said n-th local time instant to said first through N-th selected processors as a transmitted time instant when said n-th controllable clock circuit indicates a second predetermined time instant, said second predetermined time instant being a first predetermined time interval after said first predetermined time instant, and said selected number equals a particular one of said predetermined logic values; difference calculating means for calculating a plurality of time differences between said n-th local time instant and each of the respective said transmitted time instants, when said transmitted time instant is received; memorizing means for memorizing said time differences as memorized times; measuring means for measuring a lapsed time after said first predetermined time instant, said measuring means producing a time out signal when said lapsed time is equal to a second predetermined time interval which is longer than said first predetermined time interval; means calculating means responsive to said time out signal for calculating a mean time of said memorized times; and adjusting means for adjusting said n-th controllable clock circuit by using said mean 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) | 1994-08-19 | 1995-02-18 | 1995-08-20 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1998-08-19 | 1999-02-18 | 1999-08-20 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2002-08-19 | 2003-02-18 | 2003-08-20 | $7700.00 | Window Closed / Lapsed |