Synchronizing clocks in an asynchronous distributed system

• US 8,073,976 B2
• Filed: 03/25/2009
• Issued: 12/06/2011
• Est. Priority Date: 03/27/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Marucheck, Michael J., Hasha, Richard L., Mohsin, Mansoor
• Primary Examiner(s): TANG, KAREN C
• Application Number:
  US12/410,677
• Publication Number:
  US 20090248900A1
• Time in Patent Office: 986 Days
• Field of Search: 709/248, 709/223, 709/224, 713375-440
• US Class Current: 709/248
• CPC Class Codes: G06F 1/12 Synchronisation of different clock signals provided by a plurality of clock generators
• 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

The present invention extends to methods, systems, and computer program products for synchronizing clocks in an asynchronous distributed system. Embodiments of the invention facilitate creation of a trustable and practical common time (time of day) reference across a set of peer nodes (observers), such as, for example, members within a common asynchronous (distributed) system. A class of pseudo synchronous system can be created via tracking and accumulating worst case relativistic time skews amongst pairs of nodes (observers), without reference to a common master. As such, cooperating nodes can essentially guarantee a lower bound on the time-of-day that one node will observe, given an observation on another node. Accordingly, embodiments of the invention can be applied to provide a consistent (essentially safe) view of the worst case (i.e., greatest variance in) current time across such an asynchronous system—without a common external time-of-day clock entity being used.

Claims

1. At an observing computer system in an asynchronous distributed system including a plurality of computer system, the observing computer system including a processor and system memory, the asynchronous distributed system having a clock quantum constraint, Q, and a drift rate constraint, D, the clock quantum constraint indicating the maximum difference between clock quantizations among the computer systems of the asynchronous distributed system, the drift rate constraint indicating the maximum clock drift within a specified period of time for each computer system of the asynchronous distributed system, a method for determining the variance between what the observing computer system purports the time at the observed computer system to be and the actual time at the observed computer system, the method comprising:

an act of participating in one or more message exchanges with the observed computer system, the message exchanges including;

an act of recording the send time, X(t1), of the clock, X(t), at the observing computer system when a message is sent;

an act of sending a message to the observed computer system, the message including the recorded send time X(t1);

an act of subsequently receiving a correlatable message responsive to the message from the observed computer system, the correlatable message containing a time Y(t2) from the clock, Y(t), of the observed computer system;

an act of recording the received time, X(t3), of the clock, X(t) at the observing computer system when the correlatable message is received; and

an act of recording the time, Y(t2), from the observed computer system;

an act of calculating a lower bound for the time at the observed computer system relative to the time of the observing computer system based on the equation;

Y(t)>

=X(t)−

(X(t3)−

Y(t2)+2Q)−

2D(X(t)−

X(t1))/2+2Q);

an act of calculating an upper bound for the time at the observed computer system relative to the time of the observing computer system based on the equation;

Y(t)<

=X(t)+(Y(t2)−

X(t1)+2Q)+2D(X(t)−

(X(t3)+X(t1))/2+2Q);

an act of calculating the difference between the upper bound and the lower bound; and

an act of the processor calculating the maximum variance between what the observing computer system purports the time at the observed computer system to be and the actual time at the observed computer system by dividing the calculated difference by an averaging factor.

2. The method as recited in claim 1, further comprising an act of the observing computer system using the calculated maximum variance to formulate safe view of the passage of time at the observed computer system.

3. The method as recited in claim 1, further comprising an act of the observing computer system and the observed computer system agreeing on when an event occurs.

4. The method as recited in claim 3, further wherein the act of the observing computer system and the observed computer system agreeing on when an event occurs comprises an act of the observing computer system detecting the occurrence of a past event at the observed computer system.

5. The method as recited in claim 3, wherein the act of the observing computer system and the observed computer system agreeing on when an event occurs comprises an act of the observing computer system and the observed computer system agreeing on when an event will occur in the future.

