Lamport Clocks

Leslie Lamport invented one of the first and simplest types of logical clocks, called the Lamport clockL. Lamport, “Time, Clocks, and the Ordering of Events in a Distributed System,” Communications of the ACM 21, 7 July 1978, 1978..

In this type of logical clock, every node in the system maintains a logical clock in the form of a numeric counter that starts from zero when a node starts operating.

Rules of the protocol

• (R1) Before executing an event (send, receive, or local), a node increments the counter of its logical clock by one: $C_i = C_i + 1$.
• (R2) Every sent message piggybacks the clock value of its sender at sending time. When a node $n_i$ receives a message with timestamp $C_{msg}$, it executes the following actions:
  • Updates its clock by taking the maximum of its clock and the received clock: $C_i = max(C_i, C_{msg})$
  • Executes R1
  • Delivers the message