Consistency

Types of convergence (when all replicas eventually agree)

Definitions

ACID Consistency

The state satisfies application-specific invariants (e.g. every course with students enrolled must have at least one lecturer) at any given point in time

See also: CAP Theorem

Replication Consistency

Many models to choose from! Most common being read-after-write consistency

Imagine a scenario where

• Client writes to servers A and B but request to A fails (so only B has correct state)
• Client reads from servers A and B but request to B fails (so only client gets A’s incorrect state)

Clearly, client is getting inconsistent results. We can fix this via a quorum read.

Atomic Commitment Problem

Big problem with distributed transactions: atomic commitment problem

• Either all nodes must commit or all must abort
• If any node crashes, all must abort

Usually done through two-phase commit (2PC)

• Client begins a transaction with database nodes A and B
• When done, the client commits the transaction with the coordinator
• Coordinator tells both A and B to prepare for the commit
• If both A and B think it is fine for them to commit, then coordinator tells both to commit (A and B cannot go back on their response to prepare, if they said they are prepared for the commit they must commit when the coordinator tells them to)

But what if the coordinator crashes? The algorithm is blocked until coordinator recovers. We can use a fault-tolerant two-phase commit (uses total order broadcast)

Eventual Consistency

Alternative to linearizability is eventual consistency.

If there are no more updates, eventually all replicas will be in the same state.

But how do we know when there are no more updates? This can be an indefinite amount of time. An upgraded version of this is strong eventual consistency which has a few additional rules:

• Eventual delivery: every update made to one non-faulty replica is eventually processed by every non-faulty replica
• Convergence: any two replicas that have processed the same set of updates are in the same state

Properties

• Does not require waiting for network communication
• Causal broadcast can disseminate updates
• Conflicts arising from concurrent updates need to be resolved

Summary

Summary of minimum system model requirements for various forms of consistency

Problem	Must wait for communication	Requires synchrony
atomic commit	all participating nodes	partially synchronous
consensus, total order broadcast	quorum	partially synchronous
linearizable get/set	quorum	asynchronous
eventual consistency, causal broadcast, FIFO broadcast	local replica only	asynchronous