Distributed Systems and CAP

A distributed system coordinates work or state across processes that communicate through a network. Distribution can put data nearer readers, spread load and survive machine failures. It also removes a useful assumption: one participant cannot directly inspect another participant's state. It learns through messages that can arrive late or never arrive.

Two healthy servers can disagree about the same account because an update has not crossed the network. CAP describes a limit on the guarantees a shared read/write service can provide when communication fails. Understanding that limit starts with separating what happened from what a caller knows happened.

The downloadable lab needs Python 3.11+ and only the standard library. Extract it, enter its directory and run:

python3 lab.py
python3 -m unittest discover -s . -v
# Assertions cover refusal, stale reads, ambiguous writes and repair.

This is a deterministic teaching model with two live replicas and an injected broken link. It uses no network services. Its sequential simulator steps expose decisions; they do not implement consensus, failure detection or durable replication.

A timeout leaves more than one explanation

A partial failure affects some participants or communication paths while others keep working. A client might reach server A while A cannot reach B. A write might reach A while A's reply cannot reach the client. A successful health check from another location does not establish that this particular path works.

In an asynchronous network model there is no known upper bound on message delay. Silence cannot conclusively distinguish a failed participant from a slow participant or a broken path. Production deadlines let callers stop waiting; they do not reveal remote state or undo remote work.

The fixture places failure on either side of the same write. These runs start from independent registers containing zero:

from lab import Register, OutcomeUnknown

for fault, expected in (("lost_request", 0), ("lost_reply", 7)):
    register = Register()
    try:
        register.write("A", 7, fault=fault)
    except OutcomeUnknown as error:
        assert str(error) == "client deadline: no acknowledgement"
    assert register.read("A") == expected
# Identical client observation; different server state.

The final inspection belongs to the experiment's observer. The timed-out client has no such privileged knowledge. Retrying an increment could apply it twice; treating the timeout as failure could abandon a successful operation. Stable operation identity, status lookup and reconciliation address that uncertainty. Queues and Retries develops durable idempotency.

An explicit refusal is a different observation. In this fixture, Refused guarantees that the server rejected the operation before applying it. Real APIs must document which errors carry that guarantee: a proxy-generated error after forwarding a request may still leave the result unknown.

What CAP actually requires

For the theorem's shared read/write register, the three terms have precise roles:

• Consistency means linearizability: operations behave as if each took effect at one instant between invocation and completion, respecting the real-time order of operations that do not overlap.
• Availability requires every request received by a non-failing node eventually to complete its operation. It places no fixed response-time bound.
• Partition tolerance admits executions where communication between groups is lost. Nodes on both sides may remain alive and reachable by their clients.

During such a partition, a service cannot guarantee both a linearizable read/write register and completion of every request at every non-failing node. A partition is a failure condition to handle, rather than an interchangeable feature to remove from a deployment checklist.

Completion has an operation contract. For a read it means returning a register value; for a write it means acknowledging the specified update. Returning HTTP 503 for every request does not satisfy that availability requirement. A fast refusal can be useful operational behavior while leaving the requested operation unavailable. Conversely, formal availability allows responses so slow that they miss an application's latency SLO. Uptime percentages and deadline success rates measure different things.

To make linearizability concrete, suppose the register begins at zero and a write sets it to seven. With no other writes, a read invoked after the write's acknowledgement must return seven. An overlapping read may return zero or seven because it can be ordered before or after that write.

The lab's bounded checker searches possible legal sequential orders for a complete history. start and end are logical event positions, not timestamps from loosely synchronized servers:

from lab import Op, linearizable

assert not linearizable([
    Op("write", "write", 7, start=1, end=2),
    Op("read", "read", 0, start=3, end=4),
])
assert linearizable([
    Op("write", "write", 7, start=1, end=4),
    Op("read", "read", 0, start=2, end=3),
])
# Only the first history forces the write to precede the read.

