3 ms·

I've noticed that recent google infrastructure puts medium-to-strict requirements on timeservers. Does that mean that the idea of causality and vector clocks ha

by sqrt17 12y ago

I've noticed that recent google infrastructure puts medium-to-strict requirements on timeservers. Does that mean that the idea of causality and vector clocks has been abandoned partly or wholly for a greater reliance on absolute synchronicity?

mjb 12y ago
I don't think that's true. The ideas of causality, logical clocks and vector clocks have not been abandoned in any sense. In fact, there seems to be significant new interest in eventually consistent systems over the last few years, and interest in vector clocks and highly available (in the CAP 'AP' sense) systems is still growing. The excitement about research into CRDTs is a good illustration of this. More fundamentally, though, Spanner doesn't involve absolute synchronicity in any real sense. Instead, at least as described in their paper, the focus is on using the special clocks to improve some system properties by bounding absolute clock skew. The ideas of causally related operations, and the orderings between these operations, is still important even in that environment.
abeppu 12y ago
I recently reread the Lamport paper discussed in the article, and the Google Spanner paper, to draw comparisons about the relationship between time, consistency and throughput from those two perspectives. The Lamport paper does dedicate its last real section to physical clocks which need to sync with one another, and which must advance at close to the same rate in order to maintain consistency -- but he doesn't constrain them to be close to any "absolute" correct time, which is what the Spanner / TrueTime system heavily relies on. My tentative conclusion was that the giant difference between 1978 when the Lamport clocks paper was published, and 2012, is access to GPS. The fact that we get to take advantage of a DoD-built fleet of dozens of satellites that are constantly broadcasting extremely accurate times is pretty extravagant. Google can build systems today that rely on clocks in data-centers thousands of miles apart both being very close to "absolute" time, with explicit, conservative bounds on their error, in part through heavy use of GPS clocks. But for most of us that don't have an elaborate system of fancy clocks in our data-centers, Lamport's approach of having machines update one another's clocks (be they logical or physical) as they exchange messages is still a lot more relevant.
- makmanalp 12y ago
  I wonder if this means that an evil entity could cause massive data loss by broadcasting fake GPS clock information, which would mess around with the decisions that these databases make regarding consistency. That would be terrifying.
  - abeppu 12y ago
    The spanner paper doesn't discuss this in detail, but they have atomic clocks in addition to GPS clocks in large part because GPS clocks can fail or be expoited in this way and atomic clocks cannot.
- justicezyx 12y ago
  Spanner has "interval" in its time. It uses high-accuracy atomic clocks to narrow the uncertainty window. It actually proves that Lamport's technique is more fundamental, because even with such hardware, you still can run into situation where the system has no idea what the order of events is.

by sqrt17 12y ago

mjb 12y ago

I don't think that's true. The ideas of causality, logical clocks and vector clocks have not been abandoned in any sense. In fact, there seems to be significant new interest in eventually consistent systems over the last few years, and interest in vector clocks and highly available (in the CAP 'AP' sense) systems is still growing. The excitement about research into CRDTs is a good illustration of this. More fundamentally, though, Spanner doesn't involve absolute synchronicity in any real sense. Instead, at least as described in their paper, the focus is on using the special clocks to improve some system properties by bounding absolute clock skew. The ideas of causally related operations, and the orderings between these operations, is still important even in that environment.

abeppu 12y ago

I recently reread the Lamport paper discussed in the article, and the Google Spanner paper, to draw comparisons about the relationship between time, consistency and throughput from those two perspectives. The Lamport paper does dedicate its last real section to physical clocks which need to sync with one another, and which must advance at close to the same rate in order to maintain consistency -- but he doesn't constrain them to be close to any "absolute" correct time, which is what the Spanner / TrueTime system heavily relies on. My tentative conclusion was that the giant difference between 1978 when the Lamport clocks paper was published, and 2012, is access to GPS. The fact that we get to take advantage of a DoD-built fleet of dozens of satellites that are constantly broadcasting extremely accurate times is pretty extravagant. Google can build systems today that rely on clocks in data-centers thousands of miles apart both being very close to "absolute" time, with explicit, conservative bounds on their error, in part through heavy use of GPS clocks. But for most of us that don't have an elaborate system of fancy clocks in our data-centers, Lamport's approach of having machines update one another's clocks (be they logical or physical) as they exchange messages is still a lot more relevant.

makmanalp 12y ago
I wonder if this means that an evil entity could cause massive data loss by broadcasting fake GPS clock information, which would mess around with the decisions that these databases make regarding consistency. That would be terrifying.
- abeppu 12y ago
  The spanner paper doesn't discuss this in detail, but they have atomic clocks in addition to GPS clocks in large part because GPS clocks can fail or be expoited in this way and atomic clocks cannot.
justicezyx 12y ago
Spanner has "interval" in its time. It uses high-accuracy atomic clocks to narrow the uncertainty window. It actually proves that Lamport's technique is more fundamental, because even with such hardware, you still can run into situation where the system has no idea what the order of events is.