Nimendra's Notes 🪴

Time, Clocks, and the Ordering of Events in a DS

4 min read

distributedsystem dissectingresearchpapers

Lamport Clock
Tick Tock, Who’s in Sync? Logical & Vector Clock Implementation From Scratch
Lamport clocks
Time, clocks, and order. - by Dean Eigenmann

The Problem

An “Event” could be created after something important happened in our system.

  • e.g - Some instruction executed

In our distributed system, assume we have a central authority that wants to know which of two events happened first.

The first thought could be to have both processes append the current timestamp to the event before forwarding it to the central authority. That could work in theory, but the problem is that the timestamp is derived by a physical chip running on two different machines. Even just getting them synchronized is hard; using NTP, for example, it will carry some error. Assuming an operator did not mistakenly set the wrong time, they still are subjected to an effect called “clock drifting” that would cause them to go out of sync over time.

the paper tries to answer this question:

  • can we find which event happened first without using a physical clock? As we shall see, the answer is not always.
  • The second part of the paper strengthens the properties of the first part by introducing physical clocks.

It Happened Before !!

Causality means that one event influences or causes another. In distributed systems, message passing is the key way that events in different processes are causally related.

Leslie Lamport defined the “happened-before” relation (→) to capture causality.

We know for a fact that a message must be sent before it can be received.
So we can be sure that sending a message happened before it was received, giving a “happened before” relationship in the context of these two events. This relationship can therefore be recognized without needing the notion of time in a system: we can say that event A happened before event B, if A causally affected B.

An event A happened before B (written as A --> B if):

  1. Same process: If A occurs before B in the same process.
  2. Message send and receive: If A is the send of a message and B is the receive of that same message.
  3. Transitivity: If A → B and B → C, then A → C.
    • If event A caused event B (A → B),
    • And event B caused event C (B → C),
    • Then event A also caused event C (A → C).

These define causal order. Anything outside this relation is considered concurrent.

  • If event A caused event B (directly or indirectly), then A must be ordered before B.
  • Events not related by causal order are either concurrent or independent.
sequenceDiagram
    participant P1
    participant P2
    participant P3

    %% Internal event at P1
    P1->>P1: "e1 [LC=1]"
    P1->>P2: "send m1 [LC=2]"
    Note right of P1: "P1 clock = 2"

    P2->>P2: "recv m1 [LC=3]"
    P2->>P2: "e4 (internal) [LC=4]"
    P2->>P3: "send m2 [LC=5]"

    P3->>P3: "recv m2 [LC=6]"
    P3->>P3: "e7 (internal) [LC=7]"

    %% Concurrent events example
    P1->>P1: "e8 (internal) [LC=3]"
    P3->>P3: "e9 (internal) [LC=8]"
    Note over P1,P3: "e8 || e9 (concurrent)"

Each vertical line represents a separate process (P, Q, R) executing events over time.
Each dot represents an event (e.g., p1, q3, r2), and wavy arrows represent message passing from one process to another.

Time flows from bottom to top

  • p1 sends a message that is received at q2
    → So: p1 → q2
  • q2 → q3 → q4 → q5 → q6 → q7
    (Events in the same process are causally ordered)
  • q4 sends a message received at r3
    → So: q4 → r3

From above:

  • p1 → q2 → q4 → r3

Transitivity:

  • p1 → r3 (even though there’s no direct arrow between them)

Some events are not causally related — they are concurrent.
Example:

  • p3 and r2 are concurrent:
    • No message connects them
    • No causal path between them
      So: p3 || r2

Backlinks

Graph View