↓Skip to main content

Logical clocks

·2 mins
  • Physical clocks aren’t reliable in a distributed system. (Basically, assume that each server has different timestamps all the time.) Therefore, logical clocks help. Two main algorithms:
    • Lamport clocks.
    • Version vectors. (Somewhat related to but different from “version clocks”. Haven’t dug into details though.)
  • What are “events”?
    • Server receives a message or request from a client.
    • Inter-server communication (i.e. when a server receives message from another server).
  • On differences, I won’t describe how the two algorithms work as that would be too much stuff to write down. However, I’ll describe key implications of the two.
    • Lamport clocks.
      • If a happened-before b, it implies L(a) < L(b).
        • However, if you are given L(a) and L(b) such that L(a) < L(b), all that means is b did not happen-before a. You can’t deduce anything else.
      • If you have a bunch of events, you can deduce a total order which is consistent with causality. So, if two events had a happened-before relationship, they will be ordered correctly in the result. However, you can’t pick any two events from the order and deduce that the one earlier had happened-before the other.
        • Basically, the total order is some order which is consistent with causality. It is not the actual order in which events occured in physical time.
    • Version vectors.
      • Each data record is associated with a vector. Each element in the vector is associated with a server that had processed that record.
      • a -> b implies V(a) < V(b), both ways. That’s the key difference from Lamport clocks.
        • Given any two events and their version vectors, you can identify whether one of them happened-before the other or they were concurrent.
  • Important note: happens-before has nothing to with whether one event happened before the other in physical time. Instead, it means whether they are causally connected: one caused the other.

Helpful resources: