In a comment on my “right to be forgotten” proposal I mentioned causality tracking (so eg. figuring out whether event A happened before or after event B) in distributed networks as an example of a hard problem, and I figured I’d share a blog post (not mine) on one of the more modern techniques that’s still very much underutilized. This class of algorithms is called logical clocks, and the first of them was the Lamport timestamp by Leslie Lamport. Note that many of these algorithms can be used for tracking version changes and not just logical time, often with some changes like in the case of interval tree clocks.

In many cases just plopping a timestamp on a message and using that to establish causality isn’t good enough. If you rely on clients to attach that timestamp, you have to trust that their clocks are correct, or that they don’t simply lie about the time for whatever reason (although of course that’s a problem with logical clocks too.) Also, you might not want to base your causality on when a message was sent but on when it was received; even if message A is sent before message B, there’s no telling whether A actually makes it to your system before B does. These are just a few common reasons for needing logical clocks, and they’re necessary in a surprising amount of cases when you deal with distributed systems.

The advantage of interval tree clocks compared to eg. vector clocks is that they’re designed to work well in networks where participants are constantly leaving and coming back online and where you can’t know the number of nodes in the network beforehand. These are cases most other algorithms don’t deal with too well. Of course this means more complexity in the algorithm, but this is a case of “them’s the breaks” as the problem is definitely not a simple one to solve.