Causal Consistency

Vector clocks are the canonical data structure for tracking causal dependencies across a set of distributed processes or agents. Each process maintains a vector of logical timestamps, one for every process in the system.

• Mechanism: When a process performs an operation, it increments its own counter in the vector. It attaches the updated vector to the operation. A receiving process can deliver the operation only if it has seen all causally preceding operations, which is verified by comparing vector clocks.
• Detection: By comparing two vectors V1 and V2, a system can determine if the corresponding events are causally related (V1 < V2), concurrent, or causally dependent in the other direction.
• Overhead: The size of the vector scales with the number of processes, which can be a limitation for very large systems.

Causal consistency often provides session guarantees (or client-centric consistency), ensuring a single client observes a causally consistent view of the system across its sequence of operations, even if it communicates with different replicas. This is critical for user-facing applications.

• Read Your Writes: A client will always see the effects of its own previous writes.
• Monotonic Reads: Successive reads by a client will return data that is at least as recent as previous reads.
• Writes Follow Reads: A write is guaranteed to be ordered after the data read by the preceding read operation, preserving causality across read-write boundaries.
• Monotonic Writes: A client's writes are committed in the order they were issued.

Causal consistency occupies a pragmatic middle ground in the consistency-availability spectrum. It prevents confusing causal anomalies while offering higher availability and lower latency than strong consistency models.

• Availability: Writes can typically complete without requiring a global consensus or locking all replicas, as only causal dependencies must be tracked.
• Latency: Read and write operations usually have lower latency compared to linearizable systems, as they don't require immediate global synchronization.
• Use Case Fit: Ideal for collaborative applications (like document editing, social media feeds), multi-agent system state synchronization, and notification systems where causal flow is more important than a single, total order.

Causal consistency is one point in a hierarchy of distributed consistency models, each with different guarantees and costs.

• Stronger than Eventual Consistency: Eventual consistency only guarantees that all replicas will eventually converge if no new writes are made. It permits causal violations.
• Weaker than Sequential Consistency: Sequential consistency requires a total order of all operations that respects each process's program order, which is stricter than causal order.
• Much Weaker than Linearizability: Linearizability (strong consistency) provides the illusion of a single, immediately updated copy of the data, placing every operation on a global timeline.
• Foundation for Causal+ Models: Some systems implement Causal+ consistency, which is causal consistency plus convergence (all replicas see the same set of writes).

The strongest single-object consistency model. It guarantees that each operation appears to take effect atomically at some point between its invocation and completion. This point must be consistent with the real-time ordering of operations across all processes.

• Key Guarantee: Real-time recency. A read will always return the value of the most recent write that completed.
• Comparison to Causal: Linearizability implies causal consistency but is stricter. It enforces real-time constraints, whereas causal consistency only enforces constraints based on program-defined causality, making it more performant.

A data structure used to track causality dependencies between events in a distributed system. Each process maintains a vector of logical timestamps (one counter per process). By comparing vectors, the system can determine if one event happened-before another (causal relationship) or if they are concurrent.

• Primary Use: The foundational mechanism for implementing causal consistency.
• How it Works: When a process performs an operation, it increments its own counter in the vector. It attaches this updated vector to the operation. Recipients merge vectors to understand the causal history.

A family of data structures designed for highly available distributed systems. CRDTs are mathematically proven to converge to the same state across replicas without requiring coordination, even when updates are applied in different orders.

• Key Property: Commutative operations ensure eventual consistency.
• Relationship to Causal: Some CRDTs, like Causal CRDTs, leverage causal consistency to provide stronger semantics than basic eventual consistency. They use mechanisms like vector clocks to ensure causal dependencies are respected, enabling ordered operations like adding an item to a list after it was created.

A fundamental partial ordering of events in a distributed system, defined by Leslie Lamport. Event A happened-before event B (A → B) if:

1. A and B are on the same process and A executed before B (program order).
2. A is the sending of a message and B is the receipt of that message.
3. The relation is transitive (if A → B and B → C, then A → C).

• Core Concept: This relation formally defines causality.
• Foundation for Models: Causal consistency is defined in terms of this relation: it requires that if write₁ → write₂, then all processes must see write₁ before write₂.