A single-node database can rely on shared memory, one clock and the certainty that a function call either returned or the whole process died. A distributed database has none of these. Nodes exchange messages over links that lose, delay and duplicate them, each node has its own clock, and a node can never tell whether a silent peer is dead, slow or cut off by the network.

This chapter establishes the model that the rest of Part II is built on. It names the false assumptions engineers make, defines what a "link" guarantees, proves with two small arguments (the two generals and FLP) what cannot be done, and introduces the synchrony and failure models every later algorithm is stated in. Interviewers use this material to separate people who have memorised Raft from people who understand why Raft needs a majority.

In one minute

• Concurrent programs on one machine share memory; distributed programs share nothing and communicate only by messages. Delay and failure become indistinguishable.
• The eight fallacies of distributed computing (the network is reliable, latency is zero, bandwidth is infinite, ...) describe assumptions that hold locally and break remotely. Petrov adds processing time, clock skew, state divergence, local-versus-remote execution, failure handling, partitions and cascading failures.
• Links are classified by their guarantees: a fair-loss link may drop and duplicate, a stubborn link retransmits forever, a perfect link delivers reliably, exactly once, without inventing messages. Each is built from the one below using retransmission, acknowledgements and deduplication.
• Exactly-once delivery is not achievable by the transport alone; real systems deliver at least once and make processing idempotent or deduplicate on the receiver.
• The two generals' problem shows that two parties on a lossy link can never be certain they agree: every acknowledgement needs its own acknowledgement.
• FLP impossibility: in a fully asynchronous system with even one crash failure, no deterministic consensus protocol can guarantee termination. Practical protocols escape by assuming partial synchrony and using failure detectors.
• Failure models form a hierarchy: crash-stop, crash-recovery, omission, arbitrary (Byzantine). Most databases assume crash faults; blockchains and some replicated state machines tolerate Byzantine ones.
• Failures are handled by redundancy: groups of processes mask individual failures so the client sees a single reliable service.

Concurrent versus distributed computing

Concurrent computing describes multiple tasks that make progress during overlapping time intervals on one machine. They coordinate through shared memory: locks, atomics, condition variables. Reasoning about them is hard, but the hardware provides two things for free: a memory operation either happens or does not, and every thread observes the same clock.

Parallel computing is the special case where tasks literally execute at the same instant on different cores. Concurrency is about structure (independent tasks), parallelism about execution (simultaneous progress). A single core can run a concurrent program by interleaving; it cannot run a parallel one.

Distributed computing removes the shared memory. Each process has only its local state and learns about others by exchanging messages. Two consequences follow immediately:

1. Every remote operation takes unknown time. A reply may be slow because the peer is busy, because the network is congested, or because the peer crashed before replying. The caller cannot distinguish these cases.
2. There is no global "now". Processes cannot agree on the order of events just by looking at their clocks.

Three questions that the hardware used to answer now have to be answered by the algorithm:

Question	Governed by	Why it matters
How long do we wait for a peer?	The system's synchrony assumptions	Decides whether timeouts are meaningful at all
Why has the peer not answered?	The failure model	Decides which misbehaviours the algorithm must tolerate
How does the system keep working anyway?	Fault tolerance mechanisms (redundancy, failure detectors, retries)	Decides what the client observes during a failure

Shared state in a distributed system

Even when a distributed system offers something that looks like shared state (a distributed lock, a replicated key-value store), every access is a message exchange and inherits all the uncertainty above. Replication and consensus are, at bottom, about building a usable illusion of shared state out of message passing.

Fallacies of distributed computing

In 1994 L. Peter Deutsch at Sun Microsystems listed the assumptions that engineers new to distributed systems make; James Gosling added the eighth. The list is still accurate.

Fallacy	What actually happens
The network is reliable	Packets are dropped, switches fail, cables get cut
Latency is zero	A cross-region round trip is tens to hundreds of milliseconds; a local call is nanoseconds
Bandwidth is infinite	Large replication streams compete with client traffic
The network is secure	Traffic can be observed or altered unless encrypted and authenticated
Topology does not change	Nodes join, leave, move; IP addresses are reassigned
There is one administrator	Different teams, clouds and vendors operate different parts
Transport cost is zero	Serialization, copying and encryption consume CPU and money
The network is homogeneous	Mixed hardware, protocol versions and MTUs are the norm

Petrov adds the categories below, which are the ones that bite database engineers.

Processing is not instantaneous

A message that reaches a remote node is not processed on arrival. It joins a queue behind other requests, waits for a thread, may wait for disk, and only then produces a reply, so observed latency mixes network time with remote queueing time. Systems protect themselves with backpressure: a slow consumer signals producers to slow down (bounded queues, TCP flow control, credit-based schemes) instead of letting unbounded queues grow until memory runs out.

