Consistency, CAP and Consensus

Strong and eventual consistency, CAP and PACELC, quorums, leader election and what Raft solves.

Est. 40 min Updated Suggest a fix
// Part 01 — Consistency is a contract

Ask What a Read Is Allowed to Return

In a distributed system, a write may be copied to multiple nodes. A read can reach a node that has not yet received the latest write. Consistency describes the guarantees clients receive about the order and visibility of operations; it is not a vague synonym for correctness. State the guarantee for each workflow.

A bank-like balance display after a transfer may need to reflect the completed transfer immediately. A product recommendation count can often be briefly stale. A user profile update may require read-your-writes for that user while other readers catch up. The correct choice depends on the invariant and the user experience.

GuaranteeIntuitionExample use
LinearizabilityEach operation appears to take effect at one instant in real-time orderA critical reservation or balance decision
Sequential consistencyAll clients see one shared order that respects each client’s program orderShared state where real-time ordering is not required
Eventual consistencyReplicas converge if updates stop and communication recoversA follower count or search index projection
Read-your-writesA client sees its own successful writes on later readsA profile immediately after saving it
💡 Note
A consistency guarantee is an externally visible contract. Calling a system "eventually consistent" does not explain how long lag lasts, what users see during lag, or which operations remain safe.
// Part 02 — Replication timing

Strong and Eventual Consistency Are Trade-offs

Synchronous replication waits for enough nodes to confirm an update before acknowledging it. This can provide stronger visibility or durability, but increases latency and may reject writes when required nodes are unreachable. Asynchronous replication acknowledges before all copies catch up, improving write responsiveness while allowing stale reads and recovery choices after a primary failure.

text
Asynchronous path:
Client -> Leader: write value v2
Client <- Leader: acknowledged
Leader ------ v2 ------> Replica A (applied)
Leader ------ v2 - delayed -> Replica B (still v1)

A read from B can return v1 until the update arrives.

Stronger consistency can be scoped: read from the leader for a critical operation, use a session token to ensure a replica has caught up, and allow stale reads for noncritical views. If the application has no clear staleness policy, it tends to rediscover one through production incidents.

📌 Real World Example
For a UPI-like payment state, do not infer payment success from a stale replica or a browser redirect. Use an authoritative payment state transition and reconcile asynchronous provider callbacks against that source of truth.
// Part 03 — CAP and PACELC

CAP Is About a Network Partition

CAP describes a trade-off when a distributed data system is partitioned: nodes cannot communicate reliably. A system cannot guarantee both a single consistent view for all operations and a successful response from every side of the partition. A consistency-oriented design may reject or delay some operations; an availability-oriented design may accept operations that later need conflict resolution.

CAP does not mean you permanently pick only two of consistency, availability, and partition tolerance. Real systems must tolerate network partitions; the design question is what they do while one occurs. Outside a partition, there are still latency-versus-consistency decisions. PACELC summarizes this as: if there is a partition, trade availability against consistency; else, trade latency against consistency.

SituationConsistency-oriented behaviorAvailability-oriented behavior
Network partitionReject writes that cannot be safely coordinatedAccept some writes and reconcile conflicts later
Normal operationWait for coordination or quorum before respondingRespond from a nearby copy with a weaker freshness guarantee
RecoveryResume when a safe leader or quorum is availableMerge or resolve divergent updates under defined rules
⚠️ Important
CAP is not a label to apply to an entire product casually. A database may offer different consistency modes, and an application can use different policies for separate operations.
// Part 04 — Quorums

A Quorum Is a Voting Rule, Not Magic

Suppose a replicated value has N voting replicas. A read quorum R and write quorum W overlap when R + W is greater than N. That overlap can help a read encounter a replica that received a write, assuming the protocol, versioning, membership, and failure model support the guarantee. The arithmetic alone does not make an arbitrary distributed store linearizable; a correct protocol must also order concurrent writes and handle membership changes.

quorum_check.py
python
def quorum_overlap(replica_count: int, read_quorum: int, write_quorum: int) -> bool:
    if not (1 <= read_quorum <= replica_count):
        raise ValueError("read quorum must be between 1 and replica count")
    if not (1 <= write_quorum <= replica_count):
        raise ValueError("write quorum must be between 1 and replica count")
    return read_quorum + write_quorum > replica_count


replicas = 5
for reads, writes in [(3, 3), (2, 2), (1, 5)]:
    print(reads, writes, quorum_overlap(replicas, reads, writes))

Quorum size changes availability and latency. Requiring more acknowledgements can improve fault tolerance or freshness under specific protocols, but a slow or unreachable replica can delay a response. Real systems may use leader leases, version vectors, epochs, or other mechanisms; read the actual product consistency model rather than importing a simple majority formula.

// Part 05 — Consensus

Consensus Keeps Replicas in Agreement on a Decision

