System and method for synchronizing clocks in distributed computer nodes

• US 5,907,685 A
• Filed: 08/04/1995
• Issued: 05/25/1999
• Est. Priority Date: 08/04/1995
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Douceur, John R.
• Primary Examiner(s): Bowler, Alyssa H.
• Assistant Examiner(s): Nguyen, Dzung C.
• Application Number:
  US08/511,420
• Time in Patent Office: 1,390 Days
• Field of Search: 395/200.17, 395/800, 395/200.31, 395/200.78, 395/800.01, 395/551, 395/555, 395/556, 395/558, 364/DIG. 1, 364/270.5, 364/270.7, 364/270.9, 364/271, 364/271.4
• US Class Current: 709/248
• CPC Class Codes: G04G 7/00 Synchronisation radio-controlled time-pieces G04R
• CPC Class Codes: G06F 1/14 Time supervision arrangements, e.g. real time clock
• CPC Class Codes: H04J 3/0667 Bidirectional timestamps, e.g. NTP or PTP for compensation of clock drift and for compensation of propagation delays arrangements for monitoring round trip delays in packet switching networks H04L43/0864

Abstract

Described herein is a distributed computer system having a plurality of computer nodes arranged logically adjacent to each other in a communications ring. Each computer node receives communications from a preceding computer node and sends communications to a succeeding computer node. The computer nodes maintain individual local clocks with local time values c. The clocks are synchronized to each other through a sequence of distributed processing steps. The steps include a step of measuring an approximate local offset d of the local time value of each computer node relative to the local time value of a logically adjacent computer node in the communications ring. A subsequent step includes passing a plurality of collation variables from a lead computer node, through the computer nodes forming the communications ring, and back to the lead computer node in a single pass. The collation variables are processed at each computer node as they are passed around the communications ring. This processing is based at least in part on the measured approximate local offsets d at each computer node. The lead computer then calculates a difference m between its local time value and the mean of the local time values of all the computer nodes based upon the collation variables received back at the lead computer node after being passed around the communications ring. Based upon difference m, values are provided to the distributed computer nodes representing their offsets from the mean. Each computer node then adjusts the rate of its local clock to achieve synchronization. To prevent frequency runaway, each computer node updates its clock through a PLL which limits the amount of correction which can be applied to the local clock.

Claims

1. In a distributed computer system having a plurality of computer nodes arranged logically adjacent to each other in a communications ring so that each computer node receives communications from a preceding computer node and sends communications to a succeeding computer node, wherein the computer nodes maintain local clocks with local time values (c);

a method of synchronizing the local clocks, the method comprising the following steps;

measuring an approximate local offset (d) of the local time value (c) of each computer node relative to the local time value (c) of the logically adjacent computer node in the communications ring;

passing a plurality of collation variables from a lead one of the computer nodes, through the computer nodes forming the communications ring, and back to the lead computer node in a single pass;

distributively processing the collation variables at each computer node as they are passed around the communications ring, said processing being based at least in part on the measured approximate local offsets (d) at each computer node;

calculating a difference (m) at the lead computer node between the local time value (c) of the lead computer node and a mean of the local time values (c) of at least some of the computer nodes based upon the collation variables received back at the lead computer node after being passed around the communications ring;

adjusting the local clocks of at least some of the computer nodes as a function of the calculated difference (m).

2. A method as recited in claim 1 and further comprising:

periodically repeating the steps of claim 1;

designating a new lead computer node for each periodic repetition of said steps of claim 1.

3. A method as recited in claim 1 and further comprising an additional step of initializing the collation variables to zero before passing them from the lead computer node.

4. A method as recited in claim 1, the measuring step comprising:

exchanging messages between logically adjacent computer nodes, said messages containing their transmission times;

recording the reception times of the messages;

calculating the approximate local offsets (d) from the transmission and reception times of the messages exchanged between the logically adjacent computer nodes.

5. A method as recited in claim 1, wherein:

the collation variables include a participating computer node count variable (t), an accumulated offset variable (p), and a summed time value variable (q);

the distributive processing step includes a step of incrementing the participating computer node count variable (t) by one after it is passed to each succeeding computer node which is designated as a participating computer node;

the participating computer node count variable (t) representing, after it has been passed back to the lead computer node, the total number of participating computer nodes in the communications ring;