Clocks and time

Physical clocks on different machines drift and are only loosely synchronised by NTP; skew of milliseconds is normal and seconds happen. Comparing timestamps from different nodes to decide which write "came first" is unsafe unless the system is designed for it (Spanner's TrueTime bounds the uncertainty explicitly; most systems use logical clocks instead).

State consistency

When replicas apply updates independently, their states diverge. Some algorithms permit this on purpose (eventually consistent stores) and then need conflict resolution and read repair to reconcile. The divergence applies to metadata too: an eventually consistent database cannot assume every node has the same schema at the same moment, so schema changes have to be designed as propagating events, not as instantaneous facts.

Local and remote execution

Hiding a remote call behind an interface that looks local (a method call, an iterator over a "collection") is seductive and dangerous. Remote calls are orders of magnitude slower, can fail halfway, and may need retries; code that interleaves many small blocking remote calls with local logic performs terribly. Good distributed APIs make remoteness visible: batch operations, explicit timeouts, explicit error types.

Need to handle failures

In a long-running cluster, something is always down: a node restarting for maintenance, a disk being replaced, a rack losing power. Algorithms must treat failure as a normal input, detected by a heartbeat-fed failure detector (chapter 9), and specify how they behave when a node is suspected.

Network partitions and partial failures

A network partition occurs when two groups of nodes can each talk among themselves but not to the other group. Unlike a crash, both sides keep running and keep accepting requests, so they can produce conflicting results. Partial failures are the general form: some nodes or links fail while others work, and no single node can see the whole picture. Partitions are the scenario that forces the consistency-versus-availability trade-off discussed in chapter 11.

Cascading failures

A cascading failure starts in one component and spreads. The textbook sequence: a node slows down under load; clients time out and retry; the retries add load; the node slows further; its peers absorb redirected traffic and slow down too. Defences:

• Exponential backoff between retries, so that a struggling service gets exponentially less retry traffic.
• Jitter: randomise the backoff so that clients that failed together do not retry in lockstep (the "thundering herd").
• Circuit breakers: after a threshold of failures a client stops calling the failing service for a cooling-off period and fails fast, giving the service room to recover.

Distributed systems abstractions

To reason about algorithms we need precise names for what the communication layer guarantees. Petrov follows the layered model from Cachin, Guerraoui and Rodrigues' Introduction to Reliable and Secure Distributed Programming.

Links

A fair-loss link is the weakest useful abstraction, closest to a real network:

• Fair loss: if a correct process sends a message infinitely often, it is delivered infinitely often. Loss is possible but not systematic.
• Finite duplication: a message is duplicated at most a finite number of times.
• No creation: a message is delivered only if it was sent.

From the sender's point of view a message on a fair-loss link is in one of three states: not yet delivered, irrecoverably lost, or delivered. Crucially, the sender cannot tell which.

A stubborn link is built on a fair-loss link by retransmitting every message indefinitely. Its guarantee is stubborn delivery: if both processes are correct, every sent message is delivered infinitely often. Impractical as-is, it is the conceptual step that turns "may be lost" into "will arrive".

A perfect link (also called a reliable link) adds acknowledgements and deduplication to a stubborn link and provides:

1. Reliable delivery: a message sent between two correct processes is eventually delivered.
2. No duplication: each message is delivered at most once.
3. No creation: no message is delivered unless it was sent.

Acknowledgements and retransmits

To learn whether a message arrived, the sender needs a reply. The standard mechanism tags each message with a monotonically increasing sequence number: the sender transmits M(n), the receiver answers ACK(n), and the sender, on receiving the acknowledgement, knows M(n) reached its destination. If no acknowledgement arrives within some period, the sender retransmits.

Retransmission introduces a new problem. If ACK(n) was lost but M(n) arrived, the retransmitted M(n) arrives twice. For an idempotent operation (set x = 5, "mark order shipped") processing twice is harmless. For a non-idempotent one (debit 100 from account A) it is a bug. Since not every operation can be made idempotent, receivers deduplicate: they remember which sequence numbers they have processed and ignore repeats.

Message order

Two things upset order: messages take different paths and arrive out of sequence, and retransmits deliver old messages late. The receiver handles both with sequence numbers. It tracks the last sequence number it processed; a message with a lower or equal number is a duplicate and is dropped, and a message that skips ahead is held in a reordering buffer until the gap is filled. This is FIFO delivery per sender, which TCP provides within one connection.

Exactly-once delivery

Most systems honestly promise at-least-once delivery: the sender retransmits until acknowledged, so a message may be processed more than once. At-most-once is the opposite: send once, never retry, accept loss. Exactly-once delivery at the transport level is impossible on a lossy link, because the sender can never be sure the receiver's state matches its own (this is the two generals' problem, below).

