Time, Clocks & Ordering

Every computer has a hardware clock: typically a quartz crystal oscillator that vibrates at a nominal frequency (often 32,768 Hz), plus a counter that the operating system reads and calibrates into wall-clock time. The OS exposes this as the system clock (via gettimeofday on Linux, or clock_gettime(CLOCK_REALTIME, ...)), returning the number of seconds since the Unix epoch (Jan 1, 1970 UTC).

The problem: quartz oscillators are not perfect. They drift. A typical server clock drifts by 10–100 ppm (parts per million), meaning it can gain or lose up to 8.64 seconds per day. Over the lifetime of a server between reboots, this adds up to minutes or hours of error.

To counter this, servers run NTP (Network Time Protocol), which synchronizes clocks against a hierarchy of time servers that ultimately reference atomic clocks. NTP can reduce skew to 1–50 milliseconds on a LAN, but over a WAN the skew is often 100 ms or more. NTP can even step the clock backwards when it is running too fast, which violates monotonicity and can cause now() < last_recorded_time — a catastrophic assumption violation for any system that uses timestamps to order events.

Clock skew is the difference in readings between two clocks at a given instant. Clock drift is the rate at which skew accumulates over time. If Process A records timestamp T_A and Process B records timestamp T_B for events that A claims happened before B's event, but T_A > T_B due to skew, we have a false ordering.

Operating systems also expose a monotonic clock (CLOCK_MONOTONIC on Linux, time.monotonic() in Python) that is guaranteed never to go backward — it counts nanoseconds since some arbitrary point (often boot). This is safe for measuring durations on one machine but cannot be compared across machines, since the epoch differs.

Google's Spanner database confronts this head-on with TrueTime: GPS receivers and atomic clocks in every datacenter, combined with a careful error-bound API (TT.now() returns an interval [earliest, latest] rather than a point). Spanner waits out the uncertainty interval before committing a transaction, ensuring that if commit timestamp s is in the interval, no future transaction will be assigned a timestamp less than s. This is a remarkable engineering achievement that costs tens of milliseconds of commit latency in exchange for global external consistency.

import time

# System (wall) clock — NOT safe to compare across machines
t_wall = time.time()          # seconds since Unix epoch, can go backward

# Monotonic clock — safe for durations on ONE machine only
t_mono = time.monotonic()     # seconds since arbitrary epoch, never decreases

# Perf counter — highest-resolution monotonic clock available
t_perf = time.perf_counter()  # best for benchmarking on one machine

print(f"Wall clock:  {t_wall:.6f}")
print(f"Monotonic:   {t_mono:.6f}")
print(f"Perf:        {t_perf:.9f}")

# Danger: comparing timestamps across processes/machines
# If machine A has clock_skew = +200ms vs machine B:
# event on A at t=1000.200, event on B at t=1000.100
# BUT A's event actually happened AFTER B's event!
# Physical timestamps alone cannot establish causal order.

Leslie Lamport's key insight in his 1978 paper was to abandon wall-clock time entirely and define a partial order on events based purely on information flow. He called this the happens-before relation, written → (read: "happened before" or "causally precedes").

Formal definition: the happens-before relation → on a set of events in a distributed system is the smallest relation satisfying:

1. Process order: If a and b are events in the same process and a occurs before b, then a → b.
2. Message causality: If a is the sending of a message and b is the receipt of that same message, then a → b.
3. Transitivity: If a → b and b → c, then a → c.

These three rules capture causality precisely: a → b means it is possible that a influenced b. If a → b, then any process that has observed b could, in principle, have had its behavior influenced by a.

What if neither a → b nor b → a? Then a and b are concurrent, written a ∥ b. Concurrency here means: neither event could have caused the other. There was no causal path — no chain of messages or process-order steps — from a to b or from b to a.

This gives us a strict partial order on events (irreflexive, asymmetric, transitive) that is not total: some pairs of events are incomparable. This is not a limitation — it is a profound truth about distributed systems. When two writes are concurrent, there is no objective fact about which came first. Any claim of an ordering is an arbitrary choice, not a discovery.

