Time and Clocks

There are at least three distinct time problems in a system: what the current date is, how much time has elapsed for an operation, and whether two distributed events have a causal relationship. These cannot be solved by a single raw timestamp.

Wall Clocks and Monotonic Clocks: Measuring Date and Elapsed Time Separately

Wall clocks are used for log dates, business calendars, and cross-system time markers, typically referencing UTC. They may jump due to time synchronization or manual adjustments, so two consecutive gettimeofday() calls on a single machine do not guarantee correct measurement of elapsed time.

On Linux, CLOCK_MONOTONIC is unaffected by discrete jumps in the wall clock, making it suitable for measuring local intervals and deadlines, but it is subject to gradual frequency adjustments and usually does not account for system suspend time; CLOCK_BOOTTIME includes suspend time. The choice depends on whether "timeouts should count during sleep." These values also cannot be directly used to compare absolute moments across different machines. Linux clock_gettime man page

Even if local timing is reliable, a process may be suspended for a long time before executing the next instruction. A lease stating "1 second remaining" does not guarantee that the process will definitely complete an external write within 1 second.

Happens-before: Constructing Partial Order from Program Order and Messages

Define a→b: a precedes b in the same process; or a is a message send and b is the corresponding receive; plus transitivity. If neither a→b nor b→a holds, they are considered concurrent in this model.

Concurrency does not mean two events physically occur in the exact same nanosecond, but rather that the current model has not established a usable causal order. If the model misses an external communication channel, the derived "no causal relationship" may differ from that of the complete system.

Lamport Clocks: Causal Precedence Implies Count Precedence

Each process maintains a counter C. It increments for local events and send events to take a timestamp; when receiving a message m with timestamp m, it updates to max(C,m)+1. The send increments only once for that send event and should not be counted twice in both the "local event" and "send" rules.

The property is a→b ⇒ C(a)<C(b), but the converse does not hold. Two processes that have not communicated can independently accumulate to 100 and 3; 100 does not mean it knows about the other's first three events, nor does it represent actually occurring later.

Sorting (C, process_id) lexicographically allows constructing a total order compatible with causal direction for events. This is a deterministic sorting rule, not a recovery of the unique real-world complete order from numbers. Lamport: Time, Clocks, and the Ordering of Events

Vector Clocks: Preserving Known Progress of Each Process

With a fixed number N of processes, each process i maintains a vector V. Local events increment V[i]; sends carry this vector; receives first take the component-wise maximum, then increment their own component.

For two event vectors v and w, if all components vᵢ≤wᵢ and at least one is strictly less, we denote it as v<w. When fully adhering to the event model and update rules, this corresponds to causal precedence. If some components are larger and others smaller, they are incomparable.

For example, [2,0] and [1,1] are incomparable; [2,0] and [3,1] are comparable. You cannot detect concurrency via sum, maximum component, or lexicographical order, because those methods discard the independent historical information of each process.

Object version vectors are closely related to event vector clocks, but the objects counted and the causal context may differ. Object storage also needs to define rules for generating new versions, merging contexts, and preserving siblings; it cannot be simplified to "old context writes are necessarily rejected." See Conflict Resolution.

Observe How Known Progress Grows Across Two Message Propagations

Let vector components represent A, B, C in order. A's second event a2 sends a message to B; B receives it at b2, then sends a message to C at b3, which C receives at c2. During this time, A also had a local event a3 that was not sent out.

The first component of c2 is 2, indicating its causal past covers the first two events of A; no message brought a3 into this path. Although C(a3)=3 < C(c2)=5, they are still concurrent. When comparing vectors, a3 has a larger A component, while c2 has larger B and C components, which precisely exposes this distinction.

Below, we simultaneously compute ancestor sets from the event graph and calculate both clocks based on predecessor timestamps, then check all event pairs. Inputs are listed in topological order, but appearing earlier in the list does not equal a causal edge; only explicit program order and message edges count towards relationships.

events = [
    ("a1", 0, ()), ("a2", 0, ("a1",)), ("a3", 0, ("a2",)),
    ("b1", 1, ()), ("b2", 1, ("b1", "a2")), ("b3", 1, ("b2",)),
    ("c1", 2, ()), ("c2", 2, ("c1", "b3")),
]
vectors, lamport, ancestors, last = {}, {}, {}, {}
for name, process, parents in events:
    assert name not in vectors and all(p in vectors for p in parents)
    assert process not in last or last[process] in parents
    vector = [max((vectors[p][i] for p in parents), default=0) for i in range(3)]
    vector[process] += 1
    vectors[name] = tuple(vector)
    lamport[name] = max((lamport[p] for p in parents), default=0) + 1
    ancestors[name] = set(parents)
    for parent in parents:
        ancestors[name].update(ancestors[parent])
    last[process] = name

def vector_before(a, b):
    return all(x <= y for x, y in zip(a, b)) and a != b

for a in vectors:
    for b in vectors:
        causally_before = a in ancestors[b]
        assert vector_before(vectors[a], vectors[b]) == causally_before
        if causally_before:
            assert lamport[a] < lamport[b]
