1.2 Time, Causality, and Consistency Models

In a distributed archipelago, the two clock towers always show slight discrepancies. A letter written before it is read might arrive in reverse order at different observers.

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: used exclusively to measure durations within a process and should never roll back.

Timeout and latency measurements use monotonic clocks; auditing and cross-system synchronization use UTC timestamps with timezone information and record clock uncertainty. Do not determine the winner of concurrent writes based on millisecond timestamps from two machines.

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 only means that no causal chain has been observed by the system.

Lamport Clock The Necessary Direction for Preserving Causality

Each node maintains an incrementing counter: the counter is incremented for local events, the value is carried when sending, and it is updated upon receipt to max(local, received) + 1.

It guarantees:

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

Each participant maintains a count component in a vector clock. 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.

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.

Hybrid Logical Clock Combining Approximate Time with Causality

HLC fuses a physical time component with a logical counter, producing timestamps that closely approximate wall clock time while maintaining logical monotonicity even during clock regressions or overlapping physical time intervals. It does not eliminate physical clock drift, nor does it automatically enforce linearizability; instead, it provides a more practical foundation for ordering events and tracking versions.

Systems like TrueTime explicitly return intervals of physical time uncertainty and rely on waiting mechanisms and external consensus protocols to establish consistency. The key isn't that the clocks are particularly accurate, rather, the uncertainty is measured and incorporated into correctness protocols.

Consistency Models Are a Set of Allowances for History

Linearizability

Each operation appears to take effect atomically at a specific instant between its invocation and return, respecting actual time ordering. Suitable for scenarios requiring the latest semantic state of a single object, such as locks, master nodes, balances, and unique constraints.

Sequential Consistency

There exists a global total order of all operations, and each client's program order is preserved. However, it does not require that the observed time order across different clients reflect real-world timing.

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, replicas eventually converge. This definition does not specify how long convergence takes, how conflicts are resolved, or whether a client might read its own write.

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

Quorum Formulas Are Not Proofs of Linear Consistency

With N replicas, R + W > N and W > N/2 can cause read-write quorums to overlap, yet concurrency of writes, version selection, retry logic on failure, read repair, and client coordination must still be addressed.

Cassandra’s ALL and QUORUM represent replica acknowledgment levels, they do not merely by name imply that general read-write operations achieve linear consistency. When linearizability conditions are required, explicit consensus or lightweight transaction (LWT) mechanisms provided by the product must be used, and their specific guarantees must be carefully evaluated.

Selecting Guarantees Based on Invariants

Requirement	May Require
Unique username	Linearizability condition or a single authoritative owner
Immediate visibility after user modification	Read-your-writes session guarantee
Causal operations in collaborative editing	Causal metadata or specialized coordination algorithms
Analytics and recommendations	Acceptable latency with eventual consistency projections
Audit timeline	Physical time plus causal or sequence metadata

Begin by assessing whether business exceptions can be tolerated, then select storage mechanisms and communication protocols, never infer requirements from product marketing claims about "consistency."

References

• Leslie Lamport, Time, Clocks, and the Ordering of Events in a Distributed System
• Viotti, Vukolić, Consistency in Non-Transactional Distributed Storage Systems