Software Systems Atlas

English

中文

English

中文

Theme

VOL 07 / CH 01 / LESSON 02

1.2 Time, Causality, and Consistency Models ​

Physical time answers the question "roughly what time did this happen in the real world," but it cannot alone establish a causal order between two distributed events. Logical time expresses causality or versioning, while consistency models define which histories of operations are permissible for clients to observe.

Wall Clock and Monotonic Clock ​

Operating systems typically provide two kinds of time:

  • wall clock: corresponds to calendar time and is corrected by NTP, potentially jumping forward or backward;
  • monotonic clock: measures durations within one clock domain and should not move backward. Whether readings can be compared across processes, or include time spent suspended, depends on the API.

Use monotonic clocks for timeouts and latency measurements, and timestamps explicitly marked as UTC, with clock uncertainty recorded, for auditing and alignment across systems. Monotonic readings from different machines cannot be directly subtracted. Physical timestamps can support a last-write-wins rule, but clock error may let an earlier real-world write win. That rule does not establish causality.

Happened-before is a partial order ​

Lamport defined:

  • Within the same process, a prior event happens-before a subsequent event;
  • The sending of a message happens-before the receipt of that message;
  • The relationship is transitive.

If neither event A nor event B can be shown to happen-before the other, they are concurrent events. This does not mean they occurred at the same physical moment. It means no such chain exists in the modeled process order and message relations. Missing logs cannot establish concurrency if tracing omitted messages or communication outside the system.

Lamport Clocks Preserve One Direction of Causality ​

Each node maintains an incrementing counter. Local events, including sends, increment it first; outgoing messages carry that value. A receive event sets it to max(local, received) + 1.

It guarantees:

text
A happened-before B  ⇒  L(A) < L(B)

The converse does not hold. Observing L(A) < L(B) cannot establish that A caused B; concurrent events may also receive different Lamport timestamps. Thus, Lamport Clock establishes a causality-compatible ordering but cannot directly detect concurrency.

To achieve a total order, node IDs can be used to break ties when events share the same logical time. This total order is a protocol-defined convention, not a new causal fact.

Vector Clocks Can Detect Concurrency ​

For a fixed participant set, each node stores a vector with one component per participant. Local and send events increment the node’s own component. A receive event takes the componentwise maximum of the local and received vectors, then increments the receiver’s own component. If every component of V(A) is less than or equal to the corresponding component in V(B), and at least one is strictly smaller, then event A happened-before event B. If neither vector dominates the other, the events are concurrent.

For example, A’s first send carries [1, 0]. Before receiving it, B independently performs two events, reaching [0, 2]. Neither vector dominates the other, so these events are concurrent. B then receives the message, merges the vectors, and increments its own component to obtain [1, 3]. The send now happens-before the receive. Corresponding Lamport values can be 1, 2, and 3; the first two scalar values alone cannot reveal concurrency.

The cost is that metadata grows with the number of participants. Real systems may use version vectors, dotted version vectors, or compress vectors by replica group. Dynamic, large-scale clients cannot directly maintain infinite vectors. Implementations that prune or compress metadata must explain which causal comparisons remain valid.

Hybrid Logical Clocks Combine Approximate Time and Causality ​

HLC combines a physical time component with a logical counter. On receipt, a node merges its physical time, local HLC, and the message’s HLC. The logical counter distinguishes events sharing a time component and preserves increasing timestamps along happened-before relations. HLC does not eliminate clock error or automatically provide linearizability. Its proximity to wall time depends on clock-error assumptions; a remote clock far in the future can affect the receiver too.

TrueTime explicitly returns a physical-time uncertainty interval. Spanner combines it with transaction concurrency control, replication, and commit wait to provide external consistency under its default serializable isolation: transaction serialization order also respects real-time precedence. A time interval alone cannot provide that guarantee. Waiting until a commit timestamp is definitely in the past is part of the protocol.

Consistency Models Define Allowed Histories ​

Linearizability ​

Each operation appears to take effect atomically at some instant between invocation and return. If one operation returns before another is invoked, it must come first. This suits requirements for real-time ordering on a single object, but several linearizable reads and writes do not automatically form a transaction. Two clients can both read "username absent" before each creates the user; uniqueness still needs an atomic conditional write or a suitable transaction constraint.

Sequential Consistency ​

There is a total order of all operations that preserves each client’s program order. It need not preserve real-time precedence across different clients.

Suppose x starts at 0. Client A’s write(x, 1) returns before client B invokes read(x), which returns 0. If each client performs only this one operation, sequential consistency can place B’s read before A’s write. Linearizability cannot accept that explanation.

Causal Consistency ​

All nodes observe causally related operations in the same order; concurrently executed operations with no causal relationship may be ordered differently.

Eventual Consistency ​

When no new updates occur and updates can eventually propagate to the relevant replicas, replicas eventually converge. The name does not promise convergence across a permanent partition. It also does not specify convergence time, conflict resolution, or whether clients can read their own writes.

Clients often also require session guarantees: read-your-writes, monotonic reads, monotonic writes, and writes-follow-reads.

Quorum Formulas Do Not Prove Linearizability ​

For a fixed set of N replicas, suppose successful reads and writes obtain replies from R and W distinct replicas respectively. Then R + W > N guarantees read/write intersection, while W > N/2 guarantees write/write intersection. With N=3 and R=W=2, any two such sets share at least one replica. A sloppy quorum using substitute nodes outside that set cannot use the formula directly. Intersection alone does not settle concurrent writes, partially failed writes, version selection, or the read protocol, so it does not prove linearizability.

Cassandra’s ALL and QUORUM are replica acknowledgment levels. Their names do not establish linearizability for ordinary reads and writes. For linearizable conditional updates, use a mechanism the product explicitly provides, such as consensus-backed lightweight transactions (LWT), and check its exact guarantees.

Selecting Guarantees Based on Invariants ​

RequirementMay Require
Unique usernameLinearizable conditional write or a single authoritative owner
Immediate visibility after user modificationRead-your-writes session guarantee
Causal operations in collaborative editingCausal metadata or dedicated collaboration algorithms
Analytics and recommendationsAcceptable latency with eventual consistency projections
Audit timelinePhysical time plus causal or sequence metadata

Decide which business anomalies are acceptable before selecting storage and protocols. A product’s use of the word "consistency" cannot specify your requirements.

References ​

Built with VitePress | Software Systems Atlas

Copyright 2026 Steven Yang