Lamport Clocks

We looked at Logical Time in the previous article and how it can help us reason about time in a single machine. Let's now think about how we can think about this in a distributed system.

Consider sending an email to a friend and having him read it. If we think about it, any action you took before sending the email, such as writing it, checking for grammatical errors, and attaching an attachment, must have occurred prior to your friend reading the email, as must any action that follows it, such as forwarding the mail to someone else and printing it.

Logical Time is simply a counter that is incremented from an arbitrary point in time for a specific node. It means that the logical timestamps of two distinct machines cannot be compared.

If this is the case, how do we determine the order of these events when logical timestamps cannot be compared?

Lamport Clocks

The Lamport Clock, invented by Leslie Lamport, was one of the first and simplest types of Logical Clocks.

This is how Lamport Clocks function.

1. When a node is first started, it keeps a local logical time that starts at zero.
2. Prior to performing an event, the node increases its local logical time counter by one ('Ci = Ci + 1').
3. The incremented logical timestamp is sent along with the message when it is sent over the network.
4. The message's receiver does the following:
   1. It updates its own Logical Clock with the maximum of its own time and the time of the received message.
   2. It performs the required action

This allows us to directly compare and order the logical timestamps of multiple nodes.

The order is determined by

1. If the timestamp of Event A is less than Event B, then Event A happened before Event B
2. If the timestamps are same, then they are concurrent.

Lamports clocks are designed for a Crash Stop model, but they are simple to implement in a Crash Recovery model where the timestamp must be persisted on disk.

Pseduo Code for Lamport Clocks

on initialisation do
    t := 0
end on

on any event occuring in the node do
    t := t + 1
end on

on request to send message m do
    t := t + 1;
    send_message(m, t)
end on

on receiving (m, t1) do
    t := max(t, t1) + 1
    process_message(m)
end on

Limitations of Lamport Clocks

Lamport Clocks are easy to implement and assist us in reasoning about the happens before relationship in a distributed system.

According to Lamport Clocks, if Event A caused Event B, then Event A's Lamport Time will be less than Event B's. However, we cannot reverse it and say that if Event A's timestamp is less than Event B's, then they are causally related.

Because Lamport Timestamps cannot be used to infer causal relationships, we require a new type of Logical Clock that can assist us in determining causal relationships.

In the next article, we'll look at Vector Clocks, which will help us detect causal relationships.