Generating globally coherent timestamps

• US 9,915,970 B1
• Filed: 10/28/2015
• Issued: 03/13/2018
• Est. Priority Date: 05/18/2012
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google LLC (Alphabet Inc.)
• Inventors: Hochschild, Peter, Lloyd, Alexander, Hsieh, Wilson Cheng-Yi, Felderman, Robert Edman, Epstein, Michael James Boyer
• Primary Examiner(s): Bae, Ji H
• Application Number:
  US14/925,278
• Time in Patent Office: 867 Days
• Field of Search: 713401, 713375, 713400, 713503, 709248
• CPC Class Codes: G01S 19/01 Satellite radio beacon positioning systems transmitting time-stamped messages, e.g. GPS [Global Positioning System], GLONASS [Global Orbiting Navigation Satellite System] or GALILEO
• CPC Class Codes: G06F 1/12 Synchronisation of different clock signals provided by a plurality of clock generators
• CPC Class Codes: G06F 11/1675 Temporal synchronisation or re-synchronisation of redundant processing components
• CPC Class Codes: H04J 3/0661 using timestamps
• 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
• CPC Class Codes: H04L 43/106 using time related information in packets, e.g. by adding timestamps
• CPC Class Codes: H04L 67/10 in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46
• CPC Class Codes: H04L 7/0008 Synchronisation information channels, e.g. clock distribution lines
• CPC Class Codes: H04L 7/0012 by comparing receiver clock with transmitter clock
• CPC Class Codes: H04L 7/0016 correction of synchronization errors

Abstract

The present technology proposes techniques for generating globally coherent timestamps. This technology may allow distributed systems to causally order transactions without incurring various types of communication delays inherent in explicit synchronization. By globally deploying a number of time masters that are based on various types of time references, the time masters may serve as primary time references. Through an interactive interface, the techniques may track, calculate and record data relative to each time master thus providing the distributed systems with causal timestamps.

Claims

1. A method of synchronizing a host machine, comprising:

querying a subset of time masters;

voting, with one or more processors, on results of the querying;

determining, with the one or more processors based on the voting, which time masters are producing accurate current timestamps;

accepting information from time masters producing accurate timestamps;

rejecting information from time masters not producing accurate current timestamps;

determining, with the one or more processors, an order for transaction events based on the accepted information; and

assigning a timestamp to a transaction based on the determined order for the transaction events.

2. The method of claim 1, wherein the current timestamps are determined to be accurate if they are within an uncertainty range relative to the subset of time masters.

3. The method of claim 1, further comprising:

receiving responses from the subset of time masters; and

associating the responses with local timestamps denoting a time the response was received.

4. The method of claim 3, further comprising calculating a time offset interval for a given time master, the time offset interval representing transmission delays associated with the queries to and responses from the given time master.

5. The method of claim 3, further comprising:

determining whether a response was received from each time master in the subset of time masters; and

resending the query to each time master for which a response was not received.

6. The method of claim 4, wherein the voting comprises:

calculating the time offset interval for each time master;

analyzing an aggregate of the time offset intervals for each time master;

determining a smallest offset interval consistent among a selected group of the time masters; and

assigning the smallest offset interval as an agreement validated offset interval for the selected group.

7. A system, comprising:

memory;

one or more processors in communication with the memory and programmed to;

query a subset of time masters;

vote on the results of the query;

determine, based on the voting, which time masters are producing accurate current timestamps, wherein the current timestamps are determined to be accurate if they are within an uncertainty range relative to the subset of time masters;

accept information from time masters producing accurate timestamps;

reject information from time masters not producing accurate current timestamps;

determine an order for transaction events based on the accepted information; and

assign a timestamp to a transaction based on the determined order for the transaction events.

8. The system of claim 7, wherein the one or more processors are further programmed to:

receive responses from the subset of time masters; and

associate the responses with local timestamps denoting a time the response was received.

9. The system of claim 7, wherein the one or more processors are further programmed to:

calculating a time offset interval for each time master, each time offset interval representing transmission delays associated with the requests to and from a given time master;

analyzing an aggregate of the time master offset intervals;

determining a smallest offset interval consistent among a selected group of the time masters; and

assigning the smallest offset interval as an agreement validated offset interval for the selected group.