the distributive processing step further includes a step of incrementing the accumulated offset variable (p) at each respective computer node by the measured approximate local offset (d) at that respective computer node after the accumulated offset variable (p) is passed to that respective computer node;

the accumulated offset variable (p) representing, after it has been passed back to the lead computer node, the accumulated measurement error in the measured local offsets (d);

the distributive processing step further includes a step of incrementing the summed time value variable (q) at each respective participating computer node by the accumulated offset variable (p) at that respective participating computer node after the summed time value variable (q) is passed to the respective participating computer node;

the calculating step includes dividing the summed time value variable (q) by the participating computer node count variable (t), wherein the result of said dividing represents the calculated difference (m), disregarding local offset measurement errors.

6. A method as recited in claim 1, wherein:

the collation variables include a computer node count variable (k) and an accumulated offset variable (p);

the distributive processing step includes a step of incrementing the computer node count variable (k) by one after it is passed to each succeeding computer node;

the computer node count variable (k) representing, after it has been passed back to the lead computer node, the total number of computer nodes in the communications ring;

the distributive processing step further includes a step of incrementing the accumulated offset variable (p) at each respective computer node by the measured approximate local offset (d) at that respective computer node after the accumulated offset variable (p) is passed to the respective computer node;

the accumulated offset variable (p) representing, after it has been passed back to the lead computer node, the accumulated measurement error in the measured local offsets (d);

the calculating step includes dividing the accumulated offset variable (p) by the computer node count variable (k) to obtain an average per-node measurement error (y).

7. A method as recited in claim 6, wherein:

the calculating step further includes calculating the calculated difference (m) as a function of the average per-node measurement error (y);

the method further comprises;

initializing a correction variable (n) to the calculated difference (m);

passing the average per-node measurement error (y) and the correction variable (n) from the lead computer node through the computer nodes forming the communications ring;

at each computer node, subtracting the average per-node measurement error (y) from the computer node'"'"'s approximate local offset (d) and adding the result to the correction variable (n) before passing the correction variable (n) to the succeeding computer node;

at each computer node, adjusting the computer node'"'"'s local clock as a function of the correction variable (n).

8. A method as recited in claim 1 and further comprising:

initializing a correction variable (n) to the calculated difference (m);

passing a correction variable (n) from the lead computer node through the computer nodes forming the communications ring;

at each respective computer node, incrementing the value of the correction variable (n) by the respective computer node'"'"'s approximate local offset (d) before passing the correction variable (n) to the succeeding computer node;

at each computer node, adjusting the computer node'"'"'s local clock as a function of the correction variable (n) at that computer node.

9. A method as recited in claim 1, wherein:

the collation variables include a total computer node count variable (k), a participating computer node count variable (t), an accumulated offset variable (p), a summed time value variable (q), and a summed computer node count variable (w), all of the collation variables being initialized to zero before passing them from the lead computer node;

the distributive processing step includes a step of incrementing the total computer node count variable (k) by one after it is passed to each succeeding computer node;

the total computer node count variable (k) representing, after it has been passed back to the lead computer node, the total number of computer nodes in the communications ring;

the distributive processing step further includes a step of incrementing the participating computer node count variable (t) by one after it is passed to each succeeding computer node which is designated as a participating computer node;

the participating computer node count variable (t) representing, after it has been passed back to the lead computer node, the total number of participating computer nodes in the communications ring;

the distributive processing step further includes a step of incrementing the accumulated offset variable (p) by the measured approximate local offset (d) of a particular computer node after the accumulated offset variable (p) is passed to that particular computer node;

the accumulated offset variable (p) representing, after it has been passed back to the lead computer node, the accumulated measurement error in the measured local offsets (d);

the distributive processing step further includes a step of incrementing the summed time value variable (q) at each respective participating computer node by the accumulated offset variable (p) at that respective participating computer node after the summed time value variable (q) is passed to the respective participating computer node;

the distributive processing step further includes a step of incrementing the summed computer node count variable (w) at each respective participating computer node by the total computer node count variable (k) at that respective participating computer node after the summed computer node count variable (w) is passed to the respective participating computer node;

the calculating step includes calculating the difference (m) as a function of the total computer node count variable (k), the participating computer node count variable (t), the accumulated offset variable (p), the summed time value variable (q), and the summed computer node count variable (w).