6. The method as recited in claim 1, further comprising:

an act of the observing computer system participating in one or more further message exchanges with the observed computer system; and

an act of the observing computer system refining one or more of the lower bound and the upper bound based on recorded times corresponding to the one or more further message exchanges.

7. The method as recited in claim 6, further comprising:

an act of determining the elapsed time between the message exchange and the first of the one or more further message exchanges;

an act of decaying the calculated time bounds for the observed computer system prior to calculating a time range for the observed computer system, decaying the time bounds including decaying the lower bound and decaying the upper bound based on the elapsed time, the clock drift of the clock at the observing computer system, and the clock drift of the clock at the observed computer system, decaying the calculated time bounds expanding the size of the difference between the lower bound and the upper bound such that the observing computer system indicates decreased accuracy with respect to knowledge of the time at the observed computer system; and

wherein the act of calculating a time range for the observed computer system based on lower bound and upper bound of the calculated time bound comprises calculating time range for the observed computer system based on the decayed lower time bound and the decayed upper time bound.

8. The method as recited in claim 1, further comprising:

an act of increasing the maximum variance between that the observing computer system purports the time at the observed computer system to be and the actual time at the observed computer system directly proportional to the increases in elapsed time since participation in the one or more message exchanges and based at least in part on the clock drift constraint.

9. At a computer system, the computer system including a processor and system memory, a method for calculating the maximum variance between clocks at different computer systems of an asynchronous distributed system that includes a plurality of computer systems, the method comprising:

an act of accessing a clock quantum constraint, Q, the clock quantum constraint indicating the maximum difference between clock quantizations among the computer systems of the asynchronous distributed system;

an act of accessing a drift rate constraint, D, the drift rate constraint indicating the maximum clock drift within a specified period of time for each computer system of the asynchronous distributed system;

an act of accessing a maximum round trip constraint, the maximum round trip constraint indicating the maximum amount of time for a request/reply message exchange to occur between any two computer systems of the asynchronous distributed system; and

an act of the processor calculating the maximum variance, Vmax, between clocks at different computer systems of the asynchronous system based on the clock quantum constraint, the drift rate constraint, and the maximum round trip constraint according to the equation;

Vmax =((t(2)−

t(1))/2+Q+(2D*(T−

Avg(t(1), t(2))+Q)),

where t(1) is the send time of the request and t(2) is the receive time of the response at a first computer system in the asynchronous distributed system.

10. The method as recited in claim 9, wherein one or more of the clock quantum constraint and drift rate constraint are defined in a specification for the asynchronous distributed system.

11. At an observing computer system, the observing computer system including a processor and system memory, a method for indicating the time an event occurred at an observed computer system, the method comprising:

an act of participating in one or more message exchanges with the observed computer system, each message exchange including;

an act of recording the time, X(t1), of the clock, X(t), at the observing computer system when a request message is sent;

an act of sending one or more request messages to the observed computer system, each request message including a corresponding recorded send time;

an act of subsequently receiving one or more reply messages responsive to the one or more request messages from the observed computer system, each reply message containing a time, Y(t2), from the clock, Y(t), of the observed computer system; and

an act of recording the time, X(t3), of the clock at the observing computer system when a reply message is received;

an act of calculating time bounds for the clock, Y(t), of the observed computer system relative to the time, X(t), of the observing computer system based on the one or more message exchanges, the time bounds configured to be applied to the time at the observing computer system to purport a specified time range at the observed computer system subsequent to the one or more message exchanges, the time bounds including;

a lower time bound representing the bottom of the calculated time bounds, the lower time bound calculated using the equation;

Y(t)>

=X(t)−

(X(t3)−

Y(t2)+2Q)−

2D(X(t)−

X(t1))/2+2Q); and

an upper time bound representing the top of the calculated time bounds, the upper time bound calculated using the equation;

Y(t)<

=X(t)+(Y(t2)−

X(t1)+2Q)+2D(X(t)−

(X(t3)+X(t1))/2+2Q);

