Time and Clocks

Lamport 1978 · Wikipedia · Lamport timestamps

Physical clocks drift. Logical clocks don't measure wall time; they capture causality. If event A could have influenced event B, then A's timestamp is less than B's. Lamport clocks give a total order consistent with causality. Vector clocks give the exact causal partial order.

Physical clocks and drift

Every computer has a quartz oscillator. It drifts by roughly 10-100 ppm (parts per million). Over a day, that is 1-10 seconds of error. NTP corrects this but cannot eliminate it. Two nodes will never agree on the exact time.

Scheme

; Clock drift simulation.
; Two clocks start synchronized, drift apart.

(define drift-ppm 50)  ; 50 parts per million
(define seconds-per-day 86400)

; After one day, clock B is off by:
(define drift-seconds
  (/ (* drift-ppm seconds-per-day) 1000000))

(display "Drift rate: ") (display drift-ppm) (display " ppm") (newline)
(display "After 1 day, clocks differ by ")
(display drift-seconds) (display " seconds") (newline)

; After 1 week:
(display "After 1 week: ")
(display (* drift-seconds 7)) (display " seconds")

The happens-before relation

Lamport defined the happens-before relation: A happens-before B (written A → B) if A and B are on the same node and A came first, or if A is a send and B is the corresponding receive. The relation is transitive. Events that are not related by happens-before are concurrent: neither caused the other.

Lamport clocks

Each node keeps a counter. On each local event, increment. On send, increment and attach the counter. On receive, set your counter to max(yours, received) + 1. This gives a total order consistent with causality: if A → B then L(A) < L(B). But the converse is not true: L(A) < L(B) does not mean A caused B.

Scheme

; Lamport clock implementation.
; Each node maintains a counter.

(define clock-p1 0)
(define clock-p2 0)
(define clock-p3 0)

; Local event: increment
(define (local-event clock)
  (+ clock 1))

; Send: increment, return (new-clock, message-timestamp)
(define (send-event clock)
  (let ((new-clock (+ clock 1)))
    (list new-clock new-clock)))

; Receive: max(local, received) + 1
(define (receive-event local-clock msg-ts)
  (+ (max local-clock msg-ts) 1))

; Simulation: P1 sends to P2, P3 sends to P2, P2 sends to P1
(set! clock-p1 (local-event clock-p1))     ; P1: event at 1
(display "P1 local event: ") (display clock-p1) (newline)

(let ((result (send-event clock-p1)))       ; P1 sends (clock=2)
  (set! clock-p1 (car result))
  (display "P1 sends, clock=") (display clock-p1) (newline)
  (set! clock-p2 (receive-event clock-p2 (car (cdr result))))
  (display "P2 receives, clock=") (display clock-p2) (newline))

(set! clock-p3 (local-event clock-p3))      ; P3: event at 1
(let ((result (send-event clock-p3)))       ; P3 sends (clock=2)
  (set! clock-p3 (car result))
  (set! clock-p2 (receive-event clock-p2 (car (cdr result))))
  (display "P3 sends, P2 receives, P2 clock=") (display clock-p2) (newline))

(let ((result (send-event clock-p2)))       ; P2 sends (clock=5)
  (set! clock-p2 (car result))
  (set! clock-p1 (receive-event clock-p1 (car (cdr result))))
  (display "P2 sends, P1 receives, P1 clock=") (display clock-p1) (newline))

; Lamport clock implementation.
; Each node maintains a counter.

(define clock-p1 0)
(define clock-p2 0)
(define clock-p3 0)

; Local event: increment
(define (local-event clock)
  (+ clock 1))

; Send: increment, return (new-clock, message-timestamp)
(define (send-event clock)
  (let ((new-clock (+ clock 1)))
    (list new-clock new-clock)))

; Receive: max(local, received) + 1
(define (receive-event local-clock msg-ts)
  (+ (max local-clock msg-ts) 1))

; Simulation: P1 sends to P2, P3 sends to P2, P2 sends to P1
(set! clock-p1 (local-event clock-p1))     ; P1: event at 1
(display "P1 local event: ") (display clock-p1) (newline)

(let ((result (send-event clock-p1)))       ; P1 sends (clock=2)
  (set! clock-p1 (car result))
  (display "P1 sends, clock=") (display clock-p1) (newline)
  (set! clock-p2 (receive-event clock-p2 (car (cdr result))))
  (display "P2 receives, clock=") (display clock-p2) (newline))