10. A method as recited in claim 9, the measuring step comprising:

exchanging messages between logically adjacent computer nodes, said messages containing their transmission times;

recording the reception times of the messages;

calculating the approximate local offsets (d) from the transmission and reception times of the messages exchanged between the logically adjacent computer nodes.

11. A method as recited in claim 9, wherein the calculating step further includes:

dividing the accumulated offset variable (p) by the total computer node count variable (k) to obtain an average per-node measurement error (y);

subtracting the summed time value variable (q) from the product of the average per-node measurement error (y) and the summed computer node count variable (w); and

dividing the result by the participating computer node count variable (t) to obtain the calculated difference (m) between the time value (c) of the lead computer node and the mean of the time values (c) of the participating computer nodes, said calculated difference (m) accounting for local offset measurement errors.

12. A method as recited in claim 9, wherein the calculating step further includes:

dividing the accumulated offset variable (p) by the total computer node count variable (k) to obtain an average per-node measurement error (y);

subtracting the summed time value variable (q) from the product of the average per-node measurement error (y) and the summed computer node count variable (w); and

dividing the result by the participating computer node count variable (t) to obtain the calculated difference (m) between the time value (c) of the lead computer node and the mean of the time values (c) of the participating computer nodes;

the method further comprising;

initializing a correction variable (n) to the calculated difference (m);

passing the average per-node measurement error (y) and the correction variable (n) from the lead computer node and through the computer nodes forming the communications ring;

at each computer node, subtracting the average per-node measurement error (y) from the computer node'"'"'s approximate local offset (d) and adding the result to the correction variable (n) before passing the correction variable (n) to the succeeding computer node;

at each computer node, adjusting the computer node'"'"'s local clock as a function of the correction variable (n) at that computer node.

13. A method as recited in claim 12, the measuring step comprising:

exchanging messages between logically adjacent computer nodes, said messages containing their transmission times;

recording the reception times of the messages;

calculating the approximate local offsets (d) from the transmission and reception times of the messages exchanged between the logically adjacent computer nodes.

14. A method as recited in claim 12, wherein each local clock has a rate which is a function of a rate adjustment factor (r), the method further comprising:

at each computer node, calculating a local clock rate adjustment factor (r) based at least in part upon the correction variable (n) at that computer node;

at each computer node, constraining the local clock rate adjustment factor (r) within upper and lower bounds.

15. A method as recited in claim 12, wherein each local clock has a rate which is a function of a rate adjustment factor (r), the method further comprising:

at each computer node, calculating a local clock rate adjustment factor (r) based at least in part upon the correction variable (n) at that computer node;

at each computer node, proportionally attenuating the local clock rate adjustment factor (r) as it approaches upper or lower bounds to constrain the local clock rate adjustment factor (r) within said upper and lower bounds.

16. A method as recited in claim 12, wherein each local clock has a rate which is a function of a rate adjustment factor (r), the method further comprising:

at each computer node, subtracting an adjustment term from the correction variable (n) at that computer node to obtain a locally adjusted correction variable (b), the adjustment term being proportional to a previous local clock rate adjustment factor (r_i-1) at the computer node;

at each computer node, calculating a new local clock rate adjustment factor (r_i) as a function of the locally adjusted correction variable (b) at that computer node.

17. A method as recited in claim 1, wherein each local clock has a rate which is a function of a rate adjustment factor (r), the method further comprising:

initializing a correction variable (n) to the calculated difference (m);

passing the correction variable (n) from the lead computer node and through the computer nodes forming the communications ring in a single pass;

processing the correction variable (n) at each computer node as it is passed around the communications ring, said processing being based at least in part on the measured approximate local offsets (d);

at each computer node, calculating a new local clock rate adjustment factor (r_i) based at least in part upon the correction variable (n) at that computer node.

18. A method as recited in claim 17 and further comprising the following additional step:

at each computer node, constraining the new local clock rate adjustment factor (r_i) within upper and lower bounds.

19. A method as recited in claim 17 and further comprising the following additional step:

at each computer node, proportionally attenuating the new local clock rate adjustment factor (r_i) as it approaches upper or lower bounds to constrain the new local clock rate adjustment factor (r_i) within said upper and lower bounds.