Consensus lets a group of nodes agree on a value or ordered log despite some node failures, under a stated failure model. A replicated state machine applies the same committed log entries in the same order on multiple nodes. Systems commonly use a leader to simplify ordering: the leader proposes entries, a quorum acknowledges them, and nodes apply committed entries in order.

text
Client -> Leader: append entry 42
Leader -> Followers: replicate entry 42
Followers -> Leader: acknowledge
Leader: quorum reached; entry 42 is committed
Leader -> Client: success
Followers: apply committed entries in order

If the leader fails, eligible nodes elect a new leader before new writes proceed.

Raft is a consensus algorithm designed to make leader election, log replication, and safety easier to reason about. Terms distinguish leadership epochs; a candidate needs votes from a majority; log rules prevent an elected leader from discarding committed entries. Consensus does not make the entire application reliable automatically: clients, disks, networks, configuration changes, and dependent services still fail.

  1. Identify the failure model and which nodes can vote.
  2. Elect one leader for a term and reject stale leadership using terms or epochs.
  3. Replicate entries and mark them committed only under the protocol’s quorum rule.
  4. Apply committed entries deterministically and recover from durable logs or snapshots.
  5. Change cluster membership through the protocol, not by editing node lists casually.
// Part 06 — Choose a product contract

Expose Consistency to Application Code

A storage API should make important guarantees visible. Is a write acknowledged after local persistence, a replica quorum, or a consensus commit? Can reads be stale? Can a client request read-your-writes? What happens on a timeout where the client cannot tell whether the write committed? These details affect safe retries and user-facing state.

For uncertain outcomes, use an operation ID and query its status instead of repeating an unsafe action. For updates that can conflict, use version checks or a domain-specific merge rule. For projections, record their source offset or version so the UI can report that results are still catching up rather than pretending they are current.

🎯 Pro Tip
Draw a timeline for two concurrent clients and write down what each may observe. If you cannot state the allowed outcomes, the consistency requirement is not yet precise enough to choose a protocol.
// Part 07 — Common mistakes

Use Precise Words for Distributed Guarantees

Describing CAP as a permanent choice of any two properties

Why: That slogan hides the condition: the conflict appears during a network partition.

Fix: Describe behavior during a partition and the latency/consistency choice during normal operation.

Assuming a quorum formula guarantees linearizability

Why: Overlap alone does not define ordering, concurrent-write handling, or membership safety.

Fix: State the full protocol and failure model, then verify the database’s documented guarantees.

Treating eventual consistency as an acceptable default for every feature

Why: Some invariants such as a one-time payment or inventory reservation cannot tolerate arbitrary divergence.

Fix: Set per-operation freshness and invariant requirements; use authoritative writes for critical transitions.

Retrying a timed-out write blindly

Why: The original operation may have committed even though its response was lost.

Fix: Use idempotency keys or operation-status lookup to resolve ambiguous outcomes safely.

// Part 08 — Practice

Specify Consistency for a Payments and Catalog App

Practice

Turn vague requirements into allowed and forbidden outcomes

  1. For payment status, product availability, search results, and profile edits, choose a freshness guarantee and explain the user impact.
  2. Draw a primary-replica timeline where a client writes and immediately reads from a lagging replica; propose two ways to preserve read-your-writes.
  3. For N = 5 replicas, compare read/write quorum pairs and explain why overlap is necessary but not a complete consistency proof.
  4. Describe what a leader-based replicated log does when the leader fails before and after a quorum commits an entry.
  5. Write a safe client strategy for a timed-out payment-state write whose commit status is unknown.

Hint: For every answer, name what is guaranteed, what can be delayed or rejected, and how the client recovers from an uncertain response.

🎯 Key Takeaways

  • ✓Consistency specifies which operation histories a client is allowed to observe; choose the contract per workflow.
  • ✓Asynchronous replication can return stale reads; synchronous coordination trades latency or availability for stronger guarantees.
  • ✓CAP describes behavior during a network partition, while PACELC also highlights normal-operation latency trade-offs.
  • ✓Quorum overlap helps only within a protocol that correctly orders writes and manages membership and failures.
  • ✓Consensus coordinates a committed order of decisions; Raft structures leader election and log replication.
  • ✓Use idempotency or status lookup when a timeout leaves a write outcome ambiguous.

Next

What comes next

Coordination can still be slow or unavailable. Next, contain failures with timeouts, bounded retries, circuit breakers, bulkheads, and rate limits.

Lesson 09 · Reliability Patterns — Timeouts, Retries, Circuit Breakers and Rate Limiting →

HELP US IMPROVE

How was this lesson?

Your note is shared with the Chaduvuko team for review. Please don’t include personal or sensitive information.

Choose your feedback

Spotted a mistake or something unclear? Suggest a fix on GitHub or email us. Select the text first and it is quoted for you.

Share

Discussion

0

Have a better approach? Found something outdated? Share it — your knowledge helps everyone learning here.

Continue with GitHub
Loading...