Lamport clocks

Deep dive

How it works

In: local events, plus the timestamp T carried by each received message · Out: a stamp (C, node_id) per event, a total order consistent with causality · State: one counter C per process (persist it across restarts) · Cost: O(1) time, 8 bytes per timestamp

1. Local event: C += 1, stamp the event with C.
2. Send: C += 1, attach C.
3. Receive message with T: C = max(C, T) + 1, stamp the receive with C.
4. Total order: compare (C, node_id) lexicographically.

Total-order broadcast (Lamport 1978): every process broadcasts timestamped messages over FIFO channels and holds received messages in a priority queue. Deliver the smallest (T, node) once a message with a larger timestamp has arrived from every other process: by FIFO, nothing smaller can still arrive. Processes must keep talking (heartbeats) or delivery stalls; one crash stalls it forever, which is why consensus replaced it in practice.

P1: 1 ──send(2)──────────────►        5
P2:        3 ← max(0,2)+1   4 ──send(4)──► P1: max(1,4)+1 = 5

Code

use std::cmp::Reverse;
use std::collections::{BinaryHeap, HashMap};
use std::sync::atomic::{AtomicU64, Ordering};

#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Debug, Hash)]
pub struct Stamp { pub time: u64, pub node: u32 } // derive(Ord): time, then node

pub struct LamportClock { node: u32, c: AtomicU64 }

impl LamportClock {
    pub fn new(node: u32) -> Self { LamportClock { node, c: AtomicU64::new(0) } }
    /// Local event or send.
    pub fn tick(&self) -> Stamp {
        Stamp { time: self.c.fetch_add(1, Ordering::Relaxed) + 1, node: self.node }
    }
    /// Receive: jump past the sender's time. Lock-free and safe under concurrent receives.
    pub fn recv(&self, remote: u64) -> Stamp {
        let prev = self.c.fetch_update(Ordering::Relaxed, Ordering::Relaxed,
                                       |c| Some(c.max(remote) + 1)).unwrap();
        Stamp { time: prev.max(remote) + 1, node: self.node }
    }
}

/// Lamport total-order delivery over FIFO channels among a fixed membership.
pub struct TotalOrder<M> {
    pending: BinaryHeap<Reverse<(Stamp, u64)>>, // (stamp, seq) -> payload in `msgs`
    msgs: HashMap<u64, M>,
    latest: HashMap<u32, u64>,                  // highest time seen from each peer
    seq: u64,
}

impl<M> TotalOrder<M> {
    /// `peers` = all *other* processes. Our own future stamps already exceed anything received.
    pub fn new(peers: &[u32]) -> Self {
        TotalOrder { pending: BinaryHeap::new(), msgs: HashMap::new(),
                     latest: peers.iter().map(|&p| (p, 0)).collect(), seq: 0 }
    }
    /// Record any message (data or heartbeat) from a peer; `data` = None for heartbeats.
    pub fn on_message(&mut self, s: Stamp, data: Option<M>) {
        if let Some(l) = self.latest.get_mut(&s.node) { *l = (*l).max(s.time); } // own msgs: no entry
        if let Some(m) = data {
            self.seq += 1;
            self.msgs.insert(self.seq, m);
            self.pending.push(Reverse((s, self.seq)));
        }
    }
    /// Messages now safe to deliver, in the global order.
    pub fn deliverable(&mut self) -> Vec<(Stamp, M)> {
        let mut out = Vec::new();
        while let Some(&Reverse((s, id))) = self.pending.peek() {
            // Safe iff every *other* peer has sent something with a larger stamp.
            let stable = self.latest.iter().all(|(&p, &t)| p == s.node || t > s.time);
            if !stable { break; }
            self.pending.pop();
            out.push((s, self.msgs.remove(&id).unwrap()));
        }
        out
    }
}

Every process must also pass its own messages to on_message so it delivers them in the same order as everyone else.

Complexity and constants

• Per event: one atomic RMW, order of 5-20 ns uncontended; contended atomics on one cache line can cost order of 100 ns.
• Per message: 8 bytes (+ 4 for node id).
• Total-order broadcast: delivery latency ≈ one message from the slowest peer; O(log n) per heap operation.
• Lamport's mutual-exclusion algorithm: 3(N−1) messages per critical section (request, reply, release); Ricart-Agrawala: 2(N−1).

Efficiency

• Cost: one atomic read-modify-write per event, order of 5-20 ns uncontended and order of 100 ns when many threads hit one cache line; 8 bytes per timestamp (plus 4 for the node id), 1-4 bytes as a varint. Total-order delivery adds a wait for the slowest peer, one message latency, and all-to-all acks. Bound: cache-line contention in process, network latency across processes.
• Levers:
  • relaxed atomics — the clock needs only per-variable monotonicity, so no fences (above) — in-process clocks
  • piggyback acks on data or batch them on a 1-10 ms tick — fewer than n² ack messages per round (above, order of) — total-order broadcast
  • varint on the wire — 1-4 bytes instead of 8 (order of) — many small messages
  • pack (time, node) into one u64 — one compare, one key (above) — sorted indexes
  • one clock per shard or per thread, merged on exchange — removes cache-line contention (order of) — very high event rates
• Naive → standard → state of the art:
  • central sequencer, one round trip per event · 1 RTT and a single point of failure
  • Lamport clock, local atomic increment · order of 10 ns, no messages
  • Lamport stamps for ordering, consensus (Raft, Multi-Paxos) where order must survive crashes · one quorum round per batch

Implementation notes

• Persist the counter (or a high-water mark, then add a margin on restart) so timestamps never go backwards after a crash.
• u64 never overflows in practice, but a malicious or buggy peer can send u64::MAX; validate or cap remote values.
• Pack (time, node) into one u64 (e.g. 48 + 16 bits) when you need a single sortable integer key.
• Relaxed atomics suffice: the clock only needs per-variable monotonicity, not ordering with other memory.
• Total-order delivery waits until every peer has sent a larger timestamp, so latency is at least one round trip to the slowest peer and acks cost n² messages per round; piggyback acks on data or batch them on a 1-10 ms tick.
• On the wire, the counter compresses well as a varint: order of 1-4 bytes for realistic values instead of 8.

Pitfalls

• Reading C(a) < C(b) as "a caused b": it may be concurrent.
• Forgetting the receive rule (only incrementing locally): ordering then violates causality.
• Using Lamport order for "latest write wins" between users: a node that sends lots of messages pushes its clock ahead and wins every tie; that order is arbitrary, not "most recent".
• Total-order broadcast without heartbeats stalls when a peer is idle.

Variants and alternatives

In production

Paxos ballots and Raft terms (logical clocks of leadership); Automerge operation IDs counter@actor; Lamport timestamps as tie-breakers in many CRDT sequence implementations; Kafka leader epochs follow the same monotonic-epoch idea.

Implementations

Sources

• Leslie Lamport, Time, Clocks, and the Ordering of Events in a Distributed System, CACM 1978. paper
• Glenn Ricart, Ashok K. Agrawala, An Optimal Algorithm for Mutual Exclusion in Computer Networks, CACM 1981. paper