20. A method as recited in claim 17 and further comprising the following additional steps:

at each computer node, subtracting an adjustment term from the correction variable (n) to obtain a locally adjusted correction variable (b), the adjustment term being proportional to a previous local clock rate adjustment factor (r_i-1) at the computer node;

at each computer node, calculating the new local clock rate adjustment factor (r_i) as a function of the locally adjusted correction variable (b) at that computer node.

21. A method of synchronizing a local clock to a time reference, the method comprising:

regulating the rate of the local clock as a function of a clock rate adjustment factor;

obtaining a periodic sequence of error values indicating the offset of the local clock from the time reference;

for each respective error value in the sequence, changing the clock rate adjustment factor as a function of the respective error value;

attenuating changes in the clock rate adjustment factor by a variable term that constrains the clock rate adjustment factor within upper and lower bounds.

22. A method as recited in claim 21 and further comprising increasing the magnitude of the variable term in response to an increasing magnitude of the clock rate adjustment factor.

23. A method of synchronizing a local clock to a time reference, the method comprising:

obtaining a periodic sequence of error values indicating the offset of the local clock from the time reference;

regulating the rate of the local clock as a function of a sequence of clock rate adjustment factors calculated to correspond respectively to the error values;

calculating each sequential clock rate adjustment factor by adding a corresponding adjustment differential to a previous clock rate adjustment factor;

calculating the adjustment differential corresponding to a particular clock rate adjustment factor as a function of an attenuated error value, the attenuated error value being the difference between (a) the error value corresponding to the particular clock rate adjustment factor and (b) a variable attenuation term which is proportional to a previous clock rate adjustment factor.

24. A method as recited in claim 23 wherein calculating the adjustment differential comprises multiplying the attenuated error value by a frequency adjustment term to produce a frequency adjustment component of the adjustment differential.

25. A method as recited in claim 23 wherein calculating the adjustment differential comprises:

multiplying the attenuated error value by a phase adjustment term to produce a phase adjustment component of the adjustment differential;

subtracting from each adjustment differential the phase adjustment component of a previous adjustment differential.

26. A method as recited in claim 23 wherein calculating the adjustment differential comprises:

multiplying the attenuated error value by a phase adjustment term to produce a phase adjustment component of the adjustment differential;

multiplying the attenuated error value by a frequency adjustment term to produce a frequency adjustment component of the adjustment differential which is added to the phase adjustment component;

subtracting from each adjustment differential the phase adjustment component of a previous adjustment differential.

27. A computer node in a distributed computer system having a plurality of computer nodes arranged logically adjacent to each other in a communications ring so that each computer node receives communications from a preceding node and sends communications to a succeeding node, wherein the computer nodes maintain respective clocks with time values;

the computer node comprising;

a data processor;

communications means for exchanging communications with logically adjacent computers in the communications ring;

a local clock having a local time value (c);

the data processor being programmed to perform the following steps;

(i) measuring an approximate local offset (d) of the local time value (c) relative to the time value of the logically adjacent computer node in the communications ring;

(ii) receiving a plurality of collation variables from the preceding computer node in the communications ring;

(iii) processing the collation variables based at least in part on the measured approximate local offset (d);

(iv) sending the processed collation variables to the succeeding computer node in the communications ring;

(v) receiving a correction variable (n) from the preceding computer node in the communications ring, said correction variable (n) being calculated as a function of the processed collation variables;

(vi) adjusting the local clock as a function of the correction variable (n).

28. A distributed computer system comprising a plurality of computer nodes as recited in claim 27.

29. A computer node as recited in claim 27 wherein the correction variable (n) represents a difference between the local time value (c) of the local clock and a mean of the time values of the clocks of participating computer nodes in the communications ring.

30. A computer node as recited in claim 27, wherein:

the collation variables include a participating computer node count variable (t), an accumulated offset variable (p), and a summed time value variable (q);

during the programmed step (iii) of processing the collation variables, the data processor is programmed to perform the following additional steps;

incrementing the participating computer node count variable (t) by one before sending it to the succeeding computer node;

incrementing the accumulated offset variable (p) by the measured approximate local offset (d) before sending the accumulated offset variable (p) to the succeeding computer node;

incrementing the summed time value variable (q) by the accumulated offset variable (p) before sending the summed time value variable (q) to the succeeding computer node.

