Light Cone Consistency: Toward a Unified Theory of Consistency in Message-Passing Systems Rob Landers # Swytch BV, Utrecht, The Netherlands
Kaben Kramer # Swytch BV, Utrecht, The Netherlands
arXiv:2605.09114v1 [cs.DC] 9 May 2026
Abstract Every distributed system—databases, networks, postal services, CPU caches—is a message-passing system. Every message-passing system is a growing causal log observed by a set of observers. We present Light Cone Consistency (LCC), a framework that describes every known consistency model as a configuration of three constraints on each observer’s visible sub-DAG: causal closure C(deps), fork resolution O(π), and timeliness R(δ), plus an orthogonal return-value function F . We map 85 configurations, covering all 50+ named models from Viotti and Vukolić’s taxonomy [29], with caveats for fork-based and probabilistic models (Appendix B). We show that three impossibility results of distributed computing—CAP [17], FLP [15], and AFC [4]—each constrain exactly one pair of parameters, and prove they are minimal and independent. Our central result is the observation that these three constraints are fully entangled: violation of any one surface cascades to the other two, because restoring any parameter requires messages—and those messages are subject to all three constraints. The three parameters and their pairwise impossibility surfaces form a fully connected triangle. Every distributed system must exit the triangle by relaxing at least one parameter. The triangle activates only when the system is in use: C = ̸ none, O = ̸ trivial, or R ̸= absent each introduces a constraint that exposes the system to the surfaces. A system that demands nothing—or writes far slower than its propagation delay—is trivially linearizable. We identify open problems including a conjectured fourth surface (log locality), undiscovered constraints, and the universality of the safety–liveness fork as the consequence of crossing any boundary. 2012 ACM Subject Classification Theory of computation → Distributed algorithms; Computer systems organization → Distributed architectures Keywords and phrases distributed systems, consistency models, causal DAG, CAP, FLP, AFC, light cone consistency, impossibility results
1
Introduction
A letter is sent. The recipient reads it. If the recipient has also received an earlier letter on which this one depends, they have causal closure. If multiple letters arrive and the recipient reads them in a specific sequence, they have ordering. If the letter arrives within three business days, they have timeliness. A database write propagates to a replica. If the replica has all causally prior writes, it has causal closure. If all replicas agree on the sequence of writes, they have ordering. If the write arrives within 50 milliseconds, the system has timeliness. These are the same system. This paper presents a framework that makes this precise and reveals a structural relationship between the impossibility results that constrain all such systems.
1.1
The Framework
Every message-passing system is a growing causal directed acyclic graph (DAG) observed by a set of nodes. Messages are vertices. Causal dependencies are edges. Each observer sees a sub-DAG that grows monotonically over time. Every consistency guarantee is a constraint on
2
Light Cone Consistency: Toward a Unified Theory of Consistency in Message-Passing Systems
the shape, ordering, and growth rate of each observer’s visible sub-DAG. Every impossibility result is a statement about which combinations of constraints are simultaneously achievable. We define three parameterized constraints on visibility: C(deps): Causal closure. What must you have seen before you see this message? O(π): Fork resolution. When concurrent branches diverge, how much ambiguity is resolved into a deterministic sequence? R(δ): Timeliness. How quickly does a message enter your visible sub-DAG? A fourth component, the return-value function F , determines what value an observer reports given its visible sub-DAG. F is orthogonal to the impossibility surfaces (Theorem 12).
1.2
The Surfaces
Three impossibility results of distributed computing—two classical (CAP, FLP) and one recent (AFC)—each constrain one pair of parameters: Surface
Constrains
Statement
CAP [17] FLP [15] AFC [4]
C ×R O×R C ×O
Causal closure forces R ≥ partition duration Fork resolution prevents bounded R under async Resolving all forks in a closed sub-DAG requires a serializer
We prove these are minimal and independent (Theorem 21).
1.3
The Triangle
Our central observation is that these three constraints are not independent walls. They are six edges of a fully connected graph on three parameters. Violation of any surface cascades to the other two: R fails → C breaks (partition delivers messages without ancestors) and O breaks (delay prevents consensus). C fails → O breaks (incomplete history causes fork misclassification) and R is constrained (enforcing closure requires waiting). O fails → R is constrained (failed ordering blocks dependent messages) and C breaks (authority change loses uncommitted history). Restoring any parameter requires messages. Those messages are subject to all three constraints. The parameters are fully entangled through the message structure of the DAG. Every distributed system must exit the triangle by relaxing at least one parameter. Raft [26] relaxes O during leader election. CRDTs [28] set O = trivial permanently. Dynamo [14] relaxes C. Spanner [13] pays TrueTime to minimize R. The triangle has a precondition: the system must be in use. The origin—C(none), O(trivial), R(absent)—is an unread log. No causal structure to maintain (C), no ordering to contest (O), no delivery to guarantee (R). The moment someone reads the log, they create a message. That message needs delivery (R activates), may need ordering relative to other messages (O activates), and may need its causal ancestors (C activates). Each non-trivial parameter choice exposes the system to the surfaces that constrain it. A system that writes far slower than its propagation delay produces no concurrent events, and the surfaces are never approached—every operation completes and propagates before the next begins. This is not a new impossibility result. It is a structural observation about the relationship between three known results that, to our knowledge, has not been stated.
Landers & Kramer
1.4
Contributions
1. A framework generating the full consistency hierarchy from three parameterized constraints on a causal DAG, verified complete against Burckhardt’s abstract execution framework [10] (Theorem 14, Appendix A). 2. The three impossibility surfaces are minimal and independent (Theorem 21). 3. The three surfaces form a fully connected triangle (Section 5.5): violation of any surface cascades to the other two through the message structure of the DAG. 4. The safety–liveness fork: a system in the triangle must sacrifice either safety (holographic divergence—observers proceed with irreconcilable sub-DAGs) or liveness (deadlock— observers block), conjectured as the universal consequence of all three surfaces (Section 5.5, Conjecture 31). 5. Identification of open problems: log locality, undiscovered surfaces, universality of the safety–liveness fork.
1.5
Roadmap
Section 2 defines the system model. Section 3 introduces the three visibility constraints and the return-value function. Section 4 demonstrates completeness. Section 5 presents the impossibility surfaces, proves minimality, proves the triangle, and conjectures the safety– liveness fork. Section 6 discusses open problems. Section 7 surveys related work. Section 8 concludes.
2
System Model
▶ Definition 1 (Causal DAG). A causal DAG is a directed acyclic graph G = (M, E) where: M is a set of messages (vertices). A message is an atomic point event—a write, a packet, an operation, a letter, a signal. E ⊆ M × M is a set of dependency edges. An edge (m′ , m) indicates that m causally depends on m′ : the creator of m had observed m′ before creating m. The transitive closure of E defines the causal past of each message: deps ∗ (m) = {m′ : there exists a directed path from m′ to m in G}. Messages with no directed path between them are concurrent. ▶ Definition 2 (System). A system consists of: A causal DAG G = (M, E) that grows over time as new messages are created. A set N of observers (nodes, processes, replicas, recipients). A visibility predicate seen(n, m, t) ∈ {true, false}, indicating whether observer n has seen message m by time t. The visible sub-DAG of observer n at time t is V (n, t) = {m ∈ M : seen(n, m, t)} together with the edges of G restricted to V (n, t). ▶ Definition 3 (Monotonic Visibility, Axiom 1). Once seen, always seen: ∀n, m, t1 , t2 : t1 ≤ t2 ∧ seen(n, m, t1 ) =⇒ seen(n, m, t2 ) Observers accumulate messages; they never lose them.
3
4
Light Cone Consistency: Toward a Unified Theory of Consistency in Message-Passing Systems
▶ Definition 4 (Creator Visibility, Axiom 2). The creator of a message sees it immediately. Read-your-writes is not a consistency guarantee; it is a tautology. ▶ Definition 5 (Observation Induces Dependency, Axiom 3). If the creator of message m has seen message m′ before creating m, then (m′ , m) ∈ E: ∀m, m′ ∈ M : seen(creator(m), m′ , tcreate (m)) =⇒ (m′ , m) ∈ E This is Lamport’s happened-before relation [22] encoded as DAG structure: observation before creation produces a causal edge. It is the axiom that makes the DAG a causal DAG—connecting the visibility predicate to the edge set. ▶ Definition 6 (Correct Observer). An observer n is correct if it does not permanently crash. No further assumptions are made. The model does not require reliable channels, bounded delays, synchronized clocks, or any particular failure model. The only structure is the DAG, the visibility predicate, and the three axioms connecting them.
3
Three Visibility Constraints and a Return-Value Function
A consistency configuration is a tuple F (C, O, R).
3.1
Causal Closure: C(deps)
▶ Definition 7 (Causal Closure). For a dependency filter deps : M → P(M ): ∀n, m, t : seen(n, m, t) =⇒ ∀m′ ∈ deps(m) : seen(n, m′ , t) The filter determines which edges must be respected. Different choices: deps none : deps(m) = ∅. No closure. deps key : Closure within same-key sub-DAG. deps session : Closure within same-session sub-DAG. deps explicit : deps(m) = {m′ : (m′ , m) ∈ E}. Full closure.
3.2
Fork Resolution: O(π)
The causal DAG provides a partial order. Concurrent messages—vertices with no directed path between them—are unordered. These are forks. Fork resolution determines how much ambiguity is resolved. ▶ Definition 8 (Fork Resolution Scope). For a partitioning function π : M → K, O(π) requires that within each equivalence class, all forks are resolved into a total order ≺k , and visibility respects this order: ∀n, k, m1 , m2 ∈ π −1 (k), t : seen(n, m2 , t) ∧ m1 ≺k m2 =⇒ seen(n, m1 , t) Scope ranges: O(trivial): No fork resolution. Partial order only. O(πkey ): Forks resolved per key. O(πobserver ): Each observer resolves forks independently. O(πall ): Global total order. All observers agree. The mechanism of resolution—serialization, fork-choice, consensus, algebraic merge—is an implementation concern, not a consistency property.
Landers & Kramer
3.3
Timeliness: R(δ)
▶ Definition 9 (Timeliness). For a bound δ ∈ [0, ∞]: ∀n ∈ correct(N ), ∀m ∈ M : ∃t : elapsed(m, n, t) ≤ δ ∧ seen(n, m, t) where elapsed(m, n, t) is the propagation time of message m from its creator to observer n—the time the message spends in flight. This requires no clock synchronization and no drift bounds. The only measurement is the message’s own transit: it was created, it arrived, and the difference is elapsed. The message is its own clock. R(absent): No delivery guarantee. R(∞): Eventual delivery. Liveness. R(δ): Bounded delivery. R(0): Instantaneous delivery. The traditional liveness property L is exactly R(∞). Real-time ordering is not fundamental. It emerges when R(δ) is small relative to intermessage gaps. When R is large, different observers may disagree on temporal ordering. This is the relativity of simultaneity, not an approximation of it [27, 16].
3.4
Return-Value Function: F
C, O, and R determine the visible sub-DAG. F determines what value an observer reports from it. ▶ Definition 10 (Return-Value Function). F (q, V (n, t), ≺n ) → Values. ▶ Theorem 11 (Ordering of Return-Value Functions). Return-value functions form a partial order under restrictiveness: Flatest ≤ Fk-latest ≤ Fany-concurrent ≤ Fanything , and independently Flatest ≤ Fcomputed ≤ Fmulti . Fcomputed and Fany-concurrent are incomparable. Proof. By inclusion of return-value sets at each input. Flatest returns exactly one value (the most recent in ≺n ). Each successive function may return a strict superset. Fcomputed returns exactly one value (the output of a deterministic function over the sub-DAG), which may or may not be the latest. Fany-concurrent returns any concurrent value, which may not be the computed value. Neither contains the other. ◀ ◀ ▶ Theorem 12 (Orthogonality). F is independent of the impossibility surfaces. Changing F does not move a system across CAP, FLP, or AFC. The cost of consistency is entirely in visibility (C, O, R). Proof. The surfaces constrain what is visible, in what order, how quickly. F operates on the visible sub-DAG after construction. No impossibility result constrains the mapping from sub-DAGs to return values. ◀ ◀ Strong eventual consistency = Fcomputed (C(none), O(trivial), R(∞)). Causal+ consistency = Fcomputed (C(explicit), O(trivial), R(∞)). The difference between “eventual” and “strong eventual” is entirely in F .
5
6
Light Cone Consistency: Toward a Unified Theory of Consistency in Message-Passing Systems
3.5
Configuration Space
▶ Definition 13 (Configuration). A consistency configuration σ = F (C(deps), O(π), R(δ)). The configuration space Σ is the set of all tuples (F, deps, π, δ).
4
Completeness
▶ Theorem 14 (Completeness). Every consistency predicate expressible as a conjunction of standard axioms in Burckhardt’s abstract execution framework [10] maps to an LCC configuration. LCC is strictly more expressive (Corollary, Section 4). Proof sketch. Burckhardt’s predicates constrain four relations: vis, ar, rb, so. Each maps to an LCC parameter: vis → C(deps), ar → O(π), rb → R(δ), RVAL → F . Full proof in Appendix A. ◀ ◀ ▶ Corollary 15 (Strict Expressiveness). LCC is strictly more expressive: it includes R(absent), O(πobserver ), and continuous R(δ). We enumerate 85 configurations in Appendix B, mapping all 50+ models from Viotti and Vukolić [29]—with caveats for fork-based, probabilistic, and release/acquire models—plus 26 additional unnamed configurations.
4.1
Selected Configurations #
C
O
R
Name
Example
1 2 8 16 30 40 48 50 51 52
none none none none session explicit explicit explicit explicit explicit
trivial trivial πsession all∗ trivial trivial πobserver all all all∗
absent ∞ ∞ 0 ∞ ∞ δ ∞ δ 0
No guarantees Eventual consistency Per-session ordered Instant total order PRAM Causal consistency Bounded scoped causal Sequential consistency Bounded sequential Linearizability
UDP, unreliable mail Dynamo [14], postcards TCP, registered mail Network switch Read-your-writes COPS [24] Special relativity ZooKeeper [21] Spanner [13] Single-node
∗
Under R(0), all messages are instantly visible, so every message causally depends on all prior messages—the DAG is a chain with no forks. The five O choices collapse to a single equivalence class; rows 16 and 52 are both representatives, with O(all) chosen as the canonical label since it is vacuously satisfied: there are no concurrent messages to order.
4.2
Universality of the Model
The causal DAG describes every message-passing system, not only databases:
Postal services. A letter is a message. The postal route is the causal path. The sorting facility is the serialization point. R(δ) is “3–5 business days.” A contract requiring both signatures is a transaction: an envelope message whose edges include the constituent letters. Delivery confirmation is the commit notification.
Landers & Kramer
CPU cache coherence. A store is a message. The cache coherence protocol determines C and R(δ). The memory model is a consistency configuration.
Network protocols. A packet is a message. TCP provides O(πsession ). UDP provides O(trivial). BGP reconvergence is fork resolution after a topology change.
Consensus protocols. Each proposal and vote is a message. The commit decision is an envelope message whose edges include a quorum of votes. The leader is the serialization point. Transactions in any of these systems are envelope messages: a message whose causal past includes the constituent operations. Seeing the envelope requires seeing all operations it depends on (by C).
5
Impossibility Surfaces and the Consistency Triangle
5.1
The CAP Surface: C × R
▶ Theorem 16 (CAP, after Gilbert and Lynch [17]). During a network partition of duration p: C(deps ̸= none) ∧ R(δ < p) is unachievable. Proof. Let (m′ , m) ∈ E with m′ on side A, m on side B. C requires m′ ∈ V (b, t) for any b with m ∈ V (b, t). R(δ) requires m ∈ V (b, t) within δ. If δ < p, m enters b’s sub-DAG before m′ can cross the partition. The sub-DAG is not downward-closed. ◀ ◀
5.2
The FLP Surface: O × R
▶ Theorem 17 (FLP, after Fischer, Lynch, and Paterson [15]). In an asynchronous system with at least one crash failure: O(πall ) ∧ R(δ) for deterministic finite δ is unachievable. Proof. O(πall ) requires global agreement on a total order extending the DAG’s partial order. This is a consensus problem. By FLP, no deterministic protocol guarantees termination in bounded steps under asynchrony with crashes. Fork resolution cannot be bounded by finite δ. ◀ ◀ ▶ Remark 18. Randomized protocols (e.g., Ben-Or [7]) achieve probabilistic termination under asynchrony with crashes. Theorem 17 applies to deterministic protocols only. Extending the framework to probabilistic R(δ) bounds is noted as future work (Appendix B, PBS models).
5.3
The AFC Surface: C × O
▶ Theorem 19 (AFC, after Attiya, Enea, and Román-Calvo [4]). C(deps explicit ) ∧ O(πall ) under R ̸= R(0) is not achievable in an available (wait-free) implementation.
7
8
Light Cone Consistency: Toward a Unified Theory of Consistency in Message-Passing Systems
Proof. We reduce to AFC by constructing the storage specification in AFC’s framework and showing it is not arbitration-free. AFC [4] defines a storage specification as (CMod, OpSpec) where CMod is a consistency model expressed over relations vis (visibility), ar (arbitration), so (session order), wr (writeread), and rb (returns-before). A consistency model is arbitration-free if its formula, in normal form, does not use the ar relation. The AFC theorem (Theorem 8.1, generalizing the earlier Theorem 6.3) states: a storage specification admits an available implementation if and only if it is arbitration-free. We construct the specification. Step 1: C(deps explicit ) → causal visibility. C(deps explicit ) requires downward closure under all causal edges. In AFC’s framework, causal visibility is expressed as (so ∪ wr)+ ⊆ vis: the transitive closure of session order and write-read edges is contained in visibility. The LCC dependency edges E include both so edges (same-observer sequential messages, by Definition 5) and wr edges (read-after-write dependencies). Therefore C(deps explicit ) corresponds to causal visibility in AFC’s framework. Step 2: O(πall ) under R ̸= R(0) requires ar. O(πall ) demands a global total order ≺ over all messages, including concurrent messages. Under any R ̸= R(0), concurrent messages exist: messages created at different observers within the propagation window have no causal path between them (no edge in E, no so, wr, or rb relationship). The relations so, wr, rb, vis cannot order these messages: so orders only within a session; wr orders only write-read pairs; rb orders only real-time separated pairs (gap > δ); vis records what is visible, not the order. No formula over {vis, so, wr, rb} alone can produce a total order over concurrent messages, because these relations provide no information about the relative ordering of causally independent events. The ar relation exists in AFC’s framework precisely to order events that the other relations cannot. Therefore, any CMod formula expressing O(πall ) under R ̸= R(0) must use ar. The specification is not arbitration-free. Step 3. By the AFC theorem [4, Theorem 8.1], a specification that is not arbitration-free does not admit an available implementation. ◀ ◀ ▶ Remark 20 (R(0) escape). Under R(0), all messages are instantly visible. Every message’s creator has seen all prior messages (by R(0)), so every subsequent message causally depends on all prior messages (by Definition 5). The DAG is a chain—no concurrent messages exist. O(πall ) is vacuously satisfied: there are no concurrent events to arbitrate, so ar is not needed. The specification is arbitration-free. This is why linearizability (C(explicit), O(all), R(0)) is achievable on a single node: instantaneous visibility eliminates concurrency, which eliminates the need for arbitration. More generally, any system that writes far slower than R(δ) achieves the same effect: if every operation completes and propagates before the next begins, no concurrent events exist and the specification is vacuously arbitration-free.
5.4
Minimality
▶ Theorem 21 (Minimality). Each surface is independent: none is implied by the other two. Proof. We exhibit three configurations, each violating exactly one surface. (a) C(explicit), O(trivial), R(δ < p) violates CAP but not FLP or AFC. CAP violated: C(explicit) ∧ R(δ < p) during partition (Theorem 16). FLP not violated: O(trivial) requires no fork resolution, so O(all) ∧ R(δ) is not demanded. AFC not violated: O(trivial) requires no total order, so C ∧ O does not require a serializer. (b) C(none), O(all), R(δ) violates FLP but not CAP or AFC. FLP violated: O(all) ∧ R(δ) under async with crashes (Theorem 17). CAP not violated: C(none) imposes no closure
Landers & Kramer
requirement, so C × R is unconstrained. AFC not violated: C(none) imposes no closure requirement, so C(explicit) ∧ O(all) is not demanded. (c) C(explicit), O(all), R(absent) violates AFC but not CAP or FLP. AFC violated: C(explicit) ∧ O(all) requires a serializer (Theorem 19). CAP not violated: R(absent) imposes no timeliness bound, so C × R is unconstrained regardless of partition duration. FLP not violated: R(absent) is not a finite δ, so O(all) ∧ R(δ) for finite δ is not demanded. ◀ ◀ ▶ Conjecture 22 (Sufficiency). The three surfaces are sufficient to describe the boundary of the achievable region: any F (C, O, R) not violating any surface is achievable. We do not prove this. For every named model, production systems exist within the achievable region (Appendix B). The 85 configurations enumerated in Appendix B are not ruled out by the three surfaces; whether all are achievable remains open.
5.5
The Consistency Triangle
The three surfaces are not independent walls in a configuration space. They are six edges of a fully connected graph on three parameters. Violating any surface cascades to the other two, because restoring any parameter requires messages—and those messages are subject to all three constraints. ▶ Lemma 23 (Fork Misclassification). Let G = (M, E) be a causal DAG and let V ⊂ M be an incomplete visible sub-DAG (not downward-closed: there exist m ∈ V and m′ ∈ deps(m) such that m′ ∈ / V ). Then the visible causal past of m in V is a strict subset of its true causal past in G, and any fork resolution function that depends on causal past may produce different results on V than on G. Proof. Let m ∈ V with m′ ∈ deps(m) and m′ ∈ / V . The edge (m′ , m) exists in G but not in the sub-DAG induced by V . Therefore deps V (m) ⊂ deps G (m): the observer sees a strict subset of m’s true causal past. This has two consequences. First, m′ is causally before m in G, but the observer sees no evidence of this relationship. If m′ is also absent from V , the observer cannot determine whether m′ and m are causally ordered or concurrent. Second, any fork resolution function f that takes the visible sub-DAG as input operates on incomplete information: f (V ) ̸= f (V ′ ) for two observers with different incomplete sub-DAGs V, V ′ of the same G. Therefore, two observers with different missing ancestors may produce different fork resolutions of the same messages. ◀ ◀ Example. An observer receives a late fee (message m) but not the original bill (message m′ , where (m′ , m) ∈ E). The late fee appears as a root in the observer’s sub-DAG—no parents, no context. The observer cannot distinguish “I missed the original bill” (causally ordered, edge exists in G but invisible in V ) from “billing error” (concurrent, no edge in G). The two cases require different responses. Without the missing ancestor, the observer may resolve the fork incorrectly. ▶ Lemma 24 (Ordering-Dependent Message Creation). In a system with O(π) for π = ̸ trivial, let m1 , m2 be concurrent messages within the same equivalence class of π that have been resolved into an order m1 ≺ m2 . Any subsequent message m3 in the same equivalence class, created by an observer who has seen both m1 and m2 , must include the ordering decision in its causal past: m3 follows m2 , so (m2 , m3 ) ∈ E and transitively (m1 , m3 ) ∈ E ∗ . If the ordering decision has not been made (O failure), the creator of m3 cannot determine which of m1 , m2 to follow. No m3 consistent with O(π) can be constructed: either the system
9
10
Light Cone Consistency: Toward a Unified Theory of Consistency in Message-Passing Systems
blocks (no message, R violated for m3 ) or it creates a message that violates O(π). In both cases, the system has exited its configured guarantees. Messages outside the contested equivalence class are not affected. The edge O → R is scoped to the equivalence class where ordering has failed. Proof. By Definition 8, O(π) requires visibility to respect the ordering: seen(n, m2 , t) ∧ m1 ≺ m2 =⇒ seen(n, m1 , t). A new message m3 in the same class must be placed in the total order. Its creator must know the current tail of the order to create m3 with the correct causal edges. Without a resolved ordering of m1 and m2 , the creator cannot determine whether m3 follows m1 or m2 . Creating m3 with an incorrect causal past violates O(π). Therefore, either m3 is not created (R violated) or m3 is created with incorrect causal edges (O violated). The system cannot satisfy both O and R simultaneously for messages in the contested equivalence class. ◀ ◀ ▶ Lemma 25 (Ordering Decisions as Messages). In any system with O(π) for π = ̸ trivial that continues to operate (new messages are created), failed ordering produces missing causal context for subsequent messages. Proof. Let m1 , m2 be concurrent messages whose ordering has been resolved at some observers but not all. The resolution is communicated as a message r in the DAG: a vertex whose causal past includes the resolved messages. Let observer a have resolved the ordering (r ∈ V (a, t)) and create a subsequent message m3 with (r, m3 ) ∈ E. Let observer b have seen m1 and m2 but not r (r ∈ / V (b, t)). If m3 is delivered to b, then m3 ∈ V (b, t′ ) for some t′ > t. But r ∈ deps(m3 ) and r∈ / V (b, t′ ). C is violated at observer b: the sub-DAG is not downward-closed. This applies regardless of protocol: in a leader-based system, r is the leader’s commit decision; in a leaderless system, r is an observer’s fork-choice message that other observers have not yet received. ◀ ◀ ▶ Theorem 26 (The Consistency Triangle). The three parameters C, O, and R are fully entangled through the message structure of the causal DAG. Violation of any one surface cascades to the other two. Proof. We establish all six directed edges between the three parameters. R → C (Partition breaks closure). A partition delays message delivery. A message arrives at an observer before its causal ancestors. The observer’s sub-DAG is not downward-closed: C is violated. (CAP, Theorem 16.) R → O (Delay breaks ordering). Asynchronous delay prevents consensus from terminating in bounded time. Fork resolution cannot be guaranteed within any finite δ. O is violated directly, without requiring C violation. (FLP, Theorem 17.) C → O (Incomplete history breaks ordering). By Lemma 23, an incomplete sub-DAG causes the observer to misclassify causally ordered messages as concurrent. Fork resolution produces orderings inconsistent with the true causal structure G. Any O ̸= trivial is affected. C → R (Enforcing closure costs timeliness). If a system enforces C, receiving a message without its ancestors requires waiting for the ancestors before accepting the message. Enforcing closure constrains R: delivery is delayed until the causal past is complete. (CAP read in the other direction: C forces R ≥ partition duration.) O → R (Failed ordering prevents message creation). By Lemma 24, in a system with O ̸= trivial, a message whose creation depends on the ordering decision cannot be constructed until the ordering is resolved. If ordering fails, such messages do not exist and cannot be delivered: R is violated.
Landers & Kramer
11
O → C (Failed ordering creates missing causal context). By Lemma 25, in a system with O = ̸ trivial that continues to operate, ordering decisions are messages in the DAG. If ordering fails or is resolved at some observers but not others, subsequent messages created by observers with the resolution carry causal dependencies on the resolution message. Observers who receive these subsequent messages without the resolution have incomplete sub-DAGs: C is violated. All six directed edges are established. The three parameters form a fully connected graph: failure in any one cascades to both others. Each edge is conditional: the cascade from X to Y occurs only when the system demands Y . A system that relaxes Y is not subject to the X → Y edge—it has exited the triangle at vertex Y . This is the mechanism by which systems escape the triangle (Corollary 32): relaxing a parameter removes the edges that target it. ◀ ◀ From
To
Mechanism
R R C C O O
C O O R R C
Partition → missing ancestors (CAP) Delay → consensus can’t terminate (FLP) Incomplete history → fork misclassification (Lemma 23) Enforcing closure → must wait for ancestors Failed ordering → no valid message to deliver (Lemma 24) Failed ordering → missing ordering messages (Lemma 25)
▶ Remark 27 (Formal status of edges). The six edges have different formal origins. R → C and R → O are established impossibility theorems (CAP [17] and FLP [15]). C → O is Lemma 23 (fork misclassification). O → R is Lemma 24. O → C is Lemma 25. C → R is CAP read in the reverse direction: not a separate impossibility result but a consequence of the same surface. The triangle’s contribution is not six new impossibility results but the proof that these six dependencies—two established theorems, three new lemmas, and one surface read bidirectionally—connect the same three parameters into a fully entangled structure. ▶ Remark 28 (The triangle is the recovery protocol). The triangle is not a hypothetical that never executes. Every leader-based system’s recovery mechanism—leader election in Raft, proposer change in Paxos—is a traversal of the triangle. The leader was the system’s chosen exit point. When the leader fails, the system enters the triangle: it runs a leaderless protocol (voting, consensus) to re-establish the exit point. In leaderless systems, the triangle manifests as competing fork resolutions: observers make independent ordering decisions that other observers have not yet received. The triangle describes what happens whenever ordering is contested. ▶ Remark 29 (Protocols choose where to exit). Protocols such as last-writer-wins (LWW) exit the triangle by giving up causal closure. LWW accepts incomplete histories and resolves forks using physical timestamps, which are not part of the causal DAG. The triangle describes constraints at the message level. Protocols choose which constraint to relax in order to exit. ▶ Definition 30 (Holographic Divergence). Holographic divergence occurs when two or more observers hold visible sub-DAGs that are individually consistent but mutually irreconcilable under the configured constraints. ▶ Conjecture 31 (Safety–Liveness Fork). A system that enters the consistency triangle without relaxing any parameter must sacrifice either safety or liveness.
12
Light Cone Consistency: Toward a Unified Theory of Consistency in Message-Passing Systems
Proceed without resolution (sacrifice safety): observers continue with incomplete, inconsistent, or irreconcilable sub-DAGs—holographic divergence. Wait for resolution (sacrifice liveness): observers block until the violated parameter is restored—deadlock or stasis. This is the same choice at every surface: CAP: serve stale data (safety) or become unavailable (liveness). FLP: decide different values (safety) or wait forever (liveness). AFC: arbitrate independently (safety) or block for a serializer (liveness). The triangle does not introduce a new tradeoff. It reveals that all three surfaces share the same fundamental consequence, and that a system can arrive at any surface through multiple cascade paths (Theorem 26). A system designed to handle one entry path (e.g., partition → CAP) may be surprised by another (e.g., ordering failure → O → C cascade → same CAP surface). Once in the triangle, a system must relax at least one parameter to exit. The choice of which parameter to relax determines the outcome: Relax R (accept delayed delivery): the system returns to normal operation when the partition heals and missing messages arrive. Relax O (accept inconsistent orderings): observers diverge on ordering but each observer’s sub-DAG is internally consistent. The system returns to normal when consensus terminates. Relax C (accept incomplete histories): observers proceed with incomplete sub-DAGs. If the missing information never arrives or arrives after irreconcilable decisions have been made, the divergence is permanent. ▶ Corollary 32 (Every System Exits the Triangle). Every non-trivial distributed system must exit the triangle by relaxing at least one parameter. The choice determines the system’s consistency guarantees: System
Relaxes
Gives up
Gains
Raft, Paxos CRDTs Dynamo Spanner Postal service
O during election O (= trivial) C (= none) R (pay TrueTime) R (tolerate delay)
Availability during partition Global total order Causal consistency Latency Timeliness
Strong ordering Availability Low latency Strong consistency Reliability
Corollary 32 describes how systems choose to exit the triangle. The claim that failure to exit forces a safety–liveness fork is Conjecture 31, not Theorem 26. ▶ Corollary 33 (No Free Lunch). The origin (C = none, O = trivial, R = absent) is the only configuration that trivially avoids the triangle. Every non-trivial configuration is exposed to at least one edge. ▶ Remark 34 (The triangle’s precondition). The triangle presupposes that the system is in use— that at least one parameter is non-trivial. At the origin (C = none, O = trivial, R = absent), the system is an unread log: no causal structure to maintain, no ordering to contest, no delivery to guarantee. The surfaces do not apply. Each non-trivial parameter choice introduces a constraint that exposes the system to the surfaces: O ̸= trivial means concurrent events must be ordered; R ̸= absent means messages must be delivered; C ̸= none means causal structure must be maintained.
Landers & Kramer
13
The triangle is also workload-relative. A system that writes far slower than its propagation delay (the inter-operation gap τ exceeds δ) produces no concurrent events. The DAG is a chain. Every parameter is trivially satisfied. At high operation rates (τ ≪ δ), concurrent events are abundant, the surfaces activate, and the system must exit the triangle by relaxing a parameter. The configurations in LCC describe behavior under concurrency—the regime where consistency tradeoffs matter. ▶ Remark 35 (Byzantine Faults). Byzantine faults and holographic divergence share a structural consequence: irreconcilable forks in the DAG. A Byzantine node produces either a compatible sub-DAG (indistinguishable from correct) or an incompatible one. However, Byzantine fault models involve adversarial behavior—equivocation (presenting different messages to different observers) and selective message delivery—which is structurally different from the “honest disagreement” in holographic divergence. Fork-linearizability [25] was designed precisely to handle equivocation. The framework can express fork-based consistency models as (C, O, R) configurations applied per-branch after a fork, but a full treatment of Byzantine behavior within LCC is beyond the scope of this paper.
6
Open Problems
6.1
Log Locality
The triangle establishes that restoring ordering requires an authority, and the authority communicates via messages. These messages travel from a physical location. We conjecture this is a fourth impossibility surface. ▶ Conjecture 36 (Log Locality). A total order over events from spatially separated sources requires a physical serialization point. The ordering is unavailable to any other location for time ≥ d/c. This is the physics projection of C × O: AFC tells you a log requires a serializer (logic); log locality tells you the serializer requires a location (physics). A recent independent preprint in financial markets [9]1 proves that the NBBO—a total order over prices across spacelike-separated exchanges—is frame-dependent: the ordering depends on the location of the consolidation point, with approximately $5 billion per year extracted from this gap.
6.2
Physics and Logic Projections
Each pair of parameters may have both a physics projection (constraints from finite propagation speed) and a logic projection (constraints from the structure of concurrent events). Three projections are known:
1
Pair
Physics
Logic
C ×R O×R C ×O
CAP FLP Log locality (conjectured)
? (metadata growth) ? (history complexity) AFC
Non-peer-reviewed self-published technical report; we cite it as a contemporaneous independent observation rather than as a verified theorem.
14
Light Cone Consistency: Toward a Unified Theory of Consistency in Message-Passing Systems
C × R logic projection. Maintaining causal closure requires tracking dependencies. Under eventual delivery, this metadata accumulates without bound. Lower bounds on vector clock size exist [12]; lower bounds on tombstone metadata exist [3]. A formal impossibility result connecting C to R via metadata cost has not been stated as a single theorem.
O × R logic projection. Wider timeliness bounds produce more concurrent events. More concurrent events require more ordering decisions. The space of possible orderings grows combinatorially. Lower bounds on consensus time grow with concurrency [6, 23]. We are not aware of a unified formal result.
6.3
Universality of Holographic Divergence
▶ Conjecture 37 (Universality). The safety–liveness fork is the universal consequence of crossing any boundary of the achievable region, not just the three known surfaces. All three known surfaces force the same choice: proceed without resolution (safety violation) or wait for resolution (liveness violation). We conjecture this holds for any future impossibility surface, including the conjectured log locality surface and the undiscovered C × R and O × R logic projections. If Conjecture 37 holds, the framework’s boundaries reduce to a single structural consequence: every impossibility surface is a point where a system must choose between safety and liveness.
7
Related Work
Consistency taxonomies. Viotti and Vukolić [29] surveyed 50+ consistency models. Burckhardt [10] formalized consistency as predicates over abstract executions. Almeida [1] composes consistency from binary axioms (Closed past, Local visibility, Arbitration, Monotonic visibility) and derives the CLAM impossibility theorem, extending CAP. Almeida independently grounds his framework in relativistic “physical happens-before” via light cones—the closest existing work to our approach. LCC extends these by parameterizing constraints with continuous ranges and revealing the cyclic relationship between impossibility surfaces.
Comparison with Almeida’s CLAM framework. Almeida [1] independently develops a consistency framework grounded in relativistic “physical happens-before” via light cones and derives the CLAM impossibility theorem. LCC and CLAM share the observer-centric, physics-aware foundation. They answer different questions. CLAM proves a new impossibility theorem—it adds a brick to the wall. LCC reveals the structure connecting the existing impossibility theorems—it shows the bricks form a wall, and the wall is a triangle. CLAM cannot express this structure because it encodes availability as a parameter rather than deriving it from surfaces. The frameworks differ in four respects. First, CLAM requires Monotonic visibility (eventual delivery) as an axiom; LCC admits R(absent), expressing systems with no delivery
Landers & Kramer
guarantee (e.g., unreliable UDP, fire-and-forget messaging). Second, LCC separates returnvalue semantics (F ) as an orthogonal axis; CLAM does not distinguish what an observer has seen from what it reports. Third, CLAM encodes availability as an explicit parameter (Local visibility); LCC derives availability as a consequence of the impossibility surfaces. A system with C(explicit) + O(all) hits the AFC surface (requires a serializer) and the CAP surface during partitions (R violated). Availability is what is lost—it need not be a separate parameter because the surfaces already determine where it breaks. Fourth, CLAM’s parameterization does not expose the pairwise structure of the impossibility surfaces. LCC’s three-parameter decomposition (C, O, R) makes the pairwise constraints visible: CAP constrains C × R, FLP constrains O × R, AFC constrains C × O. This structure—three surfaces on three pairs—is what reveals the triangle. CLAM’s four-parameter space (C, L, A, M ) does not have this property. Indeed, the CLAM impossibility theorem itself—that C, L, A, M cannot be simultaneously satisfied—is the conjunction of the AFC surface (C + A requires a serializer) and the CAP surface (the serializer is unavailable during partitions), with availability (L) made explicit rather than derived. The underlying structure is two known surfaces; the fourth parameter obscures rather than reveals this. LCC omits availability as a parameter deliberately: availability is a consequence of which surfaces a system hits, not a design choice. A system designer chooses C, O, R. Availability is what remains after the surfaces have constrained those choices.
Parameterized consistency. Yu and Vahdat’s TACT [30] defines three axes measuring quantitative deviation from strong consistency. TACT measures how far from linearizability; LCC specifies structural properties. Golab [19] formally proves PACELC, connecting CAP to latency-consistency tradeoffs during normal operation. The LAW theorem [18] proves local reads are impossible under linearizable asynchronous replication.
Relativistic distributed systems. Schwarz and Mattern [27] drew the analogy between vector time and Minkowski causal structure; the formal correspondence was developed later by Gilbert and Golab [16], who defined relativistic linearizability at DISC 2014, and connects to the causal-set program of Bombelli et al. [8], who proposed spacetime as a locally finite partially ordered set—the same structure as a causal DAG. Lamport [22] acknowledged that special relativity directly inspired the happened-before relation. Burgess [11] models systems as autonomous agents with consistency emerging from local observations.
Impossibility results. Gilbert and Lynch [17] proved CAP. Fischer, Lynch, and Paterson [15] proved FLP. Attiya, Enea, and Román-Calvo [4] proved AFC. Attiya et al. [5] proved that linearizable implementations require hardware synchronization (Laws of Order). Hellerstein conjectured the CALM principle [20] and Ameloot, Neven, and Van den Bussche [2] proved it: monotonic programs have coordination-free implementations. Our contribution is not a new impossibility result but the observation that CAP, FLP, and AFC form a fully connected triangle through the same three parameters.
15
16
Light Cone Consistency: Toward a Unified Theory of Consistency in Message-Passing Systems
8
Conclusion
We have presented Light Cone Consistency, a framework that describes every known consistency model as a configuration of three parameterized constraints on a causal DAG. We verified completeness against Burckhardt’s abstract execution framework, proved the three impossibility surfaces are minimal and independent, and conjectured that crossing any surface forces a safety–liveness fork: a system must either proceed with irreconcilable observer views or block until resolution. Our central observation is that the three surfaces form a fully connected triangle: violation of any surface cascades to the other two, because restoring any parameter requires messages subject to all three constraints. Every distributed system must exit the triangle by relaxing at least one parameter. The framework is intentionally incomplete. We have mapped the territory and identified the gaps. We invite the community to: 1. Prove or refute Conjecture 22 (sufficiency of the three surfaces). 2. Formalize log locality (Conjecture 36) as an impossibility result. 3. Identify the C × R and O × R logic projections as formal theorems. 4. Determine whether additional surfaces exist involving system-scale parameters (node count, throughput, metadata overhead). 5. Prove or refute Conjecture 37 (universality of the safety–liveness fork across all surfaces). The causal DAG is the universal language. Every message-passing system speaks it. The consistency hierarchy is not a ladder to be climbed but a landscape to be explored—and the impossibility surfaces that bound it are not walls but edges of a single, inescapable triangle.
AI Disclosure We used Claude (Anthropic) to assist with proof verification, LaTeX formatting, and adversarial review of arguments. The tool materially affected the entire manuscript. Specifically: Proof verification. Claude was used to check the proofs in Section 5 (CAP, FLP, AFC reductions; minimality; the six triangle edges; Lemmas 23–25) and the Burckhardt mapping in Appendix A for logical gaps, missing cases, and unstated assumptions. LaTeX conformance. Claude was used to convert the source draft into LIPIcs-conforming LaTeX, including theorem environments, cross-references, bibliography entries, and table formatting. Adversarial review. Claude was used to challenge claims, identify weak arguments, surface counterexamples, and stress-test conjectures (Conjectures 22, 31, 36, and 37) before submission. The authors verified the correctness and originality of all content including references, and take full responsibility for any errors, omissions, or misattributions in the final manuscript. References 1 2 3
Paulo Sérgio Almeida. A framework for consistency models in distributed systems. arXiv:2411.16355, 2024. URL: https://arxiv.org/abs/2411.16355. Tom J. Ameloot, Frank Neven, and Jan Van den Bussche. Relational transducers for declarative networking. Journal of the ACM, 60(2):15:1–15:38, 2013. doi:10.1145/2450142.2450151. Hagit Attiya, Sebastian Burckhardt, Alexey Gotsman, Adam Morrison, Hongseok Yang, and Marek Zawirski. Specification and complexity of collaborative text editing. In ACM Symposium on Principles of Distributed Computing (PODC), pages 259–268, 2016.
Landers & Kramer
4
5
6 7
8 9
10 11 12 13
14
15
16
17
18
19 20 21 22 23
Hagit Attiya, Constantin Enea, and Enrique Román-Calvo. Arbitration-free consistency is available (and vice versa). Proc. ACM Program. Lang., 10(POPL):1183–1211, 2026. Article 41. Hagit Attiya, Rachid Guerraoui, Danny Hendler, Petr Kuznetsov, Maged M. Michael, and Martin Vechev. Laws of order: Expensive synchronization in concurrent algorithms cannot be eliminated. In 38th ACM Symposium on Principles of Programming Languages (POPL), pages 487–498, 2011. Hagit Attiya, Nancy Lynch, and Nir Shavit. Are wait-free algorithms fast? Journal of the ACM, 41(4):725–763, 1994. Michael Ben-Or. Another advantage of free choice: Completely asynchronous agreement protocols. In ACM Symposium on Principles of Distributed Computing (PODC), pages 27–30, 1983. Luca Bombelli, Joohan Lee, David Meyer, and Rafael D. Sorkin. Space-time as a causal set. Physical Review Letters, 59(5):521–524, 1987. Paul Borrill. Engineered simultaneity: The physical impossibility of consolidated price discovery across spacelike-separated exchanges. arXiv:2602.22350, 2026. URL: https://arxiv.org/ abs/2602.22350. Sebastian Burckhardt. Principles of eventual consistency. Foundations and Trends in Programming Languages, 1(1–2):1–150, 2014. Mark Burgess and Jan A. Bergstra. Promise Theory: Principles and Applications. 2014. Bernadette Charron-Bost. Concerning the size of logical clocks in distributed systems. Information Processing Letters, 39(1):11–16, 1991. James C. Corbett, Jeffrey Dean, Michael Epstein, Andrew Fikes, Christopher Frost, J. J. Furman, Sanjay Ghemawat, Andrey Gubarev, Christopher Heiser, Peter Hochschild, et al. Spanner: Google’s globally-distributed database. In 10th USENIX Symposium on Operating Systems Design and Implementation (OSDI), pages 251–264, 2012. Giuseppe DeCandia, Deniz Hastorun, Madan Jampani, Gunavardhan Kakulapati, Avinash Lakshman, Alex Pilchin, Swaminathan Sivasubramanian, Peter Vosshall, and Werner Vogels. Dynamo: Amazon’s highly available key-value store. In 21st ACM Symposium on Operating Systems Principles (SOSP), pages 205–220, 2007. doi:10.1145/1294261.1294281. Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson. Impossibility of distributed consensus with one faulty process. Journal of the ACM, 32(2):374–382, 1985. doi:10.1145/ 3149.214121. Seth Gilbert and Wojciech Golab. Making sense of relativistic distributed systems. In 28th International Symposium on Distributed Computing (DISC), volume 8784 of LNCS, pages 361–375, 2014. Seth Gilbert and Nancy Lynch. Brewer’s conjecture and the feasibility of consistent, available, partition-tolerant web services. SIGACT News, 33(2):51–59, 2002. doi:10.1145/564585. 564601. Emmanouil Giortamis, Antonios Katsarakis, Vasilis Gavrielatos, Pramod Bhatotia, Aleksandar Dragojevic, Boris Grot, Vijay Nagarajan, and Panagiota Fatourou. The LAW theorem: Local reads and linearizable asynchronous replication. Proceedings of the VLDB Endowment, 18(9):2831–2845, 2025. doi:10.14778/3746405.3746411. Wojciech Golab. Proving PACELC. ACM SIGACT News, 49(1):73–81, 2018. Joseph M. Hellerstein and Peter Alvaro. Keeping CALM: When distributed consistency is easy. Communications of the ACM, 63(9):72–81, 2020. Patrick Hunt, Mahadev Konar, Flavio P. Junqueira, and Benjamin Reed. ZooKeeper: Wait-free coordination for internet-scale systems. In USENIX Annual Technical Conference, 2010. Leslie Lamport. Time, clocks, and the ordering of events in a distributed system. Communications of the ACM, 21(7):558–565, 1978. doi:10.1145/359545.359563. Leslie Lamport. Lower bounds for asynchronous consensus. Distributed Computing, 19(2):104– 125, 2006.
17
18
Light Cone Consistency: Toward a Unified Theory of Consistency in Message-Passing Systems
24
25 26 27 28
29 30
A
Wyatt Lloyd, Michael J. Freedman, Michael Kaminsky, and David G. Andersen. Don’t settle for eventual: Scalable causal consistency for wide-area storage with COPS. In 23rd ACM Symposium on Operating Systems Principles (SOSP), pages 401–416, 2011. doi:10.1145/ 2043556.2043593. David Mazières and Dennis Shasha. Building secure file systems out of Byzantine storage. In ACM Symposium on Principles of Distributed Computing (PODC), pages 108–117, 2002. Diego Ongaro and John Ousterhout. In search of an understandable consensus algorithm. In USENIX Annual Technical Conference (ATC), pages 305–320, 2014. Reinhard Schwarz and Friedemann Mattern. Detecting causal relationships in distributed computations: In search of the holy grail. Distributed Computing, 7(3):149–174, 1994. Marc Shapiro, Nuno Preguiça, Carlos Baquero, and Marek Zawirski. Conflict-free replicated data types. In 13th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), pages 386–400, 2011. doi:10.1007/978-3-642-24550-3_29. Paolo Viotti and Marko Vukolić. Consistency in non-transactional distributed storage systems. ACM Computing Surveys, 49(1), 2016. Haifeng Yu and Amin Vahdat. Design and evaluation of a conit-based continuous consistency model for replicated services. ACM Transactions on Computer Systems, 20(3):239–282, 2002.
Completeness over Burckhardt’s Abstract Execution Framework
We prove Theorem 14: every consistency predicate expressible in Burckhardt’s abstract execution framework [10] maps to an LCC configuration, and every LCC configuration maps to a Burckhardt predicate.
A.1
Burckhardt’s Framework (Summary)
An abstract execution in Burckhardt’s framework is a tuple A = (E, op, rval, rb, vis, ar) where: E is a finite set of events (operations). op : E → Op labels each event with its operation type. rval : E → Val assigns a return value to each event. rb ⊆ E × E is the returns-before relation: e1 rb e2 if e1 ’s response precedes e2 ’s invocation in real time. rb is an irreflexive partial order. vis ⊆ E × E is the visibility relation: e1 vis e2 means e2 can see e1 . ar ⊆ E × E is the arbitration relation: a total order on events resolving conflicts. A consistency predicate P constrains which abstract executions are legal. Burckhardt also defines session order (so ⊆ E × E), where e1 so e2 if both are in the same session and e1 precedes e2 . Consistency models are defined as conjunctions of axioms over these relations. Representative axioms include EVENTUAL visibility, CAUSAL visibility (vis is transitively closed and includes so), SEQUENTIAL (ar is a total order extending vis), REAL-TIME (rb ⊆ vis), and RVAL.
A.2
The Mapping
Mapping 1: vis → C(deps). Burckhardt’s vis determines which prior events are visible to a given event. LCC’s C(deps) determines which messages must be in an observer’s visible sub-DAG.
Landers & Kramer
19
Burckhardt vis axiom
LCC C(deps)
vis unconstrained so ⊆ vis (session visibility) vis transitively closed +so ⊆ vis vis restricted to same key
C(none) C(session) C(explicit) C(key)
In Burckhardt, e1 vis e2 means “e2 sees e1 .” In LCC, m1 ∈ deps(m2 ) ∧ seen(n, m2 , t) =⇒ seen(n, m1 , t). The structural role is identical: vis constrains what must be observed before an observation is valid. The translation: for each vis axiom “X ⊆ vis,” there exists a deps filter such that C(deps) enforces X ⊆ vis in all executions. Conversely, every deps filter defines a vis constraint. Detail: Burckhardt allows visibility patterns that are not purely causal—for example, prefix-closed visibility where an observer sees a prefix of a total order. In LCC, this corresponds to C(deps) combined with O(πall ): the total order defines the prefix, and C ensures the prefix is downward-closed. No visibility pattern expressible in Burckhardt falls outside the (C, O) parameter space. Detail: Session order (so) interacts with the other mappings. Some Burckhardt predicates constrain so ∩ rb jointly—requiring that same-session operations ordered in real time are visible to each other. In LCC, same-session operations are created by the same observer. By Creator Visibility (Definition 4), an observer always sees its own prior messages. Therefore so ∩ rb ⊆ vis is guaranteed by Definition 4 for any configuration with C(session) or stronger— without requiring R(δ) to enforce it. Cross-session rb constraints do require R(δ) (Mapping 3). The session-order and cross-session cases separate cleanly: so is handled by C(deps), and cross-session rb is handled by R(δ).
Mapping 2: ar → O(π). Burckhardt’s ar is an arbitration order—a total order on events that resolves conflicts. LCC’s O(π) determines how forks in the DAG are resolved into a deterministic sequence. Burckhardt ar axiom
LCC O(π)
ar absent (no arbitration) ar per-key total order ar global total order
O(trivial) O(πkey ) O(πall )
The translation is direct: ar restricted to equivalence class k ↔ O(π) where π maps events to k. A Burckhardt predicate requiring “ar is a total order” maps to O(πall ). A predicate requiring “ar per object” maps to O(πkey ). Absence of ar maps to O(trivial). Detail: Burckhardt does not have an equivalent of O(πobserver ), where each observer independently resolves forks. This is one dimension where LCC is strictly more expressive.
Mapping 3: rb → R(δ) + C(deps). This is the non-trivial mapping. Burckhardt’s rb is a real-time ordering. LCC has no explicit real-time ordering relation. Instead, rb emerges from the interaction of R(δ) and C(deps) with the DAG structure. Claim: rb ⊆ vis is equivalent to: for all observers n, if message m1 was delivered to all observers by time t, and message m2 was created after time t, then m1 ∈ deps(m2 ).
20
Light Cone Consistency: Toward a Unified Theory of Consistency in Message-Passing Systems
Proof. Let e1 and e2 be events with e1 rb e2 . Then e1 completes at time t1 and e2 begins at time t2 > t1 . In LCC, e1 corresponds to a message m1 created at time t1 . R(δ) guarantees m1 is delivered to all correct observers by time t1 + δ. Case 1: t2 − t1 > δ. By R(δ), m1 has been delivered to e2 ’s creator before e2 begins. By Definition 5, m2 causally depends on m1 : (m1 , m2 ) ∈ E. By C(deps), any observer who sees m2 must also see m1 . Therefore m1 vis m2 . Case 2: t2 − t1 ≤ δ. R(δ) does not guarantee m1 has been delivered to e2 ’s creator. The events are within the δ window. rb holds, but the DAG may not contain the edge (m1 , m2 ). The LCC configuration with R(δ) does not enforce rb ⊆ vis for these pairs. ◀ ◀ This is not a gap in completeness. It is the precise mechanism by which different R(δ) values capture different consistency models: R(δ)
rb → vis behavior
R(0) R(δ) R(∞) R(absent)
All rb pairs produce causal edges. rb ⊆ vis always. Linearizability. Only rb pairs separated by > δ produce edges. Bounded staleness. No guaranteed delivery time. rb ⊆ vis not enforceable. Eventual. rb ⊆ vis not expressible. No delivery guarantee.
Scoped rb. Some Burckhardt predicates enforce rb ⊆ vis for a subset of event pairs without requiring it universally. These are captured by the interaction of C(deps) with Definitions 4 and 5: same-session rb ⊆ vis holds automatically under C(session) at any R; same-key rb requires C(key) combined with R(δ); cross-scope rb requires R(δ) small enough. The key insight: rb is not a separate parameter. It is an emergent property of R(δ) interacting with C(deps) and the causal structure of the DAG. Converse: Any LCC configuration with R(δ) induces an rb relation on the abstract execution: e1 rb e2 whenever the real-time gap between e1 ’s completion and e2 ’s start exceeds δ. This rb satisfies Burckhardt’s axioms.
Mapping 4: RVAL → F . Burckhardt RVAL
LCC F
RVAL returns last write in ar RVAL returns any concurrent write RVAL returns deterministic merge RVAL returns set of concurrent values RVAL unconstrained
Flatest Fany-concurrent Fcomputed Fmulti Fanything
RVAL and F operate on the same inputs (visible operations and an ordering) and produce the same output (a return value). The mapping is direct.
A.3
Completeness Proof
▶ Theorem 38 (Theorem 14, restated). For every consistency predicate P expressible as a conjunction of standard axioms over Burckhardt abstract executions, there exists an LCC configuration σ = F (C, O, R) such that A |= P implies A |= σ. The mapping is surjective: every such P maps to some σ. It is not injective: distinct predicates may map to the same σ.
Landers & Kramer
Proof. Every Burckhardt predicate P is a conjunction of axioms over (vis, ar, rb, RVAL). By Mappings 1–4, each axiom maps to a parameter choice. The conjunction of axioms maps to the conjunction of parameter choices—an LCC configuration σ. For the forward direction: if A |= P , then the vis, ar, rb, RVAL constraints hold. By the mappings, the corresponding C, O, R, F constraints hold. Therefore A |= σ. For standard Burckhardt predicates, the mapping preserves constraint strength. For fine-grained compositions involving scoped rb constraints, some distinctions may be absorbed into the (C, R) interaction. The mapping is surjective but not injective. LCC is strictly more expressive (Corollary). ◀ ◀
▶ Corollary 39 (Strict Expressiveness). LCC is strictly more expressive than Burckhardt’s framework. LCC includes configurations with no Burckhardt equivalent: 1. R(absent): no delivery guarantee. Burckhardt assumes events produce return values, implying liveness. R(absent) models systems with no liveness guarantee (UDP, fire-andforget). 2. O(πobserver ): per-observer fork resolution. Burckhardt’s ar is global—all events share one arbitration order. 3. Continuous R(δ): Burckhardt’s rb is binary. R(δ) parameterizes the delivery bound continuously, inducing a family of rb relations indexed by δ.
B
Configuration Space Enumeration
We enumerate the LCC configuration space and map each configuration to named consistency models from Viotti and Vukolić [29] and other sources. Vendor and product names in the “Example” columns reflect the consistency level the system is marketed as providing or that we judge most representative of its documented behavior; they are illustrative anchors rather than verified academic measurements, and a system’s actual behavior under contention or failure may differ.
B.1
Parameter Ranges
The configuration space is the Cartesian product of: C: {none, semantic, key, session, explicit} O: {trivial, πkey , πsession , πobserver , all} R: {absent, δ, ∞, 0} This produces 5 × 5 × 4 = 100 theoretical combinations. Of these, 20 are degenerate: under R(0), every message is instantly visible, so the DAG is a chain and O is vacuously satisfied for all scopes—the five O choices collapse to one, removing four redundant variants per C value. This yields 5 × 5 × 3 + 5 × 1 × 1 = 80 distinct configurations. Several additional configurations arise from finer deps filters (e.g., deps semantic ) that are not in the standard five C levels. We include five representative semantic-closure configurations, bringing the total to 85.
21
22
Light Cone Consistency: Toward a Unified Theory of Consistency in Message-Passing Systems
C = none (no causal closure)
B.2
#
O
R
Name
V&V Model
Example
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
trivial trivial trivial πkey πkey πkey πsession πsession πsession πobserver πobserver πobserver all all all all
absent ∞ δ absent ∞ δ absent ∞ δ absent ∞ δ absent ∞ δ 0
No guarantees Eventual delivery Bounded eventual Per-key unread log Per-key ordered Bounded per-key order Per-session unread log Per-session ordered Bounded session order Per-observer unread log Per-observer ordered Bounded observer order Global unread log Total order broadcast Bounded total order Instant total order
— Eventual consistency — — FIFO consistency — — PRAM (partial) — — — — — TOB — —
UDP, unreliable mail Dynamo anti-entropy QoS networks, MPLS WAL before recovery Kafka per-partition Cosmos DB bounded — TCP per-connection SQS FIFO with SLA — — — Raft log before apply Redis replication MySQL semi-sync Network switch
C = key (per-key causal closure)
B.3
#
O
R
Name
V&V Model
Example
17 18 19 20 21 22 23 24 25 26 27 28
trivial trivial trivial πkey πkey πkey πsession πobserver all all all all
absent ∞ δ absent ∞ δ ∞ ∞ absent ∞ δ 0
Per-key snapshot Per-key causal Bounded per-key causal Per-key ordered snapshot Per-key sequential Bounded per-key sequential Per-key session causal Per-key observer order Global per-key unread log Per-key globally ordered Bounded per-key global Per-key linearizability
— Per-key causal — — Per-key sequential — — — — Writes follow reads — Per-key linearizable
— DynamoDB causal — — Cassandra per-key — — — — Single-leader-per-shard — DynamoDB strong, LWT
Landers & Kramer
23
C = session (per-session causal closure)
B.4
#
O
R
Name
V&V Model
Example
29 30 31 32 33 34 35 36 37 38
trivial trivial trivial πkey πsession πobserver all all all all
absent ∞ δ ∞ ∞ ∞ absent ∞ δ 0
Session snapshot Session causal Bounded session causal Session per-key causal Session ordered Session observer order Global session unread log Session sequential Bounded session sequential Session linearizability
— PRAM / RYW — Monotonic writes Monotonic reads — — — — —
Frozen session Monotonic R+W — — MongoDB causal sessions — — — — —
C = explicit (full causal closure)
B.5
#
O
R
Name
V&V Model
Example
39 40 41 42 43 44 45 46 47 48 49 50 51 52
trivial trivial trivial πkey πkey πkey πsession πobserver πobserver πobserver all all all all
absent ∞ δ absent ∞ δ ∞ absent ∞ δ absent ∞ δ 0
Consistent snapshot Causal consistency Bounded causal Per-key causal snapshot Causal per-key order Bounded causal per-key Causal session order Causal observer snapshot Causal observer order Bounded causal observer Global causal unread log Sequential consistency Bounded sequential Linearizability
— Causal consistency Bounded causal — Causal+ — — — — Real-time causal — Sequential Linearizable (bounded) Linearizability
Point-in-time backup COPS, Eiger Geo-distributed causal — — CockroachDB — — Swytch (fork-choice) Special relativity at R(d/c) Finalized blockchain ZooKeeper, etcd Spanner (TrueTime) Single-node, mutex
B.6
Viotti & Vukolić Coverage
The following table maps named models from [29] to LCC configurations. Models marked ✓ map directly. Models marked △ map with caveats (scope limitations, F dependence, or Byzantine assumptions outside LCC’s model).
24
Light Cone Consistency: Toward a Unified Theory of Consistency in Message-Passing Systems
V&V Model
Config #
Notes
Eventual consistency Strong eventual consistency FIFO / PRAM consistency Causal consistency Causal+ consistency Per-key sequential Per-key linearizability Sequential consistency Linearizability Total order broadcast Monotonic reads Monotonic writes Read your writes Writes follow reads Regular register Safe register Atomic register Bounded staleness Consistent prefix Processor consistency Slow memory Fork-linearizability Fork-sequential Fork-join causal PBS (probabilistic) Weak consistency Release consistency
2 2 8, 30 40 43 21 28 50 52 14 33 32 30 26 2 2 52 3, 6 13 30 30 △ △ △ △ 1 △
✓ ✓ (F = Fcomputed ) ✓ (depends on C scope) ✓ ✓ (F = Fcomputed ) ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ F = Fany-concurrent F = Fanything ✓ ✓ (depends on O scope) ✓ (C = none, O = all) ✓ ✓ Per-branch (C, O, R) after fork Per-branch (C, O, R) after fork Per-branch (C, O, R) after fork R(δ) with probabilistic bound ✓ Requires synchronization actions
Fork-based models are expressible as standard (C, O, R) configurations applied per-branch after a fork in the DAG (see Remark on Byzantine Faults, Section 5.5). Probabilistic models (PBS) are expressible with R(δ) interpreted as a probabilistic delivery bound, extending Definition 9 to probabilistic guarantees. Release/acquire models require distinguishing synchronization operations from data operations, which LCC’s point-event model does not natively express.
B.7
Unnamed Configurations
Of the 85 configurations, approximately 26 have no established name in the literature. These unnamed points predict consistency levels that could exist but have not been built or studied. Representative examples: #10 (none, πobserver , absent): per-observer ordering with no closure and no delivery guarantee. No known system operates here. #46 (explicit, πobserver , absent): full causal closure with per-observer fork resolution and no delivery guarantee. A frozen causal snapshot with independent interpretation. #42 (explicit, πkey , absent): causally closed per-key snapshot with no delivery guarantee. A consistent backup that orders keys but never delivers.
Landers & Kramer
The existence of unnamed configurations is a feature of the framework, not a gap. It suggests that the consistency design space is larger than the currently explored region.
25