an act of the processor receiving an indication, the indication selected from among;

a) an indication of the occurrence of a past event at the observed computer system and b) an indication of when an event is to occur at the observed computer system, subsequent to the one or more message exchanges;

an act of the processor calculating a time range for the observed computer system, the time range indicative of a) when the event occurred or b) when the event is to occur at the observed computer system, the time range calculated based on a time at the observing computer system when the indication was received and based on the lower bound and the upper bound of the calculated time bound; and

an act of sending an event message including the indication and the calculated time range to one or more other computer systems.

12. The method as recited in claim 11, wherein the act of calculating time bounds for the observed computer system relative to the time of the observing computer system based on the one or more messages comprises an act of setting the lower bound to a value based at least in part on the smallest difference between the time recorded for sending a request message and the time from the observed computer system included in a corresponding reply message in any of the one or more message exchanges.

13. The method as recited in claim 12, wherein the act of setting the lower bound to a value comprises an act of setting the lower bound to a value based at least in part on an indication of a difference between the quantization of the clock at the observing computer system and the quantization of the clock at the observed computer system.

14. The method as recited in claim 12, wherein the act of setting the lower bound to a value comprises an act of setting the lower bound to a value based at least in part on the clock drift of the clock at the observing computer system and the clock drift of the clock at the observed computer system.

15. The method as recited in claim 11, wherein that act of calculating time bounds for the observed computer system relative to the time of the observing computer system based on the one or more request/reply messages comprises an act of setting the upper bound to a value based at least in part on the smallest difference between the time recorded for receiving a reply message and the time from the observed computer system included in the reply message in any of the one or more request/reply message exchanges.

16. The method as recited in claim 15, wherein the act of setting the upper bound to a value comprises an act of setting the upper bound to a value based at least in part on an indication of a difference between the quantization of the clock at the observing computer system and the quantization of the clock at the observed computer system.

17. The method as recited in claim 15, wherein the act of setting the upper bound to a value comprises an act of setting the upper bound to a value based at least in part on the clock drift of the clock at the observing computer system and the clock drift of the clock at the observed computer system.

18. The method as recited in claim 11, further comprising:

an act of determining the elapsed time between the last message exchange of the one or more message exchanges and the time the indication of the occurrence of the event was received;

an act of decaying the calculated time bounds for the observed computer system prior to calculating a time range for the observed computer system, decaying the time bounds including decaying the lower bound and decaying the upper bound based on the elapsed time, the clock drift of the clock at the observing computer system, and the clock drift of the clock at the observed computer system, decaying the calculated time bounds expanding the size of the difference between the lower bound and the upper bound such that the observing computer system indicates decreased accuracy with respect to knowledge of the time at the observed computer system; and

wherein the act of calculating a time range for the observed computer system based on lower bound and upper bound of the calculated time bound comprises calculating time range for the observed computer system based on the decayed lower time bound and the decayed upper time bound.

19. The method as recited in claim 18, further comprising:

an act of the observing computer system participating in a second one or more request/reply message exchanges with the observed computer system subsequent to sending the event message; and

an act of the observing computer system refining the value of at least one of the decayed lower bound and the decayed upper bound in response to participating in the second one or more message exchanges so as to indicate increased accuracy with respect to knowledge of the time at the observed computer system.

20. The method as recited in claim 11, further comprising:

an act of the observed computer system participating in the one or more message exchanges including for each message exchange;

an act of receiving a request message to the observed computer system;

an act of inserting a time for the clock at the observing computer system into a reply message responsive to the received request message; and

an act of sending the reply message to the observing computer system.

21. The method as recited in claim 20, wherein the act of inserting a time for the clock at the observing computer system into a reply message comprises an act of the observed computer system inserting a time indicative of when the received request message from processed at the observed computer system.

22. The method as recited in claim 11, wherein the asynchronous distributed system is a peer-to-peer system.