31. A computer node as recited in claim 27, wherein during the programmed step (i) of measuring an approximate local offset (d), the data processor is programmed to perform the following additional steps:

exchanging messages with the logically adjacent computer node, said messages containing their transmission times;

recording the reception times of the messages;

calculating the approximate local offset (d) from the transmission and reception times of the messages exchanged with the logically adjacent computer node.

32. A computer node as recited in claim 27, wherein:

the collation variables include a computer node count variable (k) and an accumulated offset variable (p);

during the programmed step (iii) of processing the collation variables, the data processor is programmed to perform the following additional steps;

incrementing the computer node count variable (k) by one before sending it to the succeeding computer node;

incrementing the accumulated offset variable (p) by the measured approximate local offset (d) before sending the accumulated offset variable (p) to the succeeding computer node.

33. A computer node as recited in claim 27 wherein the data processor is further programmed for:

processing the correction variable (n) based at least in part on the measured approximate local offset (d);

sending the processed correction variable (n) to the succeeding computer node in the communications ring.

34. A computer node as recited in claim 27, wherein the computer node may be designated as a participating node or a non-participating node, and wherein:

the collation variables include a total computer node count variable (k), a participating computer node count variable (t), an accumulated offset variable (p), a summed time value variable (q), and a summed computer node count variable (w);

the data processor being further programmed for;

incrementing the total node count variable (k) by one before sending it to the succeeding computer node;

if the computer node is designated as a participating computer node, incrementing the participating computer node count variable (t) by one before sending it to the succeeding computer node;

incrementing the accumulated offset variable (p) by the measured approximate local offset (d) before sending the accumulated offset variable (p) to the succeeding computer node;

if the computer node is designated as a participating computer node, incrementing the summed time value variable (q) by the accumulated offset variable (p) before sending the summed time value variable (q) to the succeeding computer node;

if the computer node is designated as a participating computer node, incrementing the summed node count variable (w) by the total node count variable (k) before sending the summed node count variable (w) to the succeeding computer node.

35. A computer node as recited in claim 34, wherein during the programmed step (i) of measuring an approximate local offset (d), the data processor is programmed to perform the following additional steps:

exchanging messages with the logically adjacent computer node, said messages containing their transmission times;

recording the reception times of the messages;

calculating the approximate local offset (d) from the transmission and reception times of the messages exchanged with the logically adjacent computer node.

36. A computer node as recited in claim 34, wherein:

the local clock has a rate which is a function of a clock rate adjustment factor (r);

the data processor is further programmed for;

calculating a new local clock rate adjustment factor (r) as a function of the correction variable (n);

constraining the local clock rate adjustment factor (r) within upper and lower bounds.

37. A computer node as recited in claim 34, wherein:

the local clock has a rate which is a function of a clock rate adjustment factor (r);

the data processor is further programmed for;

calculating a new local clock rate adjustment factor (r) as a function of the correction variable (n);

proportionally attenuating the local clock rate adjustment factor (r) as it approaches upper or lower bounds to constrain the local clock rate adjustment factor (r) within said upper and lower bounds.

38. A computer node as recited in claim 34, wherein:

the local clock has a rate which is a function of a clock rate adjustment factor (r);

the data processor is further programmed for;

subtracting an adjustment term from the correction variable (n) to obtain a locally adjusted correction variable (b), the adjustment term being proportional to a previous local clock rate adjustment factor (r_i-1);

calculating a new local clock rate adjustment factor (r_i) as a function of the locally adjusted correction variable (b).

39. A computer node as recited in claim 27, wherein:

the local clock has a rate which is a function of a clock rate adjustment factor (r);

the data processor being further programmed for;

processing the correction variable (n) based at least in part on the measured approximate local offset (d);

sending the processed correction variable (n) to the succeeding computer node in the communications ring;

calculating a new local clock rate adjustment factor (r_i) based at least in part upon the correction variable (n).

40. A computer node as recited in claim 39 the data processor being further programmed for constraining the local clock rate adjustment factor (r_i) within upper and lower bounds.

41. A computer node as recited in claim 39, the data processor being further programmed for proportionally attenuating the new local clock rate adjustment factor (r_i) as it approaches upper or lower bounds to constrain the new local clock rate adjustment factor (r_i) within said upper and lower bounds.

