10-Consistency Model

What is consistency model?

A consistency model is a contract describing what values clients are allowed to observe when multiple copies of data and concurrent operations exist.

Through a series of various consistency models, they answer questions such as:

• When does a completed write become visible?
• Must every replica observe writes in the same order?
• Can a read return an older value?
• If two writes conflict, must replicas choose the same winner?
• What happens during network partitions?

Consistency is mainly about observable ordering and visibility. Replication, consensus, timestamps, quorums, and conflict resolution are mechanisms used to provide particular consistency models.

Stronger vs Weaker Consistency

Stronger Consistency Models

• • Easier to write correct applications atop of the system
• • Stronger guarantees the system has to provide, leads to performance hit

Weaker Consistency Models

• • Harder to write applications, e.g., concurreny bugs
• • Weaker guarantees the system has to provide, less performance hit

Strictly Stronger Consistency

• A consistency model A is strictly stronger than B if it allows a strict subset of the behaviors of B
  • Guarantees are strictly stronger
  • Prevents a strict superset of the “anomalies” that may happen in B
    • e.g. Eventual Consistency allows an obsolute read after a write is done.
    • e.g. Linearizability doesn’t allow it.

Consistency Hierarchy

Linearzability
Sequential Consistency
Causal+ Consistency
Causal Consistency
Eventual Consistency

Linearizability

Linearizability makes a distributed object behave as if there were exactly one copy of it.

• Operations appear to be executed in some legal total order, as if done by a single threaded machine
• That total order preserves the real-time ordering between operations
  • If operation A completes before operation B begins, then A is ordered before B in real-time
  • If neither A nor B completes before the other begins, then there is no real-time order
    • (But there must be some total order)
  • Concensus protocols ensure all these logs in the replica group behave the same
    • e.g., if my write W1 is committed on replica A, then I read from replica B, I should be able to see my write W1 on replica B -> strongly consistent, linearizable
• Linearizability is the strongest single-operation consistency model
  • Doesn’t guarantee linearizability in multi-cast operations

Suppose two processes running operations concurrently and x is initially 0:

P1 --W1(x+=1)--
P2              --W2(x+=1)-- --R2(x)=2--

W1 is in real-time before W2, thus linearizability requires R2(x) = 2

P1--W1(x+=1)--    --R1(x)=1--
P2             --W2(x+=1)--

W2 and R1 are conccurent. There is no real time order between W2 and R1. Thus, it is okay for R(x) = 1.

Single Operation

Linearizability treats each individual operation as atomic:

read(x)
write(x,1)
compareAndSet(x, 1, 2)

It does not automatically make a group of operations atomic.

Consider transferring $10:

write(A, A - 10)
write(B, B + 10)

Even if both writes are individually linearizable, another client may read between them.

1. A decreases by $10
2. Another client reads A and B       ← sees intermediate state
3. B increases by $10

So linearizability alone does not provide an atomic transaction.

To make the entire transfer appear as one operation, you need a transaction guarantee such as Two Phase Commit for Serializability.

transaction {
    A = A - 10
    B = B + 10
}

Why it matters?

• Hides the complexity of the underlying distributed system from applications
• Linearizability is useful when stale or contradictory decisions are dangerous

Systems that implement linearizability

• 08-Paxos
• 09-Raft

Cost

Linearizable systems usually need coordination between replicas. This introduces:

• Network-round-trip latency
• Reduced availability during partitions
• Dependence on a quorum or current leader

Sequential Consistency

Sequential consistency says that the result must be explainable by one global sequential ordering that:

1. Contains every operation.
2. Preserves each individual client’s program order.
3. Does not require real-time order between different clients unless they have causal relationships.

Suppose two processes running operations concurrently and x is initially 0:

P1 ---W1(x+=1)---
P2                ---R2(x)=1--- ---W2(x+=1)---

Then, W1 must be in real-time before W2 since there is causal relationships from W1 -> R2 -> W2.

Also, suppose:

P1 ---W1(x+=1)---
P2                ---R2(x)=0---

This is not linearizable because the completed write precedes the read in real time.

However, it is sequentially consistent if the system explains the global order as:

R2(x) = 0 -> W1(x+=1)

That order contradicts wall-clock time, but it does not reverse either client’s own operations.

Linearizability is strictly stronger than Sequential Consistency

• Linearzability: total order + real-time ordering
• Sequential: total order + process ordering
  • process ordering < real-time ordering

Sequential consistency may require less synchronization than linearizability, although implementing some single global order can still be expensive.

Scenario	Linearizable	Sequentially consistent
Preserve each client’s order	Yes	Yes
One global order	Yes	Yes
Preserve real-time order across clients	Yes	No

Why it matters

Sequential consistency gives programmers one global interleaving to reason about without requiring every operation to respect physical time. It is especially relevant to:

• Shared-memory models
• Replicated logs
• Ordered event processing
• Systems where program order matters more than immediate visibility

Causal Consistency (Happened before relationship)

• Writes that are causally related must be seen by all processes in the same order.
• Concurrent writes may be seen in a different order on different processes.
• Unlike sequential consistency, causal consistency does not require every replica to place unrelated events in one shared global order.

Example: Causal but Not Sequential

The result of reads shown above is impossible in sequential consistency

• because there is no way to create a total order while preserveing process ordering
• However, causal consistency is possible

Why it matters

Causal consistency works for applications where users care about cause-and-effect order, but global synchronization would be too slow:

• Social-media posts and replies
• Chat messages
• Comment threads
• Collaborative applications
• Geo-replicated user data
• Offline-capable mobile applications

Causal+ Consistency (with Convergent Conflict Handling)

It provides the same causal-order guarantee as causal consistency, but adds a rule ensuring that replicas eventually agree when concurrent writes conflict.

Suppose two concurrent writes occur:

Replica A: x = "blue"
Replica B: x = "red"

Plain causal consistency does not, by itself, require a particular convergent conflict-resolution policy to resolve this writes conflict.

Causal+ can apply a deterministic rule, such as:

• Last-writer-wins using a well-defined timestamp and tie-breaker
• Higher Replica ID Wins
• Application-specific merge
• Store all concurrent versions

Property	Causal	Causal+
Preserves causal order	Yes	Yes
Concurrent operations may appear in different orders	Yes	Yes
Deterministic conflict resolution	Not required	Required
Replicas converge after receiving the same updates	Not necessarily	Yes

A causal+ system: COPS

COPS is a geo-replicated key-value store designed around causal+ consistency.

Conceptually:

1. A client reads values along with their causal metadata.
2. A later write includes its dependencies.
3. A remote replica receives the write.
4. It waits until the required dependencies are locally available.
5. The write becomes visible only after its dependencies are recieved.
6. Concurrent conflicts are handled with a convergent rule.

This avoids global coordination for unrelated operations while preventing effects from appearing before their causes.

Why it matters

Causal+ is attractive for large geo-replicated services because it combines:

• Low-latency local operations
• Causal user experience
• Operation during many network failures
• Eventual agreement between replicas

Eventual Consistency

Eventual consistency provides an eventual convergence guarantee:

If updates stop and communication eventually succeeds, all replicas will eventually converge.

Eventual consistency system example is presented here: 03-Eventual Consistency & Bayou

Why it matters

Eventual consistency is appropriate when temporary staleness is acceptable:

• DNS
• Caches
• Search indexes
• Like/view counters
• Product recommendations
• Replicated content

Example: Eventual but Not Causal