The checker supports at most eight complete successful operations on one integer register. It rejects unsupported operation types. It cannot analyze pending or outcome-unknown writes: simply dropping such a write could hide an effect observed by a later read.

Database ACID consistency refers to preserving the application's invariants across transactions, such as valid account balances. It does not by itself specify when a remote reader sees a completed update. A local transaction can enforce a constraint while a separate replica remains stale. Transaction isolation, cross-object invariants and replica visibility need their own guarantees; Indexes and MVCC covers the transaction boundary.

Two sides of a disconnected register

Start A and B at zero. Break their link, acknowledge a write of seven at A, then ask B to read. B cannot learn about that write through the broken link. It cannot distinguish this execution from one where A accepted a different value. No choice of local answer can always satisfy the shared linearizable register's specification.

The fixture exposes two policies. authority routes operations through a fixed A authority. B refuses when disconnected; A can keep working. local lets each node use its own copy. When connected, a write copies to both replicas in a single simulator step. These are specified teaching rules, with no leader election or failover.

For the same partitioned sequence, the policies produce different consequences:

from lab import Register, Refused

strict = Register("authority")
strict.partition()
assert strict.write("A", 7) == "ok"
assert strict.read("A") == 7
try:
    strict.read("B")
except Refused:
    pass
else:
    raise AssertionError("disconnected B must refuse")

local = Register("local")
local.partition()
assert local.write("A", 7) == "ok"
assert local.read("B") == 0
# Refusal preserves the strict contract; local success returns stale data.

The strict policy sacrifices operation availability at B to protect the order of successful operations. Its A never fails in this model. Promoting B safely after losing A requires protocols and fencing, which belong in Replication.

The local policy preserves response progress at both live nodes in this scenario while weakening consistency. Zero is a legitimate stored value under its weaker local-read contract, but it violates the shared register's linearizable history. Rebranding that answer as an error would lose the availability benefit. Claiming it is globally current would misstate the contract.

A's local history can look correct while B's local history also looks correct. Their combined history can still be wrong for one shared object. Separate replicas are implementations of that object, not independent objects whose guarantees can be assessed in isolation. The tests check this distinction and also verify that partitioned B can accept its own write in local mode.

Choose guarantees for each operation

Different consistency contracts constrain different observations:

These are not interchangeable settings on one universal scale. An operation's scope, routing and failure assumptions matter. Sticking to B lets a client observe B's local write in the fixture; switching that client to A immediately breaks that particular read-your-writes observation. A production session guarantee needs a mechanism that survives the supported routing changes.

Convergence also needs a mechanism. Restore the link after each side accepts a different value:

from lab import Register

register = Register("local")
register.partition()
register.write("A", 7)
register.write("B", 9)
assert register.read("B") == 9
register.heal()
assert (register.read("A"), register.read("B")) == (7, 9)

register.repair_from_a()  # Maintenance step with writes stopped.
assert (register.read("A"), register.read("B")) == (7, 7)
# Converged, but B's acknowledged write of 9 was discarded.

The explicit A-wins repair is intentionally crude. Restored connectivity alone does not send missing updates, resolve conflicts or preserve every accepted change. An actual design must define how updates propagate, which conflicts can merge and which require a business decision. Availability during disconnection does not imply eventual consistency automatically.

Choose the contract for the operation's consequences. A stale product description may be tolerable; an exclusive reservation needs a rule preventing competing owners, potentially refusing some requests during disconnection. A stale authorization decision can continue granting access after revocation. A local database constraint alone cannot enforce an exclusive claim across independently writable copies.

Real systems can expose different operations with different guarantees. For example, etcd v3.6 documents linearizable key-value operations by default and an optional serializable read mode that may return stale data; its watches have separate guarantees. That product's read-mode name should not be confused with a universal transaction isolation promise. Specify the operation, acceptable staleness, behavior under lost communication and recovery rule before choosing a database label.