Visualizing this: imagine events as nodes in a directed acyclic graph (DAG). Draw an edge from a to b if a → b directly (by rule 1 or 2). The transitive closure of this DAG is the full happens-before relation. Two nodes with no directed path between them in either direction are concurrent.

# Happens-before as a DAG (conceptual)
# Process P: a -> b -> c
# Process Q: d -> e
# Process R: f -> g -> h
# Messages: b -> e (P sends to Q), d -> g (Q sends to R)

# Edges in DAG:
# a->b, b->c  (process order in P)
# d->e        (process order in Q)
# f->g, g->h  (process order in R)
# b->e        (message: P sends to Q)
# d->g        (message: Q sends to R)

# Transitive closure gives us:
# a -> b -> c  (P's process order)
# a -> e       (a->b->e)
# b -> g       (b->e->... wait, d->g, not e->g)
# Actually: a->b->e (but e is AFTER d->g path needs checking)
# b->e, d->e (both happen before e), d->g->h
# b->e means e happens after b; b->g? Only if e->g, which is not stated.
# So: b || f, b || g (b and g are CONCURRENT — no causal path!)

def happens_before(dag_edges, a, b):
    """BFS/DFS reachability in the happens-before DAG."""
    from collections import deque
    visited = set()
    queue = deque([a])
    while queue:
        node = queue.popleft()
        if node == b:
            return True
        if node not in visited:
            visited.add(node)
            queue.extend(dag_edges.get(node, []))
    return False

edges = {'a':['b'], 'b':['c','e'], 'd':['e','g'], 'f':['g'], 'g':['h']}
print(happens_before(edges, 'a', 'c'))  # True (a->b->c)
print(happens_before(edges, 'b', 'h'))  # True (b->e, d->g->h, but b->e doesn't reach g...)
# b->e, and d->g->h; is e->g? No edge. So b->h is FALSE.
print(happens_before(edges, 'b', 'h'))  # False — b and h are concurrent!

Now that we have a precise definition of happens-before, we want to assign numbers to events such that if a → b, then timestamp(a) < timestamp(b). This is a clock condition: the clock must be consistent with causality.

Lamport's algorithm is elegantly simple. Each process P_i maintains a counter C_i, initially 0:

1. Before executing any event: C_i = C_i + 1. Assign timestamp C_i to the event.
2. When sending a message: include the current C_i in the message.
3. When receiving a message with timestamp t: C_i = max(C_i, t) + 1.

Rule 3 is the key: when you receive a message, you fast-forward your clock to at least the sender's clock value, then increment. This ensures the receive event has a strictly larger timestamp than the send event.

Clock condition theorem: If a → b, then L(a) < L(b). (Proof: by structural induction on the rules defining →.)

Important caveat — the converse is NOT true: L(a) < L(b) does NOT imply a → b. Two concurrent events a ∥ b might have L(a) < L(b) by coincidence. Lamport timestamps are a necessary but not sufficient condition for happens-before.

What Lamport timestamps ARE good for:

• Breaking ties arbitrarily to achieve a total order: if L(a) ≠ L(b), sort by timestamp; if L(a) = L(b), break ties by process ID. This total order is consistent with happens-before (no event appears before a cause) but is an arbitrary extension of the partial order (concurrent events get an arbitrary ordering).
• This total order is the basis of Lamport's Mutex algorithm and many distributed algorithms that need a globally consistent ordering without a centralized sequencer.

The key limitation: from L(a) < L(b), you cannot tell whether a → b or a ∥ b. Lamport timestamps tell you what order is consistent with causality, but not what the actual causal structure is.

import threading

class LamportClock:
    def __init__(self, pid):
        self.pid = pid
        self.time = 0
        self._lock = threading.Lock()

    def tick(self):
        """Increment before a local event. Returns (timestamp, pid) tuple."""
        with self._lock:
            self.time += 1
            return (self.time, self.pid)

    def send(self):
        """Call before sending; returns clock value to embed in message."""
        return self.tick()

    def receive(self, msg_time):
        """Call on receiving a message with timestamp msg_time."""
        with self._lock:
            self.time = max(self.time, msg_time) + 1
            return (self.time, self.pid)

