Causal Ordering — Ordering and Causality in… | OneNoughtOne

0/105

System DesignOrdering and Causality

Ordering and Causality in Distributed Systems

LevelAdvanced

Duration75 mins

TopicOrdering and Causality

3 / 5

Causal Ordering

Ordering That Respects Cause and Effect

Imagine a chat application where Alice posts: "Should we meet at 6 PM?" and Bob replies: "Sure, see you then!" If the system shows Bob's reply before Alice's question, users are confused. If Alice posts "Yes, 6 PM works!" as a follow-up to Bob's confirmation, the entire conversation becomes incomprehensible if messages appear out of order. This is the problem causal ordering solves. It's a consistency guarantee that ensures events are seen in an order that respects their causal relationships—if event A could have influenced event B, then all observers see A before B. Causal ordering occupies a sweet spot in the consistency spectrum: it's strong enough to provide intuitive semantics for many applications, yet weak enough to allow significant concurrency and good performance.

What You Will Learn

By the end of this page, you will understand what causal ordering guarantees, how it differs from other consistency models, how it's implemented using mechanisms like vector clocks, and when to choose causal ordering for your distributed system. You'll see concrete examples of causal violations and how proper systems prevent them.

What Is Causal Ordering?

Causal ordering (also called causal consistency or causal broadcast) is a property of distributed systems that guarantees: if event A happens-before event B, then all processes observe A before observing B. Formally: For all events A, B: if A \to B, then all processes that see B have already seen A. For concurrent events (A || B): different processes may see them in different orders. This definition directly builds on the happens-before relationship. Causal ordering preserves all happens-before relationships while remaining silent about the relative ordering of concurrent events.

Causal Ordering Guarantees

•If A → B, everyone sees A before B
•Read your writes: you see your own updates immediately
•Monotonic reads: once you've seen X, you won't see pre-X states
•Writes follow reads: your writes reflect what you've read
•Transitive visibility: if you see B and B → A, you've seen A

What's NOT Guaranteed

•Total order of all events (concurrent events may differ)
•Real-time ordering (wall-clock sequence not enforced)
•Same view across all processes (concurrent events vary)
•Immediate visibility (updates may be delayed)
•Preventing conflicts (concurrent writes can still conflict)

The Core Intuition

Causal ordering ensures you never see the effect without the cause. If Bob's reply was influenced by Alice's question, you'll see Alice's question before Bob's reply. But if Alice and Carol post simultaneously with no influence on each other, different users might see Alice first or Carol first—and that's acceptable.

Understanding Causal Violations

Before understanding how to implement causal ordering, let's see what happens when it's violated. Causal violations occur when a system delivers an effect before its cause. Example 1: Chat Message Ordering

causal-violation-chat.pseudo

Scenario

// Timeline of chat messages:
// User Alice posts a question
// User Bob sees Alice's question and posts a reply
 
Alice (Server A): post("Should we meet at 6 PM?")  // Event A1
 
// Message A1 propagates to Bob's view (Server B)
Bob reads Alice's message                          // Event B1
Bob (Server B): post("Sure, 6 PM sounds great!")   // Event B2
 
// Causal relationships:
// A1 → B1 → B2 (Bob's reply depends on seeing Alice's message)
 
// CAUSAL VIOLATION scenario:
// What Carol might see (Server C) with naive replication:
 
Carol's view:
Time 1: [empty chat]
Time 2: "Sure, 6 PM sounds great!" (from Bob)  // B2 arrives first!
Time 3: "Should we meet at 6 PM?" (from Alice) // A1 arrives late
 
// Result: Carol sees Bob's answer before Alice's question
// This is confusing and violates conversational logic

Example 2: Distributed Key-Value Store

causal-violation-kvstore.pseudo

Scenario

// User flow: set config, then start service that uses config
 
Admin:
    write(config, "production_settings")       // Event W1
    read(config)  → returns "production_settings"
    write(service_started, true)               // Event W2 (depends on W1)
 
// Causal relationship: W1 → W2
// Admin only started service AFTER confirming config was set
 
