Back
+20 XP
Concept

Logical Clocks & Causal Ordering: Lamport Timestamps

Physical wall clocks drift unpredictably due to NTP skew and hardware quartz variance. Lamport Logical Clocks replace physical timestamps with a monotonically increasing integer counter, updating to $\max(\text{local}, \text{remote}) + 1$ upon receiving messages to maintain causal order ⏱️📜.

python
class LamportClock:
    def __init__(self, node_id):
        self.node_id = node_id
        self.time = 0

    def step_local(self):
        self.time += 1
        return self.time

    def step_receive(self, remote_time):
        # Ensure causal ordering: happens-after relationship
        self.time = max(self.time, remote_time) + 1
        return self.time

clock_a = LamportClock("Node_A")
clock_b = LamportClock("Node_B")

msg_timestamp = clock_a.step_local() # A sends at time 1
arrival_time = clock_b.step_receive(msg_timestamp) # B receives at time 2
print(f"Node B clock updated: {arrival_time} ⏱️")

# 32. Logical Clocks & Causal Ordering: Lamport Timestamps If Server A writes `balance = 50` at 12:00:00.002 and Server B writes `balance = 0` at 12:00:00.001, but Server A's clock was running 5ms slow, a database using wall clocks will overwrite the newer value with an older one 🛑. ```python # The "Happens-Before" (->) Relation: # If event a happens before b in the same process: a -> b # If a is the sending of a message and b is receipt: a -> b # If a -> b and b -> c: a -> c (transitivity) ``` ### The Lamport Invariant 1. **Local Increment**: Before executing an internal event or sending a message, advance clock: $C_i = C_i + 1$. 2. **Message Tagging**: Every outbound network packet carries the sender's current clock value $C_i$. 3. **Causal Synchronization**: When receiving message with timestamp $T$, the recipient adjusts: $$C_j = \max(C_j, T) + 1$$ This guarantees that if $a \to b$, then $C(a) < C(b)$ 🎯. --- ### Interactive Pop-Quiz 🧠 #### Why can distributed databases not rely solely on system wall clocks (time.time()) to order writes across cluster nodes? - [ ] Because hardware clock drift, virtualization pauses, and NTP adjustments cause servers to disagree on absolute time ⏱️ - [ ] Because POSIX time overflows every 24 hours on Linux systems - [ ] Because floating point precision cannot calculate microsecond fractions - [ ] Because wall clock access requires kernel root permissions on every call --- ### Practical Challenge 🎯 Implement `LamportClock` with `tick()` (increments by 1) and `receive(remote_time)` (updates to `max(time, remote_time) + 1`). Node A ticks once, then ticks again to generate a message timestamp. Node B (initial time 5) receives Node A's message timestamp. Assert Node B's new time equals 6, and print Node B's final time. <details> <summary>Solution</summary> ```python class LamportClock: def __init__(self, node_id, initial=0): self.node_id = node_id self.time = initial def tick(self): self.time += 1 return self.time def receive(self, remote_time): self.time = max(self.time, remote_time) + 1 return self.time node_a = LamportClock("A", initial=0) node_b = LamportClock("B", initial=5) node_a.tick() msg_ts = node_a.tick() b_ts = node_b.receive(msg_ts) assert b_ts == 6 print(b_ts) ``` </details>

Checkpoint

Why can distributed databases not rely solely on system wall clocks (`time.time()`) to order writes across cluster nodes? 🧠

Practice

Implement `LamportClock` with `tick()` (increments by 1) and `receive(remote_time)` (updates to `max(time, remote_time) + 1`). Node A ticks once, then ticks again to generate a message timestamp. Node B (initial time 5) receives Node A's message timestamp. Assert Node B's new time equals 6, and print Node B's final time. 🎯

Terminal
01
Tap code blocks below to assemble
Available Blocks