Consistency and consensus

If writes stop, all replicas eventually return the same value; until then, reads may return anything older.

It is a very weak guarantee: it says nothing about when replicas converge, and it makes reads after writes unpredictable. Stronger models cost performance, which is why many systems settle for it.

Make a replicated object behave as if there were one copy and every operation took effect atomically at a single point between its start and end.

It is a recency guarantee: once any read returns a new value, all later reads (in real time) must too. Checking it means finding a total order of operations that respects real time and register semantics.

An atomic operation that sets a value only if it currently equals an expected value, and reports whether it succeeded.

With a linearizable register plus CAS you can implement locks, leader election and uniqueness constraints; whether a CAS may succeed depends on the single global order of all writes.

During a network partition, a system must choose between linearizability and availability.

Partitions are not optional, so CAP really says: when one happens, either some clients get errors (stay consistent) or everyone gets answers that may be stale (stay available). It is a narrow theorem, more slogan than design tool.

Linearizable reads and writes have response times at least proportional to network delay.

Most systems that drop linearizability (even multicore CPU caches) do it for speed, not for partition tolerance. On a WAN with variable delays, every linearizable operation pays the round trip.

Operations that are causally related are seen by everyone in the same order; concurrent ones may be seen in any order.

Causality gives a partial order, linearizability a total one. Causal consistency is the strongest model that does not slow down with network delay and stays available during partitions.

A (counter, node id) pair; every node sends its counter on every message and, on receipt, sets its counter to max(local, received) + 1.

They give a compact total order that is consistent with causality: if A happened before B, A's timestamp is smaller. The converse fails: a smaller timestamp does not mean the event came first causally.

One counter per node, merged element-wise on each message, so each event carries a summary of everything it has seen.

Unlike Lamport timestamps, vectors can tell whether two events are concurrent or causally ordered, at the cost of size growing with the number of nodes.

A total order of timestamps can pick a winner among conflicting claims only after all claims have been collected.

To enforce 'one owner per username' at the moment of the request, a node must know no other node is concurrently claiming it with a lower timestamp, which requires hearing from every node. You also need to know when the order is final: total order broadcast.

A protocol that delivers every message reliably to every node, and in the same order on all of them.

It is state machine replication: apply the same deterministic operations in the same order and replicas stay identical. It is equivalent to repeated consensus, and lets you build linearizable compare-and-set on top of an append-only log.

Ensuring that a transaction spanning several nodes either commits on all of them or aborts on all of them.

Committing independently on each node risks some committing while others abort, violating atomicity. Once committed, a transaction cannot be retracted, so the decision must be made together.

A coordinator asks every participant to prepare (vote), then writes a commit or abort decision to its log and broadcasts it.

Two points of no return make it work: a participant that votes yes can no longer abort on its own, and the coordinator's logged decision is final. Its weakness is that it blocks if the coordinator dies.

A participant that has voted yes but not yet heard the decision: it can neither commit nor abort.

It must hold its locks until the coordinator recovers, blocking other transactions. Orphaned in-doubt transactions sometimes need a human (heuristic decision) to resolve, which risks breaking atomicity.

A standard C API for two-phase commit across heterogeneous systems such as databases and message brokers.

The coordinator is often a library inside the application, so if the application server dies, its log goes with it. XA must also be lowest common denominator: it cannot detect deadlocks across systems or support SSI.

Getting several nodes to agree on a value, with uniform agreement, integrity, validity and termination.

Leader election, atomic commit, uniqueness, linearizable CAS and total order broadcast all reduce to it. Unlike 2PC, fault-tolerant consensus keeps making progress as long as a majority is up.

Algorithms such as Raft, Multi-Paxos, Zab and Viewstamped Replication that decide a sequence of values (a log).

They elect a leader per epoch and require a majority quorum both to elect it and to accept each proposal; any two majorities overlap, so a decision can never be lost or contradicted.

A monotonically increasing number attached to each leadership; a higher epoch always wins.

A leader cannot trust that it is still leader. Before deciding anything it needs a quorum of acknowledgments in its epoch, so a deposed leader from an older epoch can never get a value committed.

In a fully asynchronous model with no clocks, no deterministic algorithm can always reach consensus if a node may crash.

Real systems escape it with timeouts (to suspect crashed nodes) or randomness. That is why election timeouts are randomized and why consensus can stall when the network is very unreliable.

A small, fault-tolerant, linearizable key-value store that applications use for locks, leader election, membership and configuration.

It outsources consensus: few apps should implement Raft themselves. It offers linearizable atomic operations, total ordering (zxid as fencing tokens), failure detection via sessions, and change notifications.

A znode tied to the client session that created it; when heartbeats stop and the session times out, it is deleted automatically.

It turns failure detection into data: a lock or membership entry disappears when its owner dies. But a paused client may not know its session expired, so the resources it guards must check fencing tokens.