Distributed Systems Theory

Distributed Systems Theory

A distributed system is a collection of autonomous computers communicating over a network to appear as a coherent system. The fundamental challenge: partial failures. In a single computer, either everything works or nothing does. In distributed systems, some components fail while others continue — creating subtle inconsistencies, split brains, and the impossibility results that define the field.

The Fundamental Challenges

Partial failures: a node can crash, a network link can fail, a message can be delayed arbitrarily. Unlike a single computer, you cannot distinguish "the remote node is slow" from "the remote node has crashed."

Asynchronous networks: there is no upper bound on message delivery time. A message may arrive in 1ms or 10 seconds or never. This makes reasoning about ordering and synchronization deeply hard.

Independent failure modes: two nodes can have conflicting views of state. Both think they are the leader. Both accept writes. Data diverges. This is the split-brain problem.

CAP Theorem

Eric Brewer's CAP theorem (formally proved by Gilbert and Lynch): a distributed data store can provide at most two of:

• Consistency: every read returns the most recent write (or an error)
• Availability: every request receives a response (not an error)
• Partition Tolerance: the system continues operating despite network partitions (messages lost between nodes)

Network partitions are not optional — any distributed system over a real network must handle them. So the real choice is between CP (sacrifice availability during partitions; return errors rather than stale data) and AP (sacrifice consistency during partitions; return stale data rather than errors).

CP systems: ZooKeeper, HBase, traditional RDBMS with synchronous replication — return errors when they cannot guarantee up-to-date data.

AP systems: Cassandra, DynamoDB, CouchDB — return the best available data even if stale, converge later.

PACELC extends CAP to cover normal operation: there's a tradeoff between latency and consistency even when there are no partitions. Replicating writes synchronously before acknowledging increases consistency but latency.

Consistency Models

Linearizability (strong consistency): every operation appears to take effect atomically at a single point in time, consistent with a global clock. The strongest model; requires coordination overhead.

Sequential consistency: all operations appear in some sequential order consistent with each process's local order. Weaker than linearizability — does not require a global clock.

Causal consistency: causally related operations appear in causal order to all processes. Concurrent operations (no causal dependency) may appear in different order. Implemented using vector clocks.

Eventual consistency: if no new updates are made, all replicas will eventually agree. No bounds on convergence time. CRDTs (Conflict-free Replicated Data Types) provide specific data structures (counters, sets, registers) that merge concurrent updates deterministically.

FLP Impossibility

Fischer, Lynch, and Paterson (1985) proved: in an asynchronous distributed system, no consensus algorithm can be both correct (all non-faulty processes decide, all decide the same value) and fault-tolerant to even one crash failure.

This seems to make consensus impossible. The resolution: real systems use partial synchrony (assume message delays are bounded most of the time) or randomization (break symmetry with coin flips). Both approaches allow consensus in practice while technically violating the FLP model.

Consensus Protocols

Paxos (Lamport, 1989): the canonical consensus algorithm. A proposer proposes a value to a quorum of acceptors, which promise not to accept proposals with lower proposal numbers. If a quorum accepts, the value is decided. Complex to implement correctly — many subtleties.

Raft (Ongaro and Ousterhout, 2014): designed for understandability. Elects a leader that handles all writes, replicates a log to followers. Leader election uses randomized timeouts; log replication is straightforward. Used in etcd (Kubernetes state), CockroachDB, TiKV.

Quorum systems: require responses from a majority (quorum) of nodes. If you have 2f+1 nodes, any two quorums overlap by at least one node, ensuring at least one node in any quorum has the latest data. This allows tolerating f simultaneous failures.

Replication Strategies

Single-leader replication: one node accepts all writes, propagates to followers. Simple, strong consistency if synchronous. Leader becomes a bottleneck and single point of failure.

Multi-leader replication: multiple nodes accept writes, replicate to each other. Higher write availability; conflict resolution is the problem. Last-write-wins, version vectors, CRDTs are solutions.

Leaderless replication (Dynamo-style): any node accepts reads and writes. Uses quorums: write to W nodes, read from R nodes; if W + R > N (total replicas), reads always overlap with writes. Cassandra, Riak, DynamoDB use this model.

Distributed Transactions

Two-Phase Commit (2PC): coordinator asks all participants to prepare (acquire locks, write undo log), then commits or aborts. Provides atomicity but blocks if coordinator crashes while participants are prepared — they cannot release locks or commit without the coordinator's decision.

Three-Phase Commit (3PC): adds a pre-commit phase to allow participants to commit if the coordinator fails during commit. Safer but requires a synchronous network (bounded delays) — impractical for WAN.

Saga pattern: a sequence of local transactions, each publishing events that trigger the next. Compensating transactions undo completed steps on failure. No distributed locks — highly available but requires careful design of compensating actions.

The Real-World Implication

Every database, every distributed cache, every service mesh makes these tradeoffs. When you see "eventual consistency" in DynamoDB documentation, you now know it means: AP in the CAP sense, with convergence guaranteed eventually, and that you must design your application to handle stale reads. When you configure a Kafka consumer group, you're reasoning about partitions and consumer assignment — distributed coordination. These aren't just buzzwords; they're consequences of mathematical theorems about networked systems.