# Simulation: P0 sends to P1
p0 = LamportClock(0)
p1 = LamportClock(1)

e1 = p0.tick()              # P0 local event  -> (1, 0)
e2_send, t_sent = p0.send(), p0.time  # P0 sends msg  -> (2, 0), t_sent=2
e3 = p1.tick()              # P1 local event  -> (1, 1)  [concurrent with P0!]
e4_recv = p1.receive(t_sent)  # P1 receives -> max(1,2)+1 = (3, 1)

# Now L(send)=2 < L(recv)=3 ✓
# But L(e3)=1 < L(e2_send)=2 does NOT mean e3 happened-before e2!
# e3 and e2 are concurrent events that got an arbitrary ordering.

Lamport timestamps give us a total order consistent with causality, but they lose causal structure: we cannot detect concurrency. Vector clocks, independently developed by Colin Fidge and Friedemann Mattern in 1988, fix this by tracking a vector of counters — one per process — instead of a single counter.

With n processes, each process P_i maintains a vector V_i[1..n], initially all zeros.

Update rules:

1. Before a local event at P_i: V_i[i] = V_i[i] + 1.
2. When P_i sends a message: increment V_i[i], then send the current vector V_i with the message.
3. When P_i receives a message with vector V_msg: V_i[j] = max(V_i[j], V_msg[j]) for all j, then V_i[i] = V_i[i] + 1.

The component V_i[j] records how many events P_i knows have happened at P_j that are causally before the current event at P_i.

Comparing vector clocks: Given vectors V and W:

• V = W iff V[i] = W[i] for all i
• V ≤ W iff V[i] ≤ W[i] for all i
• V < W iff V ≤ W and V ≠ W
• V ∥ W (concurrent) iff neither V < W nor W < V

Theorem (Vector Clock Consistency): For events a and b with vector timestamps VC(a) and VC(b):

• a → b if and only if VC(a) < VC(b)
• a ∥ b if and only if VC(a) ∥ VC(b)

This is the crucial difference from Lamport: vector clocks are both necessary AND sufficient for happens-before. You can detect concurrency exactly. The price: O(n) space per timestamp, where n is the number of processes. For large clusters this can be prohibitive (Amazon Dynamo famously ran into this with hundreds of storage nodes and eventually switched to a truncated/bounded variant).

