Reading Lamport, again

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.

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.

> Imagine if the instructions in one of your program threads were not guaranteed to be executed in order.

Modern CPUs do not process instructions in the same order they are stored in memory. Out-of-order CPUs rely on the implicit order created by the dependency between instructions and operands.

As in the Lamport paper, the order in which the instruction are performed is meant to preserve the order in which the effects are produced instead of the order in which the commands are given.

The causal ordering defined in the paper is stronger than that. It says that if process P performs event A and later sends a message to process Q, then any event that occurs in Q after Q receives the message causally follows A. I don't think the blog post was meant to imply that the order of events within a single process does not need to be respected, though it doesn't specifically distinguish the single process case.