assert vectors["c2"] == (2, 3, 2)
assert lamport["a3"] < lamport["c2"]
assert "a3" not in ancestors["c2"] and "c2" not in ancestors["a3"]

This only simulates processes with fixed identities that do not lose count state. Resetting A's count to zero and reusing its old identity after a restart would break the interpretation that "components represent the complete prefix of that identity." Dynamic membership systems need to define identity generations, state recovery, and metadata recycling; simply extending or truncating the array does not solve the problem.

A message carries knowledge from send time

Each vector component belongs to one process; the sum is insufficient. Send from A, advance A locally, then deliver the earlier message to B. B receives the send-time snapshot, which contains no knowledge of A’s later event. Compare the vectors to distinguish a larger scalar clock from knowledge of the relevant history.

$$V_j\leftarrow \max (V_j,V_{\mathrm{msg}}),V_j[j]\leftarrow V_j[j]+1$$

Logical Mutual Exclusion: Ordering Is Only Part of the Protocol

Lamport's classic mutual exclusion algorithm uses a timestamped request queue under assumptions such as reliable FIFO channels. The requester broadcasts a REQUEST; receivers queue the request and reply; the requester enters the critical section after confirming its request is at the head of the queue and receiving corresponding messages from other processes; upon exit, it broadcasts a RELEASE, allowing queues to remove that request.

This differs from other mutual exclusion algorithms that "delay replies based on priority and send them after exit"; you cannot arbitrarily combine delay reply rules with Lamport's RELEASE queue flow. Schemes waiting for all members also need to handle member failures; otherwise, a permanently unresponsive member would block progress.

Uncertainty Intervals of Physical Time

If the true time of event A is known to be in [10,12] and event B in [13,15], we can judge A precedes B; if B is in [11,14], the intervals overlap, and these boundaries alone cannot determine the order.

The precision of NTP and PTP depends on the synchronization source, path asymmetry, hardware timestamps, load, and disconnection time; there is no universally applicable "fixed 1ms" or "fixed 100ns." Whether software can provide reliable boundaries depends on the system's assumptions about latency, oscillator drift, and faults; one cannot generally say software can never establish boundaries.

After Synchronization Stops, Error Budget Does Not Stop at the Last Measurement

Assume the last synchronization provided a reliable ±2 ms boundary, and afterwards the oscillator's maximum frequency error relative to ideal time is 200 ppm, accumulating at most an extra 0.2 ms of error per second. Without recalibration, no jumps, and assuming these bounds always hold, the conservative boundary after being disconnected for Δt seconds is:

ε(Δt) = 2 ms + 0.2 ms/s × Δt.

Thus, after 30 seconds it is ±8 ms, and after 10 minutes it is ±122 ms. These are examples under artificially given assumptions, not default performance for NTP or any specific crystal oscillator. If two machines each have ±8 ms error, a difference of 10 ms between their clocks is still insufficient to determine true order; uncertainty on both sides must be accounted for.

from fractions import Fraction

def error_ms(elapsed_s):
    assert elapsed_s >= 0
    return Fraction(2) + Fraction(200, 1000) * elapsed_s

def definitely_before(a_center, a_error, b_center, b_error):
    return a_center + a_error < b_center - b_error

assert error_ms(30) == 8
assert error_ms(600) == 122
assert not definitely_before(100, 8, 110, 8)  # [92,108] overlaps with [102,118]
assert not definitely_before(100, 8, 116, 8)  # Boundaries touch, still cannot prove strictly earlier
assert definitely_before(100, 8, 117, 8)

The error upper bound differs from timestamp display precision: printing to nanoseconds only indicates fine numerical format, not small true-time error. When disconnection, temperature changes, or synchronization source anomalies invalidate original assumptions, the system should expand the boundary or stop relying on it for deterministic judgment, rather than continuing to use the old ±2 ms.

TrueTime explicitly exposes time uncertainty as [earliest,latest]. Under its guaranteed conditions, the system waits for earliest to pass the commit timestamp, ensuring the real-time order of commits satisfies the target transaction semantics. Waiting, replication, and transaction concurrency control work together; it is not an atomic clock solving all consistency issues alone. Spanner and TrueTime

Cross-region itself is not a definition of "stronger than linear consistency." Spanner's external consistency is usually discussed at the transaction level regarding real-time serializability; comparisons should keep the scope of objects and transactions consistent.

Hybrid Logical Clocks and Selection Quick Reference

Hybrid Logical Clocks (HLC) combine a component close to physical time with a logical counter, helping associate timestamps easily with physical time while preserving causal direction. It does not automatically provide strict error bounds for global real time, nor does it replace consensus or transaction isolation.

References

• Lamport 1978 Paper.
• Linux clock_gettime.
• Spanner: TrueTime and External Consistency.

Keywords: wall clock, monotonic clock, Lamport clock, vector clock, happens-before, TrueTime, HLC