Vector clocks are used in: Amazon Dynamo (conflict detection), Riak (sibling resolution), version control systems (Git's DAG is structurally equivalent), distributed databases for snapshot isolation, and distributed debugging.

class VectorClock:
    def __init__(self, pid, n_procs):
        self.pid = pid
        self.n = n_procs
        self.vec = [0] * n_procs

    def tick(self):
        self.vec[self.pid] += 1
        return self.vec[:]

    def send(self):
        self.vec[self.pid] += 1
        return self.vec[:]  # send a copy

    def receive(self, msg_vec):
        for i in range(self.n):
            self.vec[i] = max(self.vec[i], msg_vec[i])
        self.vec[self.pid] += 1
        return self.vec[:]

    @staticmethod
    def compare(v1, v2):
        """Returns 'before', 'after', 'equal', or 'concurrent'."""
        less = any(v1[i] < v2[i] for i in range(len(v1)))
        greater = any(v1[i] > v2[i] for i in range(len(v1)))
        if not less and not greater: return 'equal'
        if less and not greater:     return 'before'
        if greater and not less:     return 'after'
        return 'concurrent'

# 3-process example
p0 = VectorClock(0, 3)  # P0
p1 = VectorClock(1, 3)  # P1
p2 = VectorClock(2, 3)  # P2

a = p0.tick()           # a: [1,0,0]
b = p1.tick()           # b: [0,1,0]  — concurrent with a!
c_vec = p0.send()       # P0 sends: [2,0,0]
d = p1.receive(c_vec)   # P1 receives from P0: max+1 -> [2,2,0]
e = p2.tick()           # e: [0,0,1]  — concurrent with everything above

print(VectorClock.compare(a, d))  # 'before' — a caused d
print(VectorClock.compare(b, d))  # 'before' — b caused d  
print(VectorClock.compare(a, b))  # 'concurrent' — no causal path
print(VectorClock.compare(e, d))  # 'concurrent' — P2 isolated

These terms come from mathematics but have deep practical implications.

A strict partial order is a relation < on a set S that is:

• Irreflexive: a < a is false for all a
• Asymmetric: if a < b then b < a is false
• Transitive: if a < b and b < c then a < c

The happens-before relation → is a strict partial order on the events of a distributed system. It is partial because not all pairs are comparable — concurrent events have no ordering.

A total order adds comparability (also called trichotomy or linearity):

• For all a ≠ b: either a < b or b < a

Every pair of events can be compared. A total order consistent with a given partial order is called a linear extension of that partial order.

Why does this distinction matter?

1. Databases need total orders for serializable transactions: Serializability requires that concurrent transactions appear as if they executed in some serial (total) order. But which one? Any linear extension of the happens-before order is valid. Distributed databases spend enormous effort agreeing on one.

2. Total orders can be arbitrary: When we extend a partial order to a total order (as Lamport timestamps do), we are making an arbitrary choice about the ordering of concurrent events. This is fine for many algorithms (mutual exclusion, leader election), but if concurrent events are writes to the same key, you have just invented a "winner" with no causal justification.

3. CRDTs exploit partial orders: Conflict-Free Replicated Data Types are designed so that their merge operation is commutative and associative — it doesn't matter what order concurrent updates are applied in. This is the principled way to handle concurrency without a total order.

4. Total order broadcast (atomic broadcast): A fundamental distributed-systems primitive: deliver messages to all processes in the same total order. This is equivalent in power to consensus (Paxos, Raft) — you cannot implement total-order broadcast without solving consensus. This is why ordering is hard in distributed systems: to get a total order you need coordination, and coordination is expensive and fragile.

# Demonstrating partial vs total order over events
# Events: a, b, c, d where a->c, b->c, d is concurrent with all

from functools import cmp_to_key

events = {
    'a': [1, 0, 0],  # vector clocks
    'b': [0, 1, 0],
    'c': [1, 1, 1],  # received from both a(via P0) and b(via P1)
    'd': [0, 0, 1],  # P2 local, concurrent with a and b
}

def vc_le(v1, v2):
    return all(v1[i] <= v2[i] for i in range(3))

def partial_order_compare(e1, e2):
    v1, v2 = events[e1], events[e2]
    if vc_le(v1, v2) and v1 != v2: return -1  # e1 before e2
    if vc_le(v2, v1) and v1 != v2: return  1  # e2 before e1
    return 0  # concurrent — NOT a valid comparator for total sort!

# Lamport-style total order: use sum of vector as proxy (tie-break by name)
def lamport_total_order(e1, e2):
    s1 = sum(events[e1])
    s2 = sum(events[e2])
    if s1 != s2: return s1 - s2
    return (e1 > e2) - (e1 < e2)  # lexicographic tie-break

total = sorted(events.keys(), key=cmp_to_key(lamport_total_order))
print("Total order:", total)  # e.g. ['a','b','d','c'] or similar
# Note: a and b may swap, d may appear before or after them.
# Any ordering of {a,b,d} before c is a valid linear extension.

A causality violation occurs when the observable state of a system contradicts the happens-before relation. The classic example is causal consistency in distributed databases.

Imagine Alice posts on a social network: "I got the job!" (event A). Then Bob sees Alice's post and comments: "Congratulations!" (event B, causally after A). Now Carol refreshes and sees Bob's comment but NOT Alice's post. Carol is confused — she sees an effect without its cause. This is a causality violation, and it can happen easily when different replicas are in different states.

Causal consistency is the guarantee that causally related operations are seen by all processes in causal order. It is weaker than linearizability (which requires a total order consistent with real time) but stronger than eventual consistency (which allows arbitrary orderings). Many practical systems — including MongoDB's causal sessions and YugabyteDB — offer causal consistency as a performance/correctness trade-off.

Read-your-writes is a practical special case: if you write a value and then read, you should see your own write. This is violated in naive round-robin load balancing where your read goes to a replica that hasn't received your write yet.

Vector clocks give us a precise tool to detect and prevent causality violations. When a client operation arrives at a server, include the client's vector clock. The server can check whether it has "seen" all the events the client expects — if not, it must wait (or re-route) before serving the request. Systems like Bayou, COPS (Causal+ Consistency), and Eiger use this technique.

The CAP theorem connection: Causal consistency is achievable in a partition-tolerant, available system (unlike linearizability, which CAP tells us cannot be provided under partition). COPS and similar systems prove this: you can have causal consistency AND availability AND partition tolerance, as long as you accept that some operations (like atomic multi-key writes) require additional coordination.

# Simulating a causality violation in a replicated key-value store
# and how vector clocks prevent it

class CausalKVStore:
    def __init__(self, node_id, n_nodes):
        self.nid = node_id
        self.store = {}     # key -> (value, vector_clock)
        self.vc = [0] * n_nodes

    def write(self, key, value):
        self.vc[self.nid] += 1
        self.store[key] = (value, self.vc[:])
        return self.vc[:]   # return clock to client

    def read(self, key, client_vc):
        """Only serve read if we have seen at least client_vc."""
        if key not in self.store:
            return None, None
        _, stored_vc = self.store[key]
        # Check: is client_vc <= stored_vc? (have we seen all client deps?)
        deps_satisfied = all(
            self.vc[i] >= client_vc[i] for i in range(len(client_vc))
        )
        if deps_satisfied:
            return self.store[key]
        else:
            return 'WAIT', None  # must stall until deps are replicated

# Without causal tracking, Bob's comment could arrive at a replica
# before Alice's post — causing Carol to see the comment sans post.
# With vector clocks, the replica sees the client's dependency vector
# and refuses to serve the comment until Alice's post is also visible.

A global state of a distributed system is the collection of local states of all processes plus the states of all communication channels (messages in transit). A consistent cut is a global state where, for every message received in the cut, the corresponding send event is also in the cut. In other words, you never see an effect without its cause.

The Chandy-Lamport snapshot algorithm (1985) computes a consistent global snapshot of a distributed system without stopping it. It is used for:

• Checkpointing (save state to recover from failure)
• Detecting global properties like deadlock or termination
• Debugging (what was the state of the whole system when this bug appeared?)

Algorithm (assumes reliable FIFO channels between every pair of processes):

1. Any process P_i can initiate by recording its own local state and sending a special marker message on all outgoing channels.
2. When a process P_j receives a marker on channel C_ij for the first time: a. It records its local state. b. It records the channel state C_ij as empty (the marker is the cut point). c. It sends a marker on all its outgoing channels.
3. After initiating/receiving the first marker, for any other channel C_kj where P_j has NOT yet received a marker: P_j records all messages received on C_kj after the first marker (these are in-transit messages that are part of the snapshot).
4. The algorithm terminates when all processes have received markers on all their incoming channels.

Why is this a consistent cut? The marker partitions the event stream at each process into "before snapshot" and "after snapshot". Any message sent before the marker is in the snapshot; messages sent after are not. By recording channel states (messages received after the sender marked but before the receiver marked), we capture in-flight messages that belong to the pre-snapshot world. This guarantees the cut is consistent — no message appears received without its send.

# Chandy-Lamport snapshot — conceptual single-process simulation
# Real implementation would span multiple processes/machines.

MARKER = '__MARKER__'

class Process:
    def __init__(self, pid):
        self.pid = pid
        self.state = {}      # application state (e.g. account balance)
        self.recording = {}  # channel -> list of in-transit msgs
        self.snapshot_state = None
        self.snapshot_channels = {}
        self.initiated = False

    def initiate_snapshot(self, outgoing_channels):
        """Step 1: initiating process records own state, sends markers."""
        self.snapshot_state = dict(self.state)
        self.initiated = True
        for ch in outgoing_channels:
            ch.send(MARKER)
        # Start recording all incoming channels
        for ch in self.incoming_channels:
            self.recording[ch] = []

    def on_receive(self, msg, from_channel, outgoing_channels):
        if msg == MARKER:
            if not self.initiated:
                # First marker: record state, send markers, stop recording this channel
                self.snapshot_state = dict(self.state)
                self.initiated = True
                for ch in outgoing_channels:
                    ch.send(MARKER)
                for ch in self.incoming_channels:
                    if ch != from_channel:
                        self.recording[ch] = []
            # Finalize channel state for from_channel
            self.snapshot_channels[from_channel] = self.recording.pop(from_channel, [])
        else:
            # Normal message: if recording this channel, capture it
            if from_channel in self.recording:
                self.recording[from_channel].append(msg)
            self._process(msg)

    def _process(self, msg):
        pass  # application logic

Version vectors (also sometimes loosely called vector clocks in the storage community, though they are subtly different) are the application of vector-clock ideas to replica versioning in distributed storage systems.

In a system where each key can be written by multiple replicas (like Dynamo or Riak), each value is tagged with a version vector: a mapping from replica ID to counter, recording how many writes from each replica are reflected in this version.

Difference from vector clocks: In vector clocks, the clock advances at the process that does the operation. In version vectors, the counter advances at the replica that accepted the write. The semantics are different: version vectors track which updates have been incorporated into a value, while vector clocks track causal relationships between all events.

Conflict detection with version vectors:

• If version V1 < V2 (component-wise), then V2 subsumes V1 — V2 is causally newer. Keep V2.
• If V1 ∥ V2 (neither dominates), the two values were written concurrently — this is a conflict that the application must resolve (e.g., "last writer wins", "merge", "show both to user").

Amazon Dynamo's original design used version vectors and returned conflicting sibling values to the client, which resolved them. Riak still does this. DynamoDB switched to "last writer wins" using physical timestamps (simple but can lose data). Cassandra uses a hybrid: last-writer-wins with wall-clock timestamp, relying on NTP (imperfect but practical).

The danger of "last writer wins" (LWW): If two concurrent writes happen and you pick the one with the higher physical timestamp as the winner, you silently discard one write. This is data loss. The only way to avoid it without coordination is to detect concurrency using vector clocks and handle it at the application layer.

Dotted version vectors: An advanced variant that solves the problem of distinguishing "this replica has seen and deleted a key" from "this replica hasn't heard about the key yet" — a distinction that plain version vectors cannot make. Used in Riak 2.0.

# Version vector conflict detection for a distributed key-value store

def vv_dominates(v1, v2):
    """Returns True if v1 causally dominates (is newer than or equal to) v2."""
    all_keys = set(v1) | set(v2)
    return all(v1.get(k, 0) >= v2.get(k, 0) for k in all_keys)

def merge_values(val1, vv1, val2, vv2):
    """
    Given two versions of a key, return the resolved value(s).
    Returns a single value if one dominates; list of siblings if concurrent.
    """
    d12 = vv_dominates(vv1, vv2)  # is v1 >= v2 everywhere?
    d21 = vv_dominates(vv2, vv1)  # is v2 >= v1 everywhere?

    if d12 and not d21:
        return [(val1, vv1)]           # v1 is strictly newer
    elif d21 and not d12:
        return [(val2, vv2)]           # v2 is strictly newer
    elif d12 and d21:
        return [(val1, vv1)]           # equal — same write, keep either
    else:
        return [(val1, vv1), (val2, vv2)]  # CONFLICT — concurrent writes!

# Replica A wrote 'alice' at counter A=1
vv_a = {'A': 1}
# Replica B wrote 'bob' at counter B=1 CONCURRENTLY (neither knew about the other)
vv_b = {'B': 1}

result = merge_values('alice', vv_a, 'bob', vv_b)
print(result)  # Two siblings: conflict! Application must resolve.

# After resolution: client merges and writes back with merged vv
vv_merged = {'A': 1, 'B': 1}  # "I've seen both A=1 and B=1"
result2 = merge_values('alice+bob', vv_merged, 'bob', vv_b)
print(result2)  # Single value: merged dominates