42. A computer node as recited in claim 39, the data processor being further programmed for:

subtracting an adjustment term from the correction variable (n) to obtain a locally adjusted correction variable (b), the adjustment term being proportional to a previous local clock rate adjustment factor (r_i-1);

calculating the new local clock rate adjustment factor (r_i) as a function of the locally adjusted correction variable (b).

43. A computer node in a distributed computer system having a plurality of computer nodes arranged logically adjacent to each other in a communications ring so that each computer node receives communications from a preceding node and sends communications to a succeeding node, wherein the computer nodes maintain respective clocks with time values;

the computer node comprising;

a data processor;

communications means for exchanging communications with logically adjacent computers in the communications ring;

a local clock having a local time value (c);

the data processor being programmed to configure the computer node alternatively as a lead node and as follower node;

the data processor being programmed when configuring the computer node as a lead node to perform the following steps;

(i) initializing and passing a plurality of collation variables to the succeeding computer node in the communications ring;

(ii) receiving the collation variables back from the preceding computer node in the communications ring;

(iii) calculating a difference (m) between the local time value (c) of the local clock and a mean of the time values of the clocks of other computer nodes in the communications ring based upon the received collation variables;

(iv) adjusting the local clock as a function of the calculated difference (m);

(v) sending a correction variable (n) to the succeeding computer node in the communications ring;

the data processor being programmed when configuring the computer node as a follower node to perform the following steps;

(vi) measuring an approximate local offset (d) of the local time value (c) relative to the time value of the logically adjacent computer node in the communications ring;

(vii) receiving the collation variables from the preceding computer node in the communications ring;

(viii) processing the collation variables based at least in part on the measured approximate local offset (d);

(ix) sending the processed collation variables to the succeeding computer node in the communications ring;

(x) receiving the correction variable (n) from the preceding computer node in the communications ring;

(xi) adjusting the local clock as a function of the correction variable (n).

44. A distributed computer system comprising a plurality of computer nodes as recited in claim 43.

45. A computer node as recited in claim 43, wherein the programmed step (i) of initializing and passing collation variables includes initializing the collation variables to zero.

46. A computer node as recited in claim 43, wherein:

the collation variables include a participating computer node count variable (t), an accumulated offset variable (p), and a summed time value variable (q);

during the programmed step (viii) of processing the collation variables, the data processor is programmed to perform the following additional steps;

incrementing the participating computer node count variable (t) by one before sending it to the succeeding computer node;

incrementing the accumulated offset variable (p) by the measured approximate local offset (d) before sending the accumulated offset variable (p) to the succeeding computer node;

incrementing the summed time value variable (q) by the accumulated offset variable (p) before sending the summed time value variable (q) to the succeeding computer node;

the programmed step (iii) of calculating the difference (m) includes dividing the summed time value variable (q) by the participating computer node count variable (t), wherein the result of said dividing represents the calculated difference (m), disregarding local offset measurement errors.

47. A computer node as recited in claim 43, wherein:

the collation variables include a computer node count variable (k) and an accumulated offset variable (p);

during the programmed step (viii) of processing the collation variables, the data processor is programmed to perform the following additional steps;

incrementing the computer node count variable (k) by one before sending it to the succeeding computer node;

incrementing the accumulated offset variable (p) by the measured approximate local offset before sending the accumulated offset variable (p) to the succeeding computer node;

the programmed step (iii) of calculating the difference (m) includes dividing the accumulated offset variable (p) by the computer node count variable (k) to obtain an average per-node measurement error (y).

48. A computer node as recited in claim 43 wherein:

the programmed step (v) of sending a correction variable includes initializing the correction variable (n) to the calculated difference (m) before sending it to the succeeding computer in the communications ring;

the data processor being further programmed when configuring the computer node as a lead node for;

incrementing the value of the correction variable (n) by the approximate local offset (d);

sending the correction variable (n) to the succeeding computer node in the communications ring.

49. A computer node as recited in claim 43, wherein:

the collation variables include a computer node count variable (k) and an accumulated offset variable (p);

during the programmed step (viii) of processing the collation variables, the data processor is programmed to perform the following additional steps;

incrementing the computer node count variable (k) by one before sending it to the succeeding computer node;

