Time, Clocks, and the Ordering of Events in a Distributed System

Leslie Lamport

If you know about distributed systems, abstract algebra, and special
relativity (general relativity helps for one footnote), this is a really
cool paper.

   * a distributed system is one where the message transmission delay is not
     negligible compared to the time between events
   * in such a system, it is sometimes impossible to say that one of two
     events occurred before the other; sometimes, not all pairs of events
     can be causally related
        o a distributed system is composed of processes, which are sequences
          of events that happen in some specified order (such as the
          execution of a thread, where events are executions of individual
          instructions)
        o processes communicate via messages
        o define a partial order --> ("happened before") on the set of
          events by a-->b if a and b are events in the same process and a
          happenes before b, or if a is the sending of a message by one
          process and b is the receiving of that message by another process;
          also, if a-->b and b-->c then a-->c
        o note that only if a-->b can a causally affect b (through the
          system); events a and b for which a-/>b and b-/>a are said to be
          concurrent
   * we would like this partial ordering to be extended to a total ordering,
     to solve some synchronization problems; e.g.
        o A and B are clients, S is a server; A and B use some resource R
          that S can only give to one client at a time
        o A sends a message to S requesting R, then sends a message to B,
          then B sends a message to S requesting R; S receives the message
          from B before it receives the one from A
        o we would like S to grant A's request first, as it may affect B's
          request
   * this can be achieved in many ways; for example, through the use of
     logical per-process clocks (which increment for events within a process
     and synchronize during messages)
   * however, this can cause "anomalous behaviour" if causal relationships
     happen outside of the system (user A causes event; A telephones B; B
     causes event), unless users keep in mind that events only have a
     partial order defined by causality
   * solution: base the total order on "real" time using physical clocks
   * assuming the clock rates are all approximately equal, and some bounds
     can be put on the properties of transmission times of messages, the
     paper shows how to quickly synchronize the all of the clocks in a
     distributed system, so that the total order that they induce causes no
     surprises to users (cf: xntp)