US 7,454,521 B2Granted

Byzantine fault quantifying clock synchronization

AssigneeMicrosoft Corporation

InventorsJonathan R. Howell, John R. Douceur

Life of this patent

Estimating the term…

Loading patent…

Abstract

The clocks of remote computing devices are synchronized within a range of certainty through the determination of an upper bound and a lower bound around a reference time. A message from a computing device is propagated up a network tree of devices to a device having a reference time, which encodes the reference time and returns the message down the tree. Each receiving device can determine that the reference time could not have occurred before their transmission of the message, nor could it have occurred after their receipt of the return message. Cryptographic hashes can be used to guard against malicious computing devices. Alternate paths and scheduling of messages can be used to provide a narrower spread between the upper and lower bounds, and clock drift can be accounted for by increasing the spread over time.

Claims19

Dependent claims

A method for determining a bound around a reference time such that the reference time is determined to have occurred between a first bound limit and a second bound limit, the method comprising the steps of:

transmitting a protected reference time request from a first computing device to a higher level computing device, wherein the higher level computing device is a level closer to a reference time source;
storing a transmittal time, according to a clock of the first computing device, when the protected reference time request was transmitted to the higher level computing device;
receiving a response from the higher level computing device at the first computing device, the response comprising a protected reference time source response, the reference time source response comprising the reference time, and a collection of protected reference time requests from each first level computing device that had transmitted the collection of protected reference time requests to the reference time source prior to the reference time;
storing a receipt time, according to the clock of the first computing device, when the response from the higher level computing device was received at the first computing device;
setting the first bound limit at the transmittal time when the protected reference time request was transmitted to the higher level computing device;
and
setting the second bound limit at the receipt time when the response from the higher level computing device was received.

4 more elements

A computer-readable storage medium having computer-executable instructions for determining a bound around a reference time such that the reference time is determined to have occurred between a first bound limit and a second bound limit, the computer-executable instructions performing steps comprising:

transmitting a protected reference time request from a first computing device to a higher level computing device, wherein the higher level computing device is a level closer to a reference time source;
storing a transmittal time, according to a clock of the first computing device, when the protected reference time request was transmitted to the higher level computing device;
receiving a response from the higher level computing device at the first computing device, the response comprising a protected reference time source response, the reference time source response comprising the reference time, and a collection of protected reference time requests from each first level computing device that had transmitted the collection of protected reference time requests to the reference time source prior to the reference time;
storing a receipt time, according to the clock of the first computing device, when the response from the higher level computing device was received at the first computing device;
setting the first bound limit at the transmittal time when the protected reference time request was transmitted to the higher level computing device;
and
setting the second bound limit at the receipt time when the response from the higher level computing device was received.

4 more elements

Dependencies are inferred from the claim text.

Facts

Application: 10/694,596Filed 23 Oct 2003
Published: US 2005/0089131 A128 Apr 2005
Granted: 18 Nov 2008
Term ends: Not estimatedThe source records don’t support an estimate.

Classification6 codes

H04L 63/126
Applying verification of the received information: the source of the received data
G06F 1/12
Generating or distributing clock signals or signals derived directly therefrom: synchronisation of different clock signals provided by a plurality…
G06F 1/14
Generating or distributing clock signals or signals derived directly therefrom: time supervision arrangements, e.g. real time clock
G06F 21/725
In cryptographic circuits: operating on a secure reference time value