System and method for clock-synchronization in distributed systems

1. A method for synchronizing distributed processors comprising the steps of:

establishing a socket-connection between at least two processors;

determining a roundtrip delay;

determining a roundtrip-delay threshold;

determining a current round-trip delay and an offset;

adding the current round-trip delay to a list of roundtrip delays;

determining a new roundtrip-delay threshold;

determining whether the current roundtrip delay is greater than the new roundtrip-delay threshold;

determining whether a desired number of round-trip delays have been determined upon determining the current roundtrip delay to be greater than the new roundtrip-delay threshold; and

determining whether the offset is greater than an offset threshold, adjusting a clock according to whether the offset is greater than the offset threshold and determining a linear regression upon determining that the current roundtrip delay is not greater than the new roundtrip-delay threshold.

2. The method of claim 1 , wherein a probability of the round-trip delay being greater than the roundtrip-delay threshold is about 0.5 and a probability of the round-trip delay being less than the roundtrip-delay threshold is about 0.5.

3. The method of claim 1 , wherein the step of determining whether the desired number of round-trip delays have been determined further comprises the step of entering a synchronization method upon determining the desired number round-trip delays.

4. The method of claim 1 , wherein the step of determining whether the desired number of round-trip delays have been determined further comprises recursively performing the step of determining the current round-trip delay and an offset upon determining less than the desired number delays.

5. The method of claim 1 , wherein the step of adjusting the clock according to whether the offset is greater than the offset threshold further comprises the steps of:

decrementing by an update-interval upon determining the offset to be greater than the offset threshold; and

incrementing by the update-interval upon determining the offset to be less than the offset threshold.

6. The method of claim 1 , further comprising recursively performing the step of determining the current round-trip delay and the offset.

7. The method of claim 1 , wherein the step of determining the linear regression further comprises the steps of:

setting a current synchronization time;

determining whether a number of measured offsets is greater than a desired number:

upon determining that the number of measured offsets is greater than the desired number, removing an oldest offset from a list of offsets and adding a current offset to the list of offsets and determining parameters of the linear regression from the list of offsets;

upon determining that the number of measured offsets is not greater than the desired number, adding the current offset to the list of offsets;

estimating the current offset using the linear regression;

incrementing the current synchronization time; and

determining whether the current synchronization time is greater than an update-interval:

upon determining the current synchronization time to be less than the update-interval, re-estimating the current offset using the linear regression;

upon determining the current synchronization time to be greater than the update-interval, re-determining the current roundtrip delay and the current offset.

8. The method of claim 1 , wherein the desired number of roundtrip delays is thirty.

9. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for synchronizing distributed processors, the method steps comprising:

establishing a socket-connection between at least two processors;

determining a roundtrip delay;

determining a roundtrip-delay threshold;

determining a current round-trip delay and an offset;

adding the current round-trip delay to a list of roundtrip delays;

determining a new roundtrip-delay threshold;

determining whether the current roundtrip delay is greater than the new roundtrip-delay threshold;

determining whether a desired number of round-trip delays have been determined upon determining the current roundtrip delay to be greater than the new roundtrip-delay threshold; and

determining whether the offset is greater than an offset threshold, adjusting a clock according to whether the offset is greater than the offset threshold and determining a linear regression upon determining that the current roundtrip delay is not greater than the new roundtrip-delay threshold.

10. The method of claim 9 , wherein a probability of the round-trip delay being greater than the roundtrip-delay threshold is about 0.5 and a probability of the round-trip delay being less than the roundtrip-delay threshold is about 0.5.

11. The method of claim 9 , wherein the step of determining whether the desired number of round-trip delays have been determined further comprises the step of entering a synchronization method upon determining the desired number round-trip delays.

12. The method of claim 9 , wherein the step of determining whether the desired number of round-trip delays have been determined further comprises recursively performing the step of determining the current round-trip delay and an offset upon determining less than the desired number delays.

13. The method of claim 9 , wherein the step of adjusting the clock according to whether the offset is greater than the offset threshold further comprises the steps of:

decrementing by an update-interval upon determining the offset to be greater than the offset threshold; and

incrementing by the update-interval upon determining the offset to be less than the offset threshold.

14. The method of claim 9 , further comprising recursively performing the step of determining the current round-trip delay and the offset.

15. The method of claim 9 , wherein the step of determining the linear regression further comprises the steps of:

setting a current synchronization time;

determining whether a number of measured offsets is greater than a desired number:

upon determining that the number of measured offsets is greater than the desired number, removing an oldest offset from a list of offsets and adding a current offset to the list of offsets and determining parameters of the linear regression from the list of offsets;

upon determining that the number of measured offsets is not greater than the desired number, adding the current offset to the list of offsets;

estimating the current offset using the linear regression;

incrementing the current synchronization time; and

determining whether the current synchronization time is greater than an update-interval:

upon determining the current synchronization time to be less than the update-interval, re-estimating the current offset using the linear regression;

upon determining the current synchronization time to be greater than the update-interval, re-determining the current roundtrip delay and the current offset.