// CAUSAL VIOLATION scenario:
// Worker node might see:
 
Worker node reads:
    read(service_started) → returns true       // Sees W2
    read(config) → returns null                // Hasn't received W1!
    
// Result: Worker tries to run service with no configuration
// System fails because it saw the effect (service_started) 
// before the cause (config write)

Why Causal Violations Are Dangerous

Causal violations break application logic in subtle ways. The system technically 'works'—no errors are thrown—but semantics are wrong. Users see nonsensical data, application invariants are violated, and debugging is extremely difficult because the problem is timing-dependent and may not reproduce.

Implementing Causal Ordering

To implement causal ordering, we need mechanisms to: Track causality — Determine which events happen-before which Propagate metadata — Send causal information with messages Delay delivery — Hold back messages until causal predecessors are delivered The primary tool for tracking causality is vector clocks . Let's understand how they work: Vector Clock Basics: Each process maintains a vector of counters, one for each process in the system. When process i has vector V: V[i] represents i's own logical time (how many events i has executed) V[j] represents the latest event from process j that i knows about The rules for updating vector clocks: On local event: Increment V[i] On send: Increment V[i], send V with the message On receive: V = max(V, V_received) componentwise, then increment V[i]

vector-clock-example.pseudo

Pseudocode

// Three processes: P0, P1, P2
// Vector clocks shown as [v0, v1, v2]
 
P0                      P1                      P2
VC = [0,0,0]           VC = [0,0,0]           VC = [0,0,0]
    │                      │                      │
    ● Event A              │                      │
    VC = [1,0,0]           │                      │
    │                      │                      │
    │───── msg ──────────►●│ Event B              │
    │                      │ Recv: max([1,0,0], [0,0,0]) + [0,1,0]
    │                      VC = [1,1,0]           │
    │                      │                      │
    │                      │───── msg ──────────►●│ Event C
    │                      │                      │ VC = [1,1,1]
    │                      │                      │
    ● Event D              │                      │
    VC = [2,0,0]           │                      │
    │                      │                      │
 
// Comparing events:
// A → B because [1,0,0] < [1,1,0] (A's VC ≤ B's, and not equal)
// B → C because [1,1,0] < [1,1,1]
// A → C by transitivity
// A || D? NO! A → D because same process (P0)
// D || B and D || C (neither ≤ the other)

Comparison Rules for Vector Clocks: Given vectors V and W: V \leq W iff \foralli: V[i] \leq W[i] (every component of V is \leq corresponding component of W) V < W iff V \leq W and V \neq W (V happens-before W) V || W iff \neg(V \leq W) and \neg(W \leq V) (concurrent) This gives us a way to compare any two events: attach vector clocks to events, and the comparison tells us the happens-before relationship.

Causal Delivery Protocol

