This is the first of two notes for Lamport’s Time-Clock paper.

Abstract

Order is a more basic concept than Time. And it’s critical to how we reason. However physical time, which even though gives us total ordering on all events, cannot be observed within the system. So, we introduced a Logical Clock which satisfies Clock Condition, which is observable in the system.

Time

Time is something we experience in our physical world. E.g. we saw there’s day and night, and we call the interval between two instants when the sun is at its highest “a day”. We noticed certain repetitive physical processes that repeat themselves in equal intervals (e.g. the interval between two consecutive instants when a pendulum reaches its highest) and we use that to be certain basic unit to quantify time i.e. a second. And a clock was made. Clock (or a function from event to time) was made from our observation of the physical world.

Order

Ordering (order here is the same as happen-before/happen-after relationship between events) is fundamental to our way of thinking in system. E.g. you can only withdraw $500 before your bank balance drop below $500. Your remaining balance after the transaction will be whatever was there subtract $500. We have total ordering for events in a single process system, consistent with our experience of time. All events in everyone's notion of time and space are totally ordered by time. Hence, it's easier for us to reason about a single process system than a distributed system.

Happened-before

The approach we are going to take is to first define a partial order that’s consistent with physical time, which is observable. On top of it, we define a total order, which is consistent with the partial order, which is also observable. Notice that this doesn’t mean the total order is consistent with the total order from physical time.

  • if A is the sending of a message on p0 and B is the receiving of the same message on p1, A -> B
  • if A -> B and B -> C, then A -> C

Software Engineer at Facebook working on cache infrastructure