incrementing the accumulated offset variable (p) by the measured approximate local offset before sending the accumulated offset variable (p) to the succeeding computer node;

during the programmed step (iii) of calculating the difference (m), the data processor is programmed to perform the following additional steps;

dividing the accumulated offset variable (p) by the computer node count variable (k) to obtain an average per-node measurement error (y);

calculating the calculated difference (m) as a function of the average per-node measurement error (y);

the data processor being further programmed when configuring the computer node as a lead node for;

initializing the correction variable (n) to the calculated difference (m);

sending the average per-node measurement error (y) to the succeeding computer node in the communications ring in addition to the correction variable (n);

the data processor being further programmed when configuring the computer node as a follower node for;

receiving the average per-node measurement error (y) from the preceding computer node in the communications ring in addition to the correction variable (n);

subtracting the average per-node measurement error (y) from the approximate local offset (d) and adding the result to the correction variable (n);

sending the average per-node measurement error (y) and the correction variable (n) to the succeeding computer node in the communications ring.

50. A computer node as recited in claim 43, wherein the computer node may be designated as a participating node or a non-participating node, and wherein:

the collation variables include a total computer node count variable (k), a participating computer node count variable (t), an accumulated offset variable (p), a summed time value variable (q), and a summed computer node count variable (w), all of the collation variables being initialized to zero before they are passed from the lead computer node;

the data processor being further programmed for;

incrementing the total node count variable (k) by one before sending it to the succeeding computer node;

if the computer node is designated as a participating computer node, incrementing the participating computer node count variable (t) by one before sending it to the succeeding computer node;

incrementing the accumulated offset variable (p) by the measured approximate local offset (d) before sending the accumulated offset variable (p) to the succeeding computer node;

if the computer node is designated as a participating computer node, incrementing the summed time value variable (q) by the accumulated offset variable (p) before sending the summed time value variable (q) to the succeeding computer node;

if the computer node is designated as a participating computer node, incrementing the summed node count variable (w) by the total node count variable (k) before sending the summed node count variable (w) to the succeeding computer node;

the programmed step (iii) of calculating the difference (m) includes calculating the difference (m) as a function of the total computer node count variable (k), the participating computer node count variable (t), the accumulated offset variable (p), the summed time value variable (q), and the summed computer node count variable (w).

51. A distributed computer system comprising a plurality of computer nodes as recited in claim 50.

52. A computer node as recited in claim 50, wherein during the programmed step (iii) of calculating the difference (m), the data processor is programmed to perform the following additional steps:

dividing the accumulated offset variable (p) by the total computer node count variable (k) to obtain an average per-node measurement error (y);

subtracting the summed time value variable (q) from the product of the average per-node measurement error (y) and the summed computer node count variable (w); and

dividing the result by the participating computer node count variable (t) to obtain the calculated difference (m) between the time value (c) of the lead computer node and the mean of the time values (c) of the participating computer nodes, said calculated difference (m) accounting for local offset measurement errors.

53. A computer node as recited in claim 50, wherein during the programmed step (iii) of calculating the difference (m), the data processor is programmed to perform the following additional steps:

dividing the accumulated offset variable (p) by the total computer node count variable (k) to obtain an average per-node measurement error (y);

subtracting the summed time value variable (q) from the product of the average per-node measurement error (y) and the summed computer node count variable (w); and

dividing the result by the participating computer node count variable (t) to obtain the calculated difference (m) between the time value (c) of the lead computer node and the mean of the time values (c) of the participating computer nodes;

wherein the data processor is further programmed when configuring the computer node as a lead node for;

initializing the correction variable (n) to the calculated difference (m);

passing the average per-node measurement error (y) the succeeding computer node in the communications ring in addition to the correction variable (n);

the data processor being further programmed when configuring the computer node as a follower node for;

receiving the average per-node measurement error (y) from the preceding computer node in the communications ring in addition to the correction variable (n);

subtracting the average per-node measurement error (y) from the approximate local offset (d) and adding the result to the correction variable (n);

sending the average per-node measurement error (y) and the correction variable (n) to the succeeding computer node in the communications ring.

54. A computer node as recited in claim 53, wherein:

the local clock has a rate which is a function of a clock rate adjustment factor (r);

the data processor is further programmed for;

calculating a new local clock rate adjustment factor (r) as a function of the correction variable (n);

