Lamport Clocks

Let's examine what Lamport clocks are and how they work.

We'll cover the following

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: Ci=Ci+1C_i = C_i + 1.
  • (R2) Every sent message piggybacks the clock value of its sender at sending time. When a node nin_i receives a message with timestamp CmsgC_{msg}, it executes the following actions:
    • Updates its clock by taking the maximum of its clock and the received clock: Ci=max(Ci,Cmsg)C_i = max(C_i, C_{msg})
    • Executes R1
    • Delivers the message

Clock consistency condition

The Lamport clocks satisfy the so-called clock consistency condition.

If one event e1e_1 causally precedes another event e2e_2, then C(e1)<C(e2)C(e_1) < C(e_2). However, the reverse which is the strong consistency condition, is not satisfied by Lamport clocks. This means that if C(e1)<C(e2)C(e_1) < C(e_2), then this does not necessarily mean that the event e1e_1 causally precedes e2e_2. As a result, this means that Lamport clocks cannot be used to infer partial orderings that are causally consistent.

However, they can still be used for other purposes, such as creating (non causally consistent) total orderings.

Working of Lamport clocks

To understand better how Lamport clocks work, let’s look at the example in the following illustration. We have a distributed system consisting of three nodes A, B, and C, which execute events locally and exchange messages to propagate the necessary information across the whole system. We can try running the rules described above and see that the clocks of each node are updated, as shown in the illustration.

Essentially, each node ticks its clock as local events happen and bumps the clock if it identifies that another node has a higher clock value than that node’s value.

Now, let’s discuss the conditions presented previously in more detail.

Any two events that are causally related will reflect this relationship in the clock’s value. For instance, A1A_1 causally precedes B1B_1 and we can see that C(A1)=1<2=C(B1)C(A_1) = 1 < 2 = C(B_1) (clock consistency condition).

We can also see that the strong consistency condition does not hold. For instance, C(C2)<C(B2)C(C_2) < C(B_2), but these two events are not causally dependent. Event B2B_2 could have happened either before or after C2C_2 with the same clock value.

Usage of Lamport clocks

Lamport clocks can be used to create a total ordering of events in a distributed system using some arbitrary mechanism to break ties in case clocks of different nodes have the same value (e.g. the ID of the node).

The caveat is that this total ordering is somewhat arbitrary and cannot infer causal relationships. This limits the number of practical applications that Lamport clocks can have. The paperL. Lamport, “Time, Clocks, and the Ordering of Events in a Distributed System,” Communications of the ACM 21, 7 July 1978, 1978. demonstrates how they could potentially be used to solve synchronisation problems, such as mutual exclusion.

Get hands-on with 1400+ tech skills courses.