Tracking causality is only half the problem. We also need to deliver messages in causal order. This means sometimes holding back a message until its causal predecessors have been delivered. The Causal Delivery Condition: A message m with vector clock V can be delivered to process i only when: V[sender] = delivered[sender] + 1 (this is the next expected message from sender) \forallj \neq sender: V[j] \leq delivered[j] (all messages sender saw, we've already seen) If either condition fails, the message is buffered until its prerequisites arrive.

causal-delivery.pseudo

Pseudocode

class CausalDeliveryManager:
    // Track what we've delivered from each process
    delivered: Map<ProcessId, int> = all zeros
    
    // Buffer for messages waiting on dependencies
    pending: List<Message> = []
    
    def on_receive(message, sender_vector_clock):
        pending.add((message, sender_vector_clock, sender_id))
        try_deliver_pending()
    
    def try_deliver_pending():
        made_progress = true
        
        while made_progress:
            made_progress = false
            
            for (msg, vc, sender) in pending:
                if can_deliver(vc, sender):
                    deliver_to_application(msg)
                    delivered[sender] += 1
                    pending.remove((msg, vc, sender))
                    made_progress = true
                    break  // Restart scan after state change
    
    def can_deliver(vc, sender):
        // Condition 1: This is the next message from sender
        if vc[sender] != delivered[sender] + 1:
            return false
        
        // Condition 2: We've seen everything sender had seen
        for pid in all_processes:
            if pid != sender and vc[pid] > delivered[pid]:
                return false
        
        return true
 
// EXAMPLE TRACE:
// Process P2 has delivered = [0, 0, 0]
// Receives message from P1 with VC = [1, 1, 0]
//
// Check: vc[P1] = 1, delivered[P1] + 1 = 1 ✓
// Check: vc[P0] = 1 > delivered[P0] = 0 ✗ WAIT!
//
// Message is buffered until we receive the [1, 0, 0] message from P0

The Cost of Buffering

Causal delivery can introduce latency—messages may wait in buffers for their causal predecessors. In extreme cases, a lost message can block all subsequent deliveries indefinitely. Production systems need timeouts, retries, and mechanisms to handle missing messages gracefully.

Causal Consistency in Distributed Databases

Modern distributed databases increasingly offer causal consistency as a consistency level. This provides stronger guarantees than eventual consistency while maintaining better availability than linearizability. How Databases Implement Causal Consistency: 1. Client Sessions and Dependency Tracking The database tracks which writes a client has observed (read) or performed. When the client makes a subsequent write, the database ensures all dependencies are visible at the target replica before applying the write. 2. Causal Tokens/Stamps Clients carry a 'causal token' that encapsulates their causal past. This token is passed with each operation, allowing the database to understand dependencies without full vector clocks. 3. Hybrid Logical Clocks (HLC) Some systems use HLCs that combine physical timestamps with logical counters. This bounds timestamp growth while still capturing causality.

Causal Consistency in Production Databases
Database	Feature Name	Implementation Approach	Notes
MongoDB	Causal Consistency	Logical session IDs + cluster time	Available since 3.6
CockroachDB	Serializable (achieves causal)	Hybrid logical clocks	Stronger than causal
Cassandra	LWT + careful design	Paxos for LWT, manual design for causal	Not automatic
Cosmos DB	Session consistency	Session tokens	Default consistency level
Spanner	External consistency	TrueTime with bounded error	Stronger than causal

Session Consistency

Many databases offer 'session consistency' as a practical approximation of causal consistency. Within a session, you always read your own writes and see monotonically increasing states. This covers the most common causal requirements while being easier to implement than full causal consistency across all clients.

Causal Ordering vs Other Consistency Models

Understanding where causal ordering sits in the consistency hierarchy helps you choose the right model for your application:

Consistency Model Comparison
Property	Eventual	Causal	Sequential	Linearizable
Concurrent events ordered	No	No	Yes (some order)	Yes (real-time)
Read-your-writes	Eventually	Yes	Yes	Yes
Monotonic reads	No	Yes	Yes	Yes
Writes-follow-reads	No	Yes	Yes	Yes
Global total order	No	No	Yes	Yes (real-time)
Availability under partition	High	High	Limited	Low
Typical latency	Lowest	Low	Medium	Highest

Key insight: Causal consistency is the strongest consistency model achievable in an always-available system. This remarkable result, proven by Mahajan et al., means: Stronger models (sequential, linearizable) require sacrificing availability during partitions Weaker models (eventual) lose important semantic guarantees Causal sits exactly at the boundary—you get maximum consistency while keeping maximum availability This makes causal consistency a Goldilocks choice for many distributed applications.

When to Choose Causal Consistency

•Collaborative applications — Documents, chat, shared state where user actions often depend on what they've observed
•Social networks — Posts, comments, reactions where causal relationships are visible to users
•Multi-region deployments — When you need to avoid cross-region synchronization for every operation
•Mobile/offline-first apps — Where local operations should reflect the user's causal past
•Microservices — When services must see consistent views of related data

Practical Implementation Considerations

Implementing causal ordering in production systems involves several practical challenges beyond the theoretical foundations: 1. Vector Clock Scalability Vector clocks grow with the number of processes. For systems with thousands of nodes, this becomes prohibitive. Solutions include: Dependency tracking — Track only recent dependencies, not full history Plausible clocks — Bounded-size approximations that may rarely violate causality Hierarchical schemes — Group processes to reduce dimensionality 2. Garbage Collection How do you know when old causal metadata can be discarded? You need to know that all processes have progressed past a certain point—requiring coordination. 3. Client Mobility When a client moves between servers (load balancing, failover), it must carry its causal context. Lost context can cause causal violations. 4. Partial Replication In sharded systems, not every replica has all data. Tracking causality across shards requires careful design—you might need to track which shards a transaction touched.

causal-context-client.pseudo

Pseudocode

// Client-side causal context management
 
class CausalClient:
    server: ServerConnection
    causal_context: CausalToken = empty_token()
    
    def read(key):
        // Send context to server so it waits for dependencies
        response = server.read(
            key=key,
            after=self.causal_context
        )
        
        // Update context using server's returned token
        self.causal_context = merge(
            self.causal_context,
            response.causal_token
        )
        
        return response.value
    
    def write(key, value):
        // Write depends on everything we've read
        response = server.write(
            key=key,
            value=value,
            depends_on=self.causal_context
        )
        
        // Update our context to include this write
        self.causal_context = response.causal_token
    
    def on_server_change(new_server):
        // When switching servers, carry context along
        new_server.establish_session(self.causal_context)
        server = new_server
        
// CRITICAL: If causal_context is lost (crash, timeout),
// client may see causal anomalies until context rebuilds

Production Reality

Most production systems don't implement 'pure' causal consistency. They use pragmatic approximations: session-scoped causal guarantees, bounded staleness, or causal consistency only within specific scopes (user, tenant, partition). These trade theoretical purity for practical efficiency.

System DesignOrdering and Causality

Ordering and Causality in Distributed Systems

LevelAdvanced

Duration75 mins

TopicOrdering and Causality

3 / 5

Causal Ordering

Ordering That Respects Cause and Effect

Imagine a chat application where Alice posts: "Should we meet at 6 PM?" and Bob replies: "Sure, see you then!" If the system shows Bob's reply before Alice's question, users are confused. If Alice posts "Yes, 6 PM works!" as a follow-up to Bob's confirmation, the entire conversation becomes incomprehensible if messages appear out of order. This is the problem causal ordering solves. It's a consistency guarantee that ensures events are seen in an order that respects their causal relationships—if event A could have influenced event B, then all observers see A before B. Causal ordering occupies a sweet spot in the consistency spectrum: it's strong enough to provide intuitive semantics for many applications, yet weak enough to allow significant concurrency and good performance.

What You Will Learn

By the end of this page, you will understand what causal ordering guarantees, how it differs from other consistency models, how it's implemented using mechanisms like vector clocks, and when to choose causal ordering for your distributed system. You'll see concrete examples of causal violations and how proper systems prevent them.

What Is Causal Ordering?

Causal ordering (also called causal consistency or causal broadcast) is a property of distributed systems that guarantees: if event A happens-before event B, then all processes observe A before observing B. Formally: For all events A, B: if A \to B, then all processes that see B have already seen A. For concurrent events (A || B): different processes may see them in different orders. This definition directly builds on the happens-before relationship. Causal ordering preserves all happens-before relationships while remaining silent about the relative ordering of concurrent events.

Causal Ordering Guarantees

•If A → B, everyone sees A before B
•Read your writes: you see your own updates immediately
•Monotonic reads: once you've seen X, you won't see pre-X states
•Writes follow reads: your writes reflect what you've read
•Transitive visibility: if you see B and B → A, you've seen A

What's NOT Guaranteed

•Total order of all events (concurrent events may differ)
•Real-time ordering (wall-clock sequence not enforced)
•Same view across all processes (concurrent events vary)
•Immediate visibility (updates may be delayed)
•Preventing conflicts (concurrent writes can still conflict)

The Core Intuition

Causal ordering ensures you never see the effect without the cause. If Bob's reply was influenced by Alice's question, you'll see Alice's question before Bob's reply. But if Alice and Carol post simultaneously with no influence on each other, different users might see Alice first or Carol first—and that's acceptable.

Understanding Causal Violations

Before understanding how to implement causal ordering, let's see what happens when it's violated. Causal violations occur when a system delivers an effect before its cause. Example 1: Chat Message Ordering

causal-violation-chat.pseudo

Scenario

// Timeline of chat messages:
// User Alice posts a question
// User Bob sees Alice's question and posts a reply
 
Alice (Server A): post("Should we meet at 6 PM?")  // Event A1
 
// Message A1 propagates to Bob's view (Server B)
Bob reads Alice's message                          // Event B1
Bob (Server B): post("Sure, 6 PM sounds great!")   // Event B2
 
// Causal relationships:
// A1 → B1 → B2 (Bob's reply depends on seeing Alice's message)
 
// CAUSAL VIOLATION scenario:
// What Carol might see (Server C) with naive replication:
 
Carol's view:
Time 1: [empty chat]
Time 2: "Sure, 6 PM sounds great!" (from Bob)  // B2 arrives first!
Time 3: "Should we meet at 6 PM?" (from Alice) // A1 arrives late
 
// Result: Carol sees Bob's answer before Alice's question
// This is confusing and violates conversational logic

Example 2: Distributed Key-Value Store

causal-violation-kvstore.pseudo

Scenario

// User flow: set config, then start service that uses config
 
Admin:
    write(config, "production_settings")       // Event W1
    read(config)  → returns "production_settings"
    write(service_started, true)               // Event W2 (depends on W1)
 
// Causal relationship: W1 → W2
// Admin only started service AFTER confirming config was set
 
// CAUSAL VIOLATION scenario:
// Worker node might see:
 
Worker node reads:
    read(service_started) → returns true       // Sees W2
    read(config) → returns null                // Hasn't received W1!
    
// Result: Worker tries to run service with no configuration
// System fails because it saw the effect (service_started) 
// before the cause (config write)

Why Causal Violations Are Dangerous

Causal violations break application logic in subtle ways. The system technically 'works'—no errors are thrown—but semantics are wrong. Users see nonsensical data, application invariants are violated, and debugging is extremely difficult because the problem is timing-dependent and may not reproduce.

Implementing Causal Ordering

To implement causal ordering, we need mechanisms to: Track causality — Determine which events happen-before which Propagate metadata — Send causal information with messages Delay delivery — Hold back messages until causal predecessors are delivered The primary tool for tracking causality is vector clocks . Let's understand how they work: Vector Clock Basics: Each process maintains a vector of counters, one for each process in the system. When process i has vector V: V[i] represents i's own logical time (how many events i has executed) V[j] represents the latest event from process j that i knows about The rules for updating vector clocks: On local event: Increment V[i] On send: Increment V[i], send V with the message On receive: V = max(V, V_received) componentwise, then increment V[i]

vector-clock-example.pseudo

Pseudocode

// Three processes: P0, P1, P2
// Vector clocks shown as [v0, v1, v2]
 
P0                      P1                      P2
VC = [0,0,0]           VC = [0,0,0]           VC = [0,0,0]
    │                      │                      │
    ● Event A              │                      │
    VC = [1,0,0]           │                      │
    │                      │                      │
    │───── msg ──────────►●│ Event B              │
    │                      │ Recv: max([1,0,0], [0,0,0]) + [0,1,0]
    │                      VC = [1,1,0]           │
    │                      │                      │
    │                      │───── msg ──────────►●│ Event C
    │                      │                      │ VC = [1,1,1]
    │                      │                      │
    ● Event D              │                      │
    VC = [2,0,0]           │                      │
    │                      │                      │
 
// Comparing events:
// A → B because [1,0,0] < [1,1,0] (A's VC ≤ B's, and not equal)
// B → C because [1,1,0] < [1,1,1]
// A → C by transitivity
// A || D? NO! A → D because same process (P0)
// D || B and D || C (neither ≤ the other)

Comparison Rules for Vector Clocks: Given vectors V and W: V \leq W iff \foralli: V[i] \leq W[i] (every component of V is \leq corresponding component of W) V < W iff V \leq W and V \neq W (V happens-before W) V || W iff \neg(V \leq W) and \neg(W \leq V) (concurrent) This gives us a way to compare any two events: attach vector clocks to events, and the comparison tells us the happens-before relationship.

Causal Delivery Protocol

Tracking causality is only half the problem. We also need to deliver messages in causal order. This means sometimes holding back a message until its causal predecessors have been delivered. The Causal Delivery Condition: A message m with vector clock V can be delivered to process i only when: V[sender] = delivered[sender] + 1 (this is the next expected message from sender) \forallj \neq sender: V[j] \leq delivered[j] (all messages sender saw, we've already seen) If either condition fails, the message is buffered until its prerequisites arrive.

causal-delivery.pseudo

Pseudocode

class CausalDeliveryManager:
    // Track what we've delivered from each process
    delivered: Map<ProcessId, int> = all zeros
    
    // Buffer for messages waiting on dependencies
    pending: List<Message> = []
    
    def on_receive(message, sender_vector_clock):
        pending.add((message, sender_vector_clock, sender_id))
        try_deliver_pending()
    
    def try_deliver_pending():
        made_progress = true
        
        while made_progress:
            made_progress = false
            
            for (msg, vc, sender) in pending:
                if can_deliver(vc, sender):
                    deliver_to_application(msg)
                    delivered[sender] += 1
                    pending.remove((msg, vc, sender))
                    made_progress = true
                    break  // Restart scan after state change
    
    def can_deliver(vc, sender):
        // Condition 1: This is the next message from sender
        if vc[sender] != delivered[sender] + 1:
            return false
        
        // Condition 2: We've seen everything sender had seen
        for pid in all_processes:
            if pid != sender and vc[pid] > delivered[pid]:
                return false
        
        return true
 
// EXAMPLE TRACE:
// Process P2 has delivered = [0, 0, 0]
// Receives message from P1 with VC = [1, 1, 0]
//
// Check: vc[P1] = 1, delivered[P1] + 1 = 1 ✓
// Check: vc[P0] = 1 > delivered[P0] = 0 ✗ WAIT!
//
// Message is buffered until we receive the [1, 0, 0] message from P0

The Cost of Buffering

Causal delivery can introduce latency—messages may wait in buffers for their causal predecessors. In extreme cases, a lost message can block all subsequent deliveries indefinitely. Production systems need timeouts, retries, and mechanisms to handle missing messages gracefully.

Causal Consistency in Distributed Databases

Modern distributed databases increasingly offer causal consistency as a consistency level. This provides stronger guarantees than eventual consistency while maintaining better availability than linearizability. How Databases Implement Causal Consistency: 1. Client Sessions and Dependency Tracking The database tracks which writes a client has observed (read) or performed. When the client makes a subsequent write, the database ensures all dependencies are visible at the target replica before applying the write. 2. Causal Tokens/Stamps Clients carry a 'causal token' that encapsulates their causal past. This token is passed with each operation, allowing the database to understand dependencies without full vector clocks. 3. Hybrid Logical Clocks (HLC) Some systems use HLCs that combine physical timestamps with logical counters. This bounds timestamp growth while still capturing causality.

Causal Consistency in Production Databases
Database	Feature Name	Implementation Approach	Notes
MongoDB	Causal Consistency	Logical session IDs + cluster time	Available since 3.6
CockroachDB	Serializable (achieves causal)	Hybrid logical clocks	Stronger than causal
Cassandra	LWT + careful design	Paxos for LWT, manual design for causal	Not automatic
Cosmos DB	Session consistency	Session tokens	Default consistency level
Spanner	External consistency	TrueTime with bounded error	Stronger than causal

Session Consistency

Many databases offer 'session consistency' as a practical approximation of causal consistency. Within a session, you always read your own writes and see monotonically increasing states. This covers the most common causal requirements while being easier to implement than full causal consistency across all clients.

Causal Ordering vs Other Consistency Models

Understanding where causal ordering sits in the consistency hierarchy helps you choose the right model for your application:

Consistency Model Comparison
Property	Eventual	Causal	Sequential	Linearizable
Concurrent events ordered	No	No	Yes (some order)	Yes (real-time)
Read-your-writes	Eventually	Yes	Yes	Yes
Monotonic reads	No	Yes	Yes	Yes
Writes-follow-reads	No	Yes	Yes	Yes
Global total order	No	No	Yes	Yes (real-time)
Availability under partition	High	High	Limited	Low
Typical latency	Lowest	Low	Medium	Highest

Key insight: Causal consistency is the strongest consistency model achievable in an always-available system. This remarkable result, proven by Mahajan et al., means: Stronger models (sequential, linearizable) require sacrificing availability during partitions Weaker models (eventual) lose important semantic guarantees Causal sits exactly at the boundary—you get maximum consistency while keeping maximum availability This makes causal consistency a Goldilocks choice for many distributed applications.

When to Choose Causal Consistency

•Collaborative applications — Documents, chat, shared state where user actions often depend on what they've observed
•Social networks — Posts, comments, reactions where causal relationships are visible to users
•Multi-region deployments — When you need to avoid cross-region synchronization for every operation
•Mobile/offline-first apps — Where local operations should reflect the user's causal past
•Microservices — When services must see consistent views of related data

Practical Implementation Considerations

Implementing causal ordering in production systems involves several practical challenges beyond the theoretical foundations: 1. Vector Clock Scalability Vector clocks grow with the number of processes. For systems with thousands of nodes, this becomes prohibitive. Solutions include: Dependency tracking — Track only recent dependencies, not full history Plausible clocks — Bounded-size approximations that may rarely violate causality Hierarchical schemes — Group processes to reduce dimensionality 2. Garbage Collection How do you know when old causal metadata can be discarded? You need to know that all processes have progressed past a certain point—requiring coordination. 3. Client Mobility When a client moves between servers (load balancing, failover), it must carry its causal context. Lost context can cause causal violations. 4. Partial Replication In sharded systems, not every replica has all data. Tracking causality across shards requires careful design—you might need to track which shards a transaction touched.

causal-context-client.pseudo

Pseudocode

// Client-side causal context management
 
class CausalClient:
    server: ServerConnection
    causal_context: CausalToken = empty_token()
    
    def read(key):
        // Send context to server so it waits for dependencies
        response = server.read(
            key=key,
            after=self.causal_context
        )
        
        // Update context using server's returned token
        self.causal_context = merge(
            self.causal_context,
            response.causal_token
        )
        
        return response.value
    
    def write(key, value):
        // Write depends on everything we've read
        response = server.write(
            key=key,
            value=value,
            depends_on=self.causal_context
        )
        
        // Update our context to include this write
        self.causal_context = response.causal_token
    
    def on_server_change(new_server):
        // When switching servers, carry context along
        new_server.establish_session(self.causal_context)
        server = new_server
        
// CRITICAL: If causal_context is lost (crash, timeout),
// client may see causal anomalies until context rebuilds

Production Reality

Most production systems don't implement 'pure' causal consistency. They use pragmatic approximations: session-scoped causal guarantees, bounded staleness, or causal consistency only within specific scopes (user, tenant, partition). These trade theoretical purity for practical efficiency.

Causal Ordering

Ordering That Respects Cause and Effect

What Is Causal Ordering?

Understanding Causal Violations

Implementing Causal Ordering

Causal Delivery Protocol

Causal Consistency in Distributed Databases

Causal Ordering vs Other Consistency Models

Practical Implementation Considerations

There’s more to understand.

Causal Ordering

Ordering That Respects Cause and Effect

What Is Causal Ordering?

Understanding Causal Violations

Implementing Causal Ordering

Causal Delivery Protocol

Causal Consistency in Distributed Databases

Causal Ordering vs Other Consistency Models

Practical Implementation Considerations

There’s more to understand.