constraining the local clock rate adjustment factor (r) within upper and lower bounds.

55. A computer node as recited in claim 53, wherein:

the local clock has a rate which is a function of a clock rate adjustment factor (r);

the data processor is further programmed for;

calculating a new local clock rate adjustment factor (r) as a function of the correction variable (n);

proportionally attenuating the local clock rate adjustment factor (r) as it approaches upper or lower bounds to constrain the local clock rate adjustment factor (r) within said upper and lower bounds.

56. A computer node as recited in claim 53, wherein:

the local clock has a rate which is a function of a clock rate adjustment factor (r);

the data processor is further programmed for;

subtracting an adjustment term from the correction variable (n) to obtain a locally adjusted correction variable (b), the adjustment term being proportional to a previous local clock rate adjustment factor (r_i-1);

calculating a new local clock rate adjustment factor (r_i) as a function of the locally adjusted correction variable (b).

57. A computer node as recited in claim 43, wherein:

the local clock has a rate which is a function of a clock rate adjustment factor (r);

the programmed step (v) of sending a correction variable (n) includes initializing the correction variable (n) to the calculated difference (m);

the data processor being further programmed when configuring the computer node as a follower node for;

processing the correction variable (n) based at least in part on the measured approximate local offset (d);

sending the processed correction variable (n) to the succeeding computer node in the communications ring.

calculating a new local clock rate adjustment factor (r_i) based at least in part upon the correction variable (n).

58. A computer node as recited in claim 57 the data processor being further programmed for constraining the local clock rate adjustment factor (r_i) within upper and lower bounds.

59. A computer node as recited in claim 57, the data processor being further programmed for proportionally attenuating the new local clock rate adjustment factor (r_i) as it approaches upper or lower bounds to constrain the new local clock rate adjustment factor (r_i) within said upper and lower bounds.

60. A computer node as recited in claim 57, the data processor being further programmed for:

subtracting an adjustment term from the correction variable (n) to obtain a locally adjusted correction variable (b), the adjustment term being proportional to a previous local clock rate adjustment factor (r_i-1);

calculating the new local clock rate adjustment factor (r_i) as a function of the locally adjusted correction variable (b).

61. A clock for maintaining a local time value in synchronization with a time reference in response to a periodic sequence of error values indicating the offset of the local time value from the time reference, comprising:

means for regulating the rate of the local clock as a function of a clock rate adjustment factor;

means for periodically changing the clock rate adjustment factor as a function of the error values;

means for attenuating changes in the clock rate adjustment factor by a variable term that constrains the clock rate adjustment factor within upper and lower bounds; and

means for increasing the magnitude of the variable term in response to an increasing magnitude of the clock rate adjustment factor.

62. A clock for maintaining a local time value in synchronization with a time reference in response to a periodic sequence of error values indicating the offset of the local time value from the time reference, comprising:

means for regulating the rate of the local clock as a function of a sequence of clock rate adjustment factors calculated to correspond respectively to the error values;

means for calculating each sequential clock rate adjustment factor by adding a corresponding adjustment differential to a previous clock rate adjustment factor;

means for calculating the adjustment differential corresponding to a particular clock rate adjustment factor as a function of an attenuated error value, the attenuated error value being the difference between (a) the error value corresponding to the particular clock rate adjustment factor and (b) a variable attenuation term which is proportional to a previous clock rate adjustment factor.

63. A clock as recited in claim 62 wherein said means for calculating the adjustment differential comprises means for multiplying the attenuated error value by a frequency adjustment term to produce a frequency adjustment component of the adjustment differential.

64. A clock as recited in claim 62 wherein said means for calculating the adjustment differential comprises:

means for multiplying the attenuated error value by a phase adjustment term to produce a phase adjustment component of the adjustment differential;

means for subtracting from each adjustment differential the phase adjustment component of a previous adjustment differential.

65. A clock as recited in claim 62 wherein said means for calculating the adjustment differential comprises:

means for multiplying the attenuated error value by a phase adjustment term to produce a phase adjustment component of the adjustment differential;

means for multiplying the attenuated error value by a frequency adjustment term to produce a frequency adjustment component of the adjustment differential which is added to the phase adjustment component;

means for subtracting from each adjustment differential the phase adjustment component of a previous adjustment differential.