(set! clock-p3 (local-event clock-p3))      ; P3: event at 1
(let ((result (send-event clock-p3)))       ; P3 sends (clock=2)
  (set! clock-p3 (car result))
  (set! clock-p2 (receive-event clock-p2 (car (cdr result))))
  (display "P3 sends, P2 receives, P2 clock=") (display clock-p2) (newline))

(let ((result (send-event clock-p2)))       ; P2 sends (clock=5)
  (set! clock-p2 (car result))
  (set! clock-p1 (receive-event clock-p1 (car (cdr result))))
  (display "P2 sends, P1 receives, P1 clock=") (display clock-p1) (newline))

Vector clocks

A vector clock is an array of counters, one per node. Node i increments its own entry on each event. On send, attach the whole vector. On receive, take the componentwise max, then increment your entry. Two events are concurrent if and only if neither vector dominates the other. Vector clocks capture the exact causal partial order.

Scheme

; Vector clocks: one counter per node.
; Dominance = componentwise <=, strict on at least one.

(define (vc-increment vc i)
  ; increment position i in vector vc
  (let loop ((v vc) (j 0) (acc (list)))
    (if (null? v) (reverse acc)
        (loop (cdr v) (+ j 1)
              (cons (if (= j i) (+ (car v) 1) (car v)) acc)))))

(define (vc-merge vc1 vc2)
  ; componentwise max
  (let loop ((a vc1) (b vc2) (acc (list)))
    (if (null? a) (reverse acc)
        (loop (cdr a) (cdr b)
              (cons (max (car a) (car b)) acc)))))

(define (vc-before? a b)
  ; a <= b componentwise, and a != b
  (let loop ((x a) (y b) (all-leq #t) (strict #f))
    (if (null? x) (and all-leq strict)
        (loop (cdr x) (cdr y)
              (and all-leq (<= (car x) (car y)))
              (or strict (< (car x) (car y)))))))

; Three nodes: indices 0, 1, 2
(define vc-a (list 0 0 0))
(define vc-b (list 0 0 0))

; Node 0 does a local event
(set! vc-a (vc-increment (list 0 0 0) 0))  ; (1 0 0)
; Node 1 does a local event
(set! vc-b (vc-increment (list 0 0 0) 1))  ; (0 1 0)

(display "vc-a = ") (display vc-a) (newline)
(display "vc-b = ") (display vc-b) (newline)
(display "a before b? ") (display (vc-before? vc-a vc-b)) (newline)
(display "b before a? ") (display (vc-before? vc-b vc-a)) (newline)
(display "concurrent? ") (display (and (not (vc-before? vc-a vc-b))
                                        (not (vc-before? vc-b vc-a))))

; Vector clocks: one counter per node.
; Dominance = componentwise <=, strict on at least one.

(define (vc-increment vc i)
  ; increment position i in vector vc
  (let loop ((v vc) (j 0) (acc (list)))
    (if (null? v) (reverse acc)
        (loop (cdr v) (+ j 1)
              (cons (if (= j i) (+ (car v) 1) (car v)) acc)))))

(define (vc-merge vc1 vc2)
  ; componentwise max
  (let loop ((a vc1) (b vc2) (acc (list)))
    (if (null? a) (reverse acc)
        (loop (cdr a) (cdr b)
              (cons (max (car a) (car b)) acc)))))

(define (vc-before? a b)
  ; a <= b componentwise, and a != b
  (let loop ((x a) (y b) (all-leq #t) (strict #f))
    (if (null? x) (and all-leq strict)
        (loop (cdr x) (cdr y)
              (and all-leq (<= (car x) (car y)))
              (or strict (< (car x) (car y)))))))

; Three nodes: indices 0, 1, 2
(define vc-a (list 0 0 0))
(define vc-b (list 0 0 0))

; Node 0 does a local event
(set! vc-a (vc-increment (list 0 0 0) 0))  ; (1 0 0)
; Node 1 does a local event
(set! vc-b (vc-increment (list 0 0 0) 1))  ; (0 1 0)

(display "vc-a = ") (display vc-a) (newline)
(display "vc-b = ") (display vc-b) (newline)
(display "a before b? ") (display (vc-before? vc-a vc-b)) (newline)
(display "b before a? ") (display (vc-before? vc-b vc-a)) (newline)
(display "concurrent? ") (display (and (not (vc-before? vc-a vc-b))
                                        (not (vc-before? vc-b vc-a))))

Neighbors

Cross-references

🔑 Logic Ch.7 — partial orders: the mathematical structure behind happens-before

← What Makes It Hard by june.kim Replication →