What systems actually provide is exactly-once processing: at-least-once delivery combined with idempotent handlers or receiver-side deduplication keyed on a sequence number, producer id or transaction id. Kafka's idempotent producer and transactions, TCP's sequence numbers and a database's unique constraint on an idempotency key are all instances of this pattern.

Two impossibility results

The two generals' problem

Two armies camp on opposite sides of an enemy city. Their generals must attack at the same time or both lose. The only communication is a messenger who must cross enemy territory and may be captured. How can the generals agree on a time?

General A sends "attack at dawn". A cannot attack without knowing the message arrived, so B replies with an acknowledgement. But now B cannot be sure A received the acknowledgement; if it was lost, A will not attack and B attacks alone. So A must acknowledge the acknowledgement, and B must acknowledge that, and so on. No finite exchange of messages makes both generals certain.

The result, first formalised by Akkoyunlu, Ekanadham and Huber in 1975 and named by Jim Gray in 1978, says that two parties on an unreliable link cannot reach common knowledge that they agree. It is the reason exactly-once delivery cannot be built from the transport alone, and it is the simplest demonstration that distributed agreement is fundamentally harder than local agreement. Practical systems live with it: they attack after a bounded number of acknowledgements and accept a small probability of inconsistency, or they design operations so that a partner acting alone does no harm.

FLP impossibility

The two generals' problem concerns lossy links. Fischer, Lynch and Paterson showed in 1985 that even with reliable links, consensus is impossible to guarantee in a fully asynchronous system if a single process may crash.

Consensus requires three properties:

1. Agreement: no two correct processes decide different values.
2. Validity: the decided value was proposed by some process.
3. Termination: every correct process eventually decides.

In an asynchronous model there is no bound on message delay or on how long a process takes to execute a step. A process that has not responded might be crashed or might merely be slow, and no timeout can tell them apart, because any timeout could be too short. FLP proves that for every deterministic consensus protocol in this model there exists an execution, with at most one crash, in which the protocol never terminates. Agreement and validity can be preserved (safety), but termination (liveness) cannot be guaranteed.

FLP is commonly misread. It does not say consensus is impossible in practice, only that no protocol can guarantee termination under the weakest timing assumptions; and it is not about message loss, since links are reliable in its model. The practical escape routes are:

• Strengthen the timing model to partial synchrony and use timeouts as failure detectors (Paxos, Raft, ZAB). Liveness holds whenever the system behaves synchronously for long enough.
• Randomisation (Ben-Or's protocol): with coin flips, termination is guaranteed with probability 1 rather than deterministically.
• Failure detectors as an abstraction (Chandra and Toueg): an eventually accurate detector is enough to solve consensus, which is why chapter 9 exists.

System synchrony

Synchrony describes how much the algorithm may assume about time.

Model	Assumptions	Consequences
Synchronous	Known upper bounds on message delay and on relative process speeds; clocks drift within known bounds	Timeouts are reliable failure detectors; simple algorithms work; the model rarely matches real networks
Asynchronous	No bounds at all; a message may take arbitrarily long, a process may pause arbitrarily	Timeouts mean nothing; FLP applies; only safety can be guaranteed
Partially synchronous	Bounds exist but are unknown, or hold only after some unknown stabilisation time	Algorithms stay safe always and become live once the network behaves; this is the model Paxos and Raft are designed for

The asynchronous model is the most pessimistic and the most honest about pathological cases (a stop-the-world garbage collection pause, a saturated link), which is why algorithms are proven safe under it. The partially synchronous model of Dwork, Lynch and Stockmeyer is the one practical systems live in: use timeouts for progress, and make sure a wrong timeout only slows things down, never violates safety.

Failure models

A failure model specifies which misbehaviours a process may exhibit. Algorithms are designed for a model and are unsafe outside it, so stating the model is part of stating the algorithm.

Crash faults

In the crash-stop (fail-stop) model a process executes correctly until some point, then halts and never recovers. This is the simplest model and a surprising amount of theory assumes it. The crash-recovery model allows a process to stop and later come back, usually with its stable storage intact but its volatile memory lost. Databases operate in crash-recovery: a node restarts, replays its log and rejoins, so protocols must tolerate a participant that forgets what it was doing mid-protocol unless it wrote it to disk first.

Omission faults

An omission fault means a process skips steps or its steps are not observed: it fails to send a message it should have sent (send omission), fails to receive one that was delivered (receive omission), or performs a step whose effect never becomes visible. From the outside, an omission fault looks like a slow or lossy network, so it is often folded into the link model. Crash faults are a special case: a crashed process omits every subsequent step.

Arbitrary (Byzantine) faults

In the arbitrary or Byzantine model a faulty process may do anything: send contradictory messages to different peers, decide a value nobody proposed, corrupt data, or collude with other faulty processes. Tolerating f Byzantine processes requires at least 3f + 1 participants and cryptographic authentication, and the protocols (PBFT and descendants) are several times more expensive in messages than crash-tolerant ones. Most databases trust their own nodes and stop at crash-recovery; Byzantine tolerance matters for blockchains and for surviving nodes that lie because of corruption or bugs.

Model	Faulty process may...	Example cause	Typical tolerance
Crash-stop	Halt forever	Hardware death	f < n/2 for consensus
Crash-recovery	Halt, then restart with disk state	Reboot, OOM kill	Same, with durable logging
Omission	Drop sends or receives	Full buffers, lossy links	Handled by retransmission
Arbitrary / Byzantine	Anything, including lying	Malice, memory corruption, bugs	n >= 3f + 1 plus signatures

Handling failures

The goal of fault tolerance is failure masking: the system keeps functioning, and clients ideally do not notice, when individual components fail. The universal tool is redundancy. Processes are organised into groups that hold the same data or perform the same role; when a member fails, the others continue, and the failed member is replaced or repaired. Replication (chapter 11) is redundancy of data, leader election (chapter 10) is redundancy of coordination, and consensus (chapter 14) is how a group agrees on state despite failures of some members.

Masking has limits: a majority-based group of n replicas tolerates fewer than n/2 crashes, and no amount of redundancy hides a partition that separates clients from the majority. Each later chapter therefore begins by stating which failures it masks.

Design trade-offs

Decision	Option A	Option B	Pick A when	Pick B when
Delivery semantics	At-least-once + idempotent handlers	At-most-once	Correctness matters (payments, replication)	Loss is acceptable (metrics, telemetry)
Timing model to design for	Asynchronous for safety, partial synchrony for liveness	Synchronous	Always for safety proofs	Only inside a tightly controlled environment such as a single chassis
Failure model	Crash-recovery	Byzantine	Nodes are trusted and operated by you	Nodes may be malicious or corrupt data silently
Reaction to overload	Backpressure and load shedding	Unbounded queues and retries	Always	Never; this is how cascades start

The recurring theme: be pessimistic about timing and failures when proving safety, pragmatic when engineering liveness. Paxos and Raft both stay safe under asynchrony and become live under partial synchrony.

Interview angle

• What is the difference between a concurrent and a distributed system? Concurrent processes share memory and a clock on one machine; distributed processes share nothing and communicate by messages with unbounded delay. The practical difference is that in a distributed system a non-response is ambiguous: the peer may be slow, dead or partitioned, and no local observation can tell which.

• Explain the two generals' problem and what it implies for real systems. Two parties on a lossy channel cannot reach certainty that both know a decision, because each acknowledgement itself needs acknowledging. It implies that exactly-once delivery cannot be guaranteed by the transport and that any two-party commit on an unreliable network has a window of uncertainty. Systems cope by bounding the number of rounds and making the actions idempotent or compensable.

• Is exactly-once delivery possible? How does Kafka claim it? Not at the transport level. Kafka provides exactly-once processing: the producer attaches a producer id and sequence number so the broker deduplicates retries, and transactions atomically commit output records together with consumer offsets. The underlying delivery is still at-least-once.

• State FLP in one sentence and explain why Raft works anyway. In an asynchronous system with one possible crash, no deterministic protocol can guarantee that consensus terminates. Raft is safe under asynchrony but relies on randomised election timeouts and the assumption that the network is eventually synchronous for liveness; when timing misbehaves, Raft stalls rather than diverges.

• What goes wrong if you treat a remote call like a local one? Latency goes from nanoseconds to milliseconds and compounds across loops; partial failures (request sent, reply lost) create ambiguous outcomes; retries without idempotency duplicate effects; and timeouts, if absent, hang threads indefinitely. The fix is explicit remote APIs with batching, timeouts, idempotency keys and bounded retries.

• How would you design retry behaviour for a client of an overloaded service? Exponential backoff with full jitter so retries spread out, a retry budget capping retries to a percentage of normal traffic, a circuit breaker that fails fast after repeated errors, and idempotency keys so a retried request is safe. Also distinguish retryable errors (timeouts, 503) from non-retryable ones (400, 409).

• Which failure model does a database like etcd assume, and what does that imply? Crash-recovery: a node may halt and return with its disk intact, so it must persist its term and log before acknowledging anything. It does not tolerate a node that deliberately sends wrong log entries; that would require Byzantine tolerance with 3f + 1 nodes and signatures.

• What is a cascading failure and how do you stop one spreading? A localised slowdown that amplifies itself through retries and redirected load until it takes down neighbours. Stop it with backpressure (bounded queues), load shedding, retry budgets, backoff with jitter, circuit breakers and bulkheads that isolate resource pools per dependency.

Pitfalls and misconceptions

• "FLP says consensus is impossible." It says termination cannot be guaranteed in a fully asynchronous system with a crash. Safety is always achievable, and liveness is achievable under partial synchrony or with randomisation. Paxos and Raft are not violations of FLP; they sidestep its model.
• "Exactly-once is impossible, so duplicates are unavoidable." Duplicate delivery is unavoidable; duplicate effects are not. Idempotency keys and deduplication tables give exactly-once processing.
• "A timeout tells me the node is dead." It tells you the node did not answer in time. The node may be alive and still processing your request, which is why fencing tokens and epochs exist (chapter 10).
• "Comparing wall-clock timestamps across nodes is fine if NTP is running." NTP skew is typically milliseconds and can be seconds after a leap second or a VM migration. Use logical or hybrid clocks, or bound uncertainty explicitly like TrueTime.
• "A network partition is rare, so I can ignore it." Partitions include asymmetric ones (A can reach B but not the reverse), long GC pauses that look like partitions, and misconfigured firewalls. Every cloud provider has public post-mortems involving them.
• "Retrying faster recovers faster." Retries are load. Without backoff and jitter they turn a hiccup into an outage.

Key terms

Term	Meaning
Fallacies of distributed computing	Deutsch and Gosling's eight false assumptions about networks (reliable, zero latency, infinite bandwidth, ...)
Backpressure	A consumer signalling producers to slow down so queues stay bounded
Network partition	Two groups of nodes that can communicate internally but not with each other
Exponential backoff with jitter	Retry delays that double each attempt and are randomised to avoid synchronised retry storms
Fair-loss link	A link that may lose and finitely duplicate messages but delivers a message sent infinitely often and never fabricates one
Stubborn link	A link that retransmits each message forever, guaranteeing eventual delivery between correct processes
Perfect link	A link with reliable delivery, no duplication and no creation, built from acknowledgements and deduplication
At-least-once / at-most-once / exactly-once	Delivery semantics: may duplicate, may lose, neither (achievable only as processing semantics with deduplication)
Two generals' problem	The impossibility of two parties reaching certain agreement over an unreliable channel
FLP impossibility	No deterministic consensus protocol guarantees termination in an asynchronous system with one crash fault
Synchronous / asynchronous / partially synchronous	Timing models with known bounds, no bounds, or bounds that hold eventually or are unknown
Crash-stop / crash-recovery	A process halts forever, or halts and resumes with stable storage intact
Byzantine fault	A process behaves arbitrarily, including maliciously; tolerance needs n >= 3f + 1

Further reading

• Database Internals, Chapter 8, and Part II introduction.
• Cachin, Guerraoui, Rodrigues, Introduction to Reliable and Secure Distributed Programming (the source of the link and failure-model hierarchy).
• Fischer, Lynch, Paterson, "Impossibility of Distributed Consensus with One Faulty Process", JACM 1985: https://doi.org/10.1145/3149.214121
• Dwork, Lynch, Stockmeyer, "Consensus in the Presence of Partial Synchrony", JACM 1988.
• Chandra, Toueg, "Unreliable Failure Detectors for Reliable Distributed Systems", JACM 1996: https://doi.org/10.1145/226643.226647
• Lamport, Shostak, Pease, "The Byzantine Generals Problem", 1982: https://lamport.azurewebsites.net/pubs/byz.pdf
• Lamport, "Time, Clocks, and the Ordering of Events in a Distributed System", 1978: https://doi.org/10.1145/359545.359563
• Marc Brooker, "Exponential Backoff And Jitter", AWS Architecture Blog: https://aws.amazon.com/blogs/architecture/exponential-backoff-and-jitter/
• Fallacies of distributed computing: https://en.wikipedia.org/wiki/Fallacies_of_distributed_computing
• Confluent, "Exactly-once Semantics Are Possible: Here's How Kafka Does It": https://www.confluent.io/blog/exactly-once-semantics-are-possible-heres-how-apache-kafka-does-it/
• Kyle Kingsbury's distributed systems class notes: https://github.com/aphyr/distsys-class