Every protocol studied so far assumed that processes and channels are reliable. That assumption is now dropped: processes may crash, channels may lose packets, and the system must keep working anyway. This chapter is about tolerating partial failure, which is the defining challenge of a distributed system. We first fix the vocabulary (dependability, faults, failure modes, redundancy), then walk through what can go wrong in the simplest possible system, a single client and a single server, and progressively scale up to reliable group communication and, finally, to recovery: how a process that has crashed is brought back to a consistent state.

Reaching internal agreement inside a group (the consensus problem, FloodSet, the Byzantine generals, commit protocols, Raft) is a topic in its own right and is deferred to the next chapter, Agreement. Here the group only needs to communicate reliably, not to decide.

1. Why Be Fault Tolerant? Dependability#

A dependable system is one we can rely on: it operates as expected even in unforeseen situations. Dependability is not a single property but a bundle of four.

Availability means the system is ready to use whenever we need it: when we look for it, we find it running. Reliability means the system runs continuously for a long time without interruption.

Safety means that even under the worst unforeseen conditions the system never puts us in a harmful situation. A safe word processor may be unreliable or unavailable (it crashes when the power is cut), but it never loses our data, because it saves continuously. It can fail, but it fails gracefully. Maintainability means the system is easy to modify. This is an internal property, but it strongly influences the other three: if we can easily change the system, we can correct the situations that make it crash, hang, or lose data.

2. Faults, Errors, and Failures#

These three terms are distinct and form a causal chain.

• A fault is the root cause: a programmer writing incorrect code, or a user forgetting to charge a battery.
• An error is the bad internal state the fault triggers: a segmentation fault caused by a dangling pointer, or a battery running flat.
• A failure is the observable outcome: the process crashes and stops providing its service.

Testing puts failures in evidence (it finds inputs that make the system fail), but the goal is always to identify and fix the underlying fault, not just to observe its symptom.

Some faults are under our control (a programmer’s mistake, a battery we can keep charged); others are not (a power cut, a severed cable). In a centralised system an uncontrollable hardware fault is equivalent to a total crash: there is a single machine, and nothing can be done. In a distributed system such a fault typically affects only part of the runtime. We do not want the failure of a single disk in a data centre to bring down the whole system. Tolerating partial failure is exactly the core problem of distributed fault tolerance.

3. Classifying Failures#

3.1 By duration#

Type	Description
Transient	Occurs once and does not recur, or recurs very rarely. Generally not a serious problem.
Permanent	Persists until explicitly corrected (a crashed disk). It will not fix itself, but it is diagnosable and repairable.
Intermittent	Appears and disappears unpredictably (a flaky Wi-Fi link). The hardest to diagnose.

Intermittent faults are the most problematic: the system crashes, you re-run it, and this time the fault does not reappear, so pinning down the root cause becomes very difficult.

3.2 By failure mode#

Omission failures occur when a component fails to perform an expected action.

• Process omission: the process stops executing (crashes). Crashes are sub-classified by how detectable they are: fail-stop (reliably detectable by others), fail-silent (undetectable, the process simply goes quiet), and fail-safe (produces a wrong but easily recognisable output).
• Channel omission: packets are dropped, further distinguished into send, channel, or receive omission depending on where the loss occurs.

Byzantine (arbitrary) failures occur when a component keeps operating but produces incorrect results: a process executes the wrong program (omitting steps or inventing new ones), or a channel delivers a packet whose contents have been corrupted.

Timing failures exist only in a synchronous system: one of the assumed bounds is violated, for example a packet arrives later than the maximum assumed latency. Since almost every algorithm we study assumes synchrony, timing failures are worth naming.

In practice:

• Channels typically suffer Byzantine failures (corruption), but these are cheaply converted into omission failures with a CRC or other checksum: a corrupted packet is detected and simply discarded, which turns “wrong packet” into “missing packet”. Checksums are therefore part of every serious channel protocol.
• Processes typically suffer omission failures (crashes). A Byzantine process is rare and is usually the result of a security attack (someone took control of the process and changed its code) rather than a spontaneous fault. There is no process-level equivalent of the CRC, since in general we cannot check that a computed result is the expected one.

4. Masking Failures with Redundancy#

The general tool for tolerating faults is redundancy, in three flavours.

Information redundancy adds redundant data so errors can be detected and corrected. A Hamming code in a packet can not only detect a flipped bit but reconstruct the original, with no retransmission.

Time redundancy detects an error and retries: send a packet, notice the missing acknowledgement, resend. This works well for transient and intermittent faults.

Physical redundancy deploys multiple copies (replicas) of a component so that if one fails the others continue. This is the most common strategy in distributed systems, and the oldest: biology got there first. Examples include RAID disk mirroring and process replication.

The classic hardware pattern is Triple Modular Redundancy (TMR): each sub-module is triplicated and its outputs pass through a majority voter, so a single faulty sub-module is silently outvoted.

4.1 How much redundancy? Crash versus Byzantine#

The degree of replication needed depends on the type of failure being tolerated. Suppose we want an external client to obtain a correct answer from a replicated component.

• Crash / omission failures. Two disks halve the probability of total loss; if one crashes, the other is used. In general, tolerating $k$ crashes needs $k+1$ replicas.
• Byzantine failures. Two replicas are insufficient: if one returns a wrong value you cannot tell which of the two is correct. With three, a majority vote isolates the liar. In general, tolerating $k$ Byzantine faults needs $2k+1$ replicas, so that the $k+1$ correct replicas always outvote the $k$ faulty ones.

Byzantine faults are therefore far more expensive to tolerate than crashes. This distinction ($k+1$ vs $2k+1$) returns, in a sharper form, when the group must reach an internal decision rather than answer an outside client, which is the subject of the Agreement chapter.

5. Reliable Client-Server Communication#

To see how much can go wrong in practice, take the simplest possible distributed system: one client and one server exchanging messages.

5.1 Reliable point-to-point communication and TCP#

The foundation is reliable point-to-point delivery, usually provided by TCP. TCP masks channel omission with acknowledgements and retransmission (time redundancy), but with important caveats.

• TCP is optimised for loss due to congestion, the common case on wired networks, where its exponential backoff (waiting progressively longer before retransmitting) makes sense.
• On wireless links, packets are more often lost to interference or corruption than to congestion. There, retransmitting immediately would beat waiting longer and longer.
• TCP cannot cope with a permanent partition (a severed cable): the sender waits indefinitely, unable to distinguish a very slow reply from a dead connection.

In short, TCP solves the vast majority of channel-level problems, but completely masking every failure is impossible: in some situations TCP gives up and raises an exception to the application.

5.2 The RPC illusion and its failure modes#

RPC aims to give the caller the illusion of a local procedure call: transparent, reliable, executed exactly once. A local call fails only if the whole machine crashes; a remote call has many more failure modes.

1. The server cannot be located at the outset.
2. The request is lost before reaching the server.
3. The server crashes during execution.
4. The reply is lost after the server has finished.
5. The client crashes after sending the request.

Case 1 can be handled by raising an exception or redirecting to another server. The rest are harder, and the fundamental obstacle is that the client cannot tell them apart: if no reply arrives, it does not know whether the request was lost, the server crashed before executing, the server crashed after executing, or the reply was lost.

5.3 Delivery semantics: at-most-once, at-least-once, exactly-once#

Consider a concrete print server: the client sends a document, the server prints it and returns a confirmation. The channel is reliable (TCP, no partitions). The only source of failure is the server crashing at an unpredictable point: before, during, or after printing.

Two things are under our control:

• Server strategy: send the confirmation message M before printing, or after printing (P).
• Client strategy: always reissue, never reissue, reissue only if the confirmation was received, or reissue only if it was not.

Enumerating every client strategy against both server strategies and every crash timing (assuming a single crash) gives the following. Outcomes are OK (printed once), DUP (printed twice), ZERO (never printed); C marks the crash point.

(The first three columns are the M then P server strategy, the last three P then M.) No row is “OK” across all six crash timings: every strategy risks a duplicate or a missing print somewhere.

Semantics	How to obtain it	Trade-off
At-most-once	Client sends once, never retries.	The document may never be printed.
At-least-once	Server confirms after printing; client retries until confirmed.	The document may be printed more than once.
Exactly-once	Cannot be guaranteed.	See below.

A partial fix for duplicates is to attach a unique ID to each request, keep a history of processed IDs on the server, and discard (only re-acknowledging) any request already seen. This gives exactly-once in practice, but it needs, in principle, unbounded memory for the history (a delayed request could arrive arbitrarily late) and therefore assumptions on maximum traffic and delay to bound that memory. If those assumptions are violated (a timing failure), a duplicate may still slip through.

5.4 Lost replies and idempotency#

When the reply is lost, the client faces the same dilemma and the same risk of a duplicate on retry. The practical escape is to make operations idempotent: executing the request several times has the same effect as executing it once. This is automatic for stateless servers: “what is $5+3$?” always returns $8$, however many times it is asked. With idempotent operations, at-least-once is enough, since duplicate executions are harmless. This is a major argument for stateless, functional server design.

5.5 Client crashes: orphan computations#

A client crash seems harmless but can leave an orphan on the server. If the client’s request spawned a server thread, that thread may block indefinitely waiting to confirm delivery of its reply (especially over TCP) after the client has vanished.

• Extermination. The client logs every outgoing RPC. On restart it reads the log, finds the calls that never completed, and explicitly asks the servers to kill the corresponding orphans. Costly (every call is logged) and awkward with grand-orphans (orphans that themselves spawned further remote work) and with partitions that hide orphans from the client.
• Reincarnation. Each request carries an epoch number. On restart the client broadcasts a new epoch; servers kill any thread from a previous epoch of that client. No per-server bookkeeping is needed, grand-orphans are caught, and any stray reply carrying an obsolete epoch is simply discarded.
• Gentle reincarnation. On restart the client first tries to resume the orphaned computation; it kills it only if the owner cannot be located within a timeout.
• Expiration (most common). Each server-side computation has a time-to-live: if it cannot contact the client within that time, it terminates itself, needing no coordination on restart.

Killing an orphan thread is conceptually simple but practically involved: the mechanism to force-terminate a thread must exist, and any resources it opened (files, locks, connections) must be cleaned up.

6. Process Resilience and Groups#

The primary technique for surviving process crashes is replication: instead of a single server, run a group of processes in the same role, so that if one crashes the others carry on.

This is easy for stateless services (there is no state to keep in sync; a client is simply directed to any surviving member). For stateful services the replicas must stay synchronised: a state change at one replica must reach all others, so that a client redirected to a different replica after a crash finds the state it expects.

• A flat group treats all processes as peers and broadcasts state changes to everyone. No single point of failure, but coordination needs a distributed agreement protocol.
• A coordinated group routes updates through one coordinator: simpler, but the coordinator is a single point of failure, mitigated by leader election of a replacement when it crashes.

A further difficulty is membership management: knowing who is still alive. A crashed process cannot announce its own crash, and a network partition can make some processes unreachable without their having crashed, so a surviving partition may wrongly conclude the others are dead. Distinguishing a crashed process from a merely unreachable one is, in general, impossible.

6.1 How big must the group be?#

For an external client querying the group, the sizing mirrors section 4.1: tolerating $k$ crashes needs $k+1$ members (any survivor answers); tolerating $k$ Byzantine members needs $2k+1$ (contact all of them, take the majority vote). To tolerate one Byzantine member, query 3 and vote; to tolerate two, query 5.

7. Reliable Group Communication#

A stateful replicated group keeps its members in sync by exchanging messages, so it needs reliable multicast: a message sent to the group is reliably delivered to all its members. Assume for now that processes do not fail but the channel may lose packets.

7.1 The point-to-point approach and ACK implosion#

One option is a separate TCP connection from the sender to each member. It works, but on a shared broadcast medium (Ethernet, Wi-Fi) it wastefully retransmits the same message over the same wire. A better base is an underlying broadcast/multicast protocol (for example UDP multicast) with reliability added on top.

The naive way to add reliability, TCP-style positive acknowledgements, causes ACK implosion: when all goes well (the common case) the sender is flooded by an ACK from every receiver at once.

7.2 Scalable Reliable Multicast (SRM)#

The fix inverts the acknowledgement model: receivers stay silent and send a negative acknowledgement (NACK) only when they detect a missing packet. A gap in sequentially numbered packets (receiving 1, 2, 3, 5, 7) reveals that 4 and 6 were missed, possibly after a short wait for out-of-order delivery.

But if a packet is lost near the sender, every receiver misses it and they would all NACK at once, recreating the implosion. The solution is feedback suppression:

1. On detecting a loss, a receiver does not NACK immediately; it starts a random-delay timer.
2. When the timer expires it sends the NACK in broadcast (not just to the sender).
3. If another receiver’s NACK arrives first, it cancels its own timer: the loss has already been reported.

This keeps the number of NACKs per lost packet to one or two regardless of group size. The full protocol (sequential numbering, NACKs, random timers, broadcast NACKs) is Scalable Reliable Multicast (SRM), also called non-hierarchical feedback control. Its cost is that every member processes every NACK, even for packets it received correctly. SRM suits shared broadcast media precisely because it leverages the broadcast nature of the medium for both data and NACK suppression.

7.3 Hierarchical feedback control#

For very large groups even flat SRM generates too much traffic. The group is then organised into a hierarchy of subgroups: each subgroup uses SRM internally, a leader is elected per subgroup, and leaders communicate by unicast. The subgroups form a tree rooted at the sender; a leader requests missing messages from its parent and may drop a buffered message only once all its own receivers and all its child leaders have it. A crashed leader is re-elected. This trades coordination complexity for much lower load at scale.

8. Reliable Multicast with Faulty Processes: Virtual Synchrony#

Now let processes crash as well. Reliable delivery alone is no longer enough: we must keep the group consistent across membership changes. The building block is the distinction between receiving a message (the communication layer buffers it) and delivering it (handing it to the application only once some condition holds). That buffering is exactly what lets the middleware enforce ordering and atomicity.

8.1 Close synchrony versus virtual synchrony#

The ideal, close synchrony, would treat messages as sent instantaneously and reliably: a process crashes either before sending (nobody receives the message) or after sending (everyone receives it), and receivers always learn of a crash after any final message from the departing process. This is impossible, because both message propagation and crash notification take time.

The achievable approximation is virtual synchrony (Birman and Joseph, 1987).

Virtual synchrony is a weaker but implementable property. Informally, it requires:

• A message sent by process P is either delivered to all current group members, or to none of them.
• No process is informed that P has crashed before receiving all messages that P sent to the group.
• No process receives a message from P after being informed that P has crashed.

In other words, group membership changes (a process joining or leaving/crashing) act as epoch boundaries. All messages exchanged within an epoch are fully contained within that epoch, no message bleeds across the membership boundary. This applies symmetrically to processes joining the group: a process should not receive messages from a new member before being informed that the member joined.

Formally, a multicast sent during a particular group view (membership epoch) is delivered either to all members of that view or to none. Group membership changes delimit epochs, and messaging and membership changes appear in a consistent order across all processes. The same constraint applies to a joining member: no process should receive messages from a new member before being told it has joined. The two situations that stay unacceptable are partial delivery and receiving a crash notification before the message.

8.2 Message ordering#

Virtual synchrony says nothing about the order of messages within an epoch. That is an orthogonal choice with two dimensions. Causal strength ranges from unordered (no guarantee), through FIFO (messages from the same sender are delivered in send order), to causal (if sending A causally precedes sending B, everyone delivers A before B). Orthogonally, delivery may be non-totally ordered or totally ordered (all receivers deliver messages in the same order, even if that order differs from real time). The six combinations have standard names:

The Lamport-clock-based ordering from the Synchronization chapter is exactly a causal atomic multicast: it respects causal order (via timestamps) and is totally ordered (via a deterministic tie-break), delivering in the same order everywhere. Virtual synchrony is layered on top of whichever of the six guarantees is chosen.

8.3 An implementation: the ISIS protocol#

How ISIS enforces virtual synchrony (view-change flush)

The ISIS middleware (Birman et al., 1991) implements virtual synchrony for small replicated groups (typically 3 to 5 replicas) over reliable, FIFO point-to-point channels. The delicate moment is a sender crashing mid-broadcast, with some replicas having the last message and others not.

A message is stable once every current member has acknowledged it; until then it is unstable and must be retained. When a process detects a crash it triggers a view change:

1. it notifies all other members;
2. all members suspend delivery of new messages to the application (the epoch freezes);
3. every member sends all its unstable messages to all others (a flush);
4. once a member has flushed and received everyone’s flush, it signals ready;
5. when all are ready, the new view (without the crashed process) is installed and delivery resumes.

This guarantees that a message received by at least one surviving member before the crash is delivered to all survivors before the new view installs: no message is seen by some but not others across a membership boundary. ISIS assumes at most one crash during the flush; its per-message acknowledgement is expensive, which is why it targets small groups of replicated servers rather than large broadcast networks.

9. Recovery#

Fault tolerance so far kept the system running despite a crash. Recovery is the complementary question: when a crashed process comes back, how is it returned to a correct state?

9.1 Backward versus forward recovery#

Backward recovery returns to a previously known-good state. TCP retransmission is an example: not receiving an ACK, the sender conceptually steps back to “message not yet sent” and resends. So is reloading a periodically saved state from disk. Forward recovery repairs the erroneous state and continues: an error-correcting code reconstructs a corrupted packet and completes the reception without going back; a streaming player interpolates a dropped frame and plays on. For crashing processes in distributed systems, backward recovery dominates.

9.2 Checkpointing#

When a process crashes and restarts, the global state may be inconsistent. Checkpointing periodically saves a consistent global state to stable storage, so that on failure the system reloads it and resumes.

The right checkpoint is a consistent cut (in the sense of the distributed-snapshot algorithm from the Synchronization chapter): a state in which no process has recorded a message as received that the sender does not record as sent. Such a state may never have occurred at a single real instant, yet it is causally valid and therefore a legitimate restart point.

Coordinated checkpointing, built on the global snapshot protocol, guarantees consistency by construction but is expensive: every node coordinates and saves its state at a precise point, writing a potentially large amount of data. Despite the cost it is used in production; enabling fault tolerance in Apache Flink, for instance, activates coordinated checkpointing across all nodes, so that any crash restarts the job from the last checkpoint.

9.3 Logging#

As an alternative to saving the full state, each process can log every operation it performs and, on restart, replay the log to reconstruct its state up to the crash. Each log record is small (cheap per step), but recovery may replay a very long history. In practice the two are combined: periodic checkpoints plus a log of the operations between them. On failure the system reloads the last checkpoint and replays only the log since, keeping both the checkpoint cost and the replay cost manageable. Logging is developed further in section 11.

10. Uncoordinated Checkpointing and the Recovery Line#

10.1 Uncoordinated checkpointing and the domino effect#

Coordinated checkpointing is costly at runtime. Uncoordinated (independent) checkpointing is the cheap alternative: each process saves its own local state to disk independently, with no coordination and without saving channel contents. The price is paid at recovery.

Naively reloading each process’s most recent local checkpoint can yield a globally inconsistent state, for instance one in which P2 has “received” a message that P1 has no record of sending. Such a state is causally invalid. The system must therefore search backwards through the stored checkpoints for the most recent set that forms a consistent cut. In the worst case, rolling one process back orphans a message and forces another rollback, which orphans a further message, and so on, cascading all the way to the start.

Whether this happens depends on the checkpoint pattern: with luck the latest checkpoints already form a consistent cut; without it, no pair does and the whole history is lost. The goal is to find the recovery line, the most recent consistent cut among the stored checkpoints.

10.2 Tracking dependencies between checkpoints#

To find a consistent cut without a centralised snapshot protocol, each process labels its execution into intervals (the periods between consecutive checkpoints) and records inter-process dependencies cheaply:

• each interval gets a unique identifier (a per-process sequence number);
• when $P_i$ sends a message during its interval $x$, it tags the message with $x$;
• when $P_j$ receives that message during its own interval $y$, it records that its interval $y$ depends on interval $x$ of $P_i$.

These records are small (one per received message’s interval, not per message) and are saved with each local checkpoint. No global coordination happens during normal execution. When a failure occurs, all processes (including the recovered one) send their checkpoint history and dependency records to a central coordinator, which reconstructs the full interval-dependency graph and computes the recovery line.

10.3 The two algorithms#

Both algorithms turn interval dependencies into edges between checkpoints, then read off the recovery line. They must, and do, give the same answer.

Rollback-dependency graph (RDG).

1. Turn each interval dependency into a directed edge from the closing checkpoint of the sender’s interval to the closing checkpoint of the receiver’s interval (the checkpoint that ends each interval).
2. Add the implicit horizontal edges from each checkpoint to the next one of the same process (a checkpoint always depends on its predecessor).
3. Mark the failed states (the volatile state each crashed process was in at crash time, drawn at the right end).
4. Propagate the mark forward along all edges, message and horizontal alike; every checkpoint reached becomes marked.
5. The recovery line is, for each process, its most recent unmarked checkpoint.

Checkpoint-dependency graph (CDG).

1. Turn each interval dependency into an edge from the opening checkpoint of the sender’s interval (the one that starts it) to the closing checkpoint of the receiver’s interval. (This is the only difference from RDG: opening instead of closing on the sender side.) Keep the horizontal edges.
2. Remove the failed states outright.
3. Take a tentative recovery line = each process’s most recent surviving checkpoint.
4. If any checkpoint in the line can reach another checkpoint in the line (directly or transitively, following edges), remove the destination (arrival) checkpoint of that dependency, rolling that process back one step.
5. Repeat step 4 until no checkpoint in the line reaches another. The result is the recovery line.

10.4 A fully worked example#

The following is the standard example from the course slides, with P0 and P1 both failing. The interval-dependency graph (checkpoints as bars, messages as arrows) is on the left; the two graphs derived from it are below.

Both methods return the same recovery line: P0 and P1 roll back to $c_{0,2}$ and $c_{1,2}$ (their later checkpoints are tainted by the failures they exchanged messages from), while the non-failed P2 and P3 keep their last checkpoints. The lesson to carry into the exam is the mechanical procedure, not the specific values: mark the failures and propagate (RDG), or take the latest surviving set and prune arrivals until no in-line dependency remains (CDG).

10.5 Coordinated checkpointing revisited#

The alternative to all of the above is to coordinate the checkpoints so a consistent cut is guaranteed by construction. A simple coordinator-based scheme: the coordinator asks every process to checkpoint; each saves its state and stops sending new messages until cleared; when all have confirmed, the coordinator broadcasts clearance. Blocking sends during the window is essential, since it prevents an in-flight message from creating a dependency that crosses the checkpoint boundary. The downside is that the whole system blocks for the duration. The practical alternative is the non-blocking global snapshot (Chandy-Lamport) algorithm. Two refinements cut the cost further: an incremental snapshot checkpoints only the processes that actually matter for recovery, and communication-induced checkpointing piggybacks information on application messages so a receiver can decide whether it too must checkpoint to keep the global state consistent, blending uncoordinated runtime cost with coordinated consistency.

10.6 Coordinated versus uncoordinated: the trade-off#

Approach	Runtime cost	Recovery cost	Consistency
Coordinated (global snapshot)	High: all processes synchronise periodically	Low: the snapshot is always a valid consistent cut	Guaranteed by construction
Uncoordinated (independent + dependency tracking)	Low: each process acts alone; lightweight tagging	High: collect all data, build the graph, compute the line	Found only after failure; domino effect possible

Uncoordinated checkpointing is preferred when minimising runtime overhead matters and failures are rare; coordinated checkpointing when recovery must be fast and predictable.

11. Logging in Detail#

11.1 When logging works: piecewise determinism#

Logging assumes execution is piecewise deterministic: between the receipt of two messages a process behaves entirely deterministically, with no other influencing inputs (keystrokes, random numbers, interrupts). Under this assumption, replaying the same sequence of messages reproduces the same sequence of states.

11.2 Stable and unstable messages, orphans#

A message $M$ is stable if it can no longer be lost, that is, it has been written to stable storage (by the sender before sending, or by the receiver after receipt). An unstable $M$ lives only in volatile memory. For each unstable $M$ two sets are defined:

• Depend($M$): the processes whose state depends on the delivery of $M$, the direct receiver and anyone who later received a message causally dependent on $M$.
• Copy($M$): the processes that currently hold a copy of $M$ in volatile memory (not yet on stable storage).

A surviving process $Q$ is an orphan with respect to $M$ if $Q \in$ Depend($M$) but every process in Copy($M$) has crashed: $M$ can never be replayed, yet $Q$’s state assumes it was received. Replaying the log without $M$ would place $Q$ in a state it never actually passed through. To rule orphans out entirely it suffices to ensure that every process in Depend($M$) is also in Copy($M$): then $M$ is lost only if all dependent processes crashed too, so no survivor is ever orphaned.

11.3 Pessimistic versus optimistic logging#

In pessimistic logging the system guarantees no orphan is ever created. The rule: a process must stabilise a message before sending anything that causally depends on it. The simplest realisation is that the sender writes $M$ to its log just before transmitting, so $M$ is always on stable storage in Copy($M$). It is “pessimistic” because it assumes crashes are frequent and pays the I/O cost on every message; the reward is clean recovery, with no orphan detection needed.

In optimistic logging messages are logged asynchronously, cutting the per-message overhead but allowing orphans to appear on failure. Recovery must then compute the Depend and Copy sets, identify the orphans, and force them to roll back to a checkpoint before the dependency (or restart). The orphan-detection machinery is intricate and not detailed here.

11.4 Combining checkpointing and logging#

• Coordinated checkpoint + log. Take a coordinated checkpoint periodically and log operations between checkpoints; on failure reload the last checkpoint and replay the log. Log segments before a checkpoint can be safely discarded, since the checkpoint is a guaranteed consistent cut.
• Uncoordinated checkpoint + log. The same idea, but old log segments cannot be discarded after a local checkpoint, because that checkpoint may not lie on any valid recovery line: if the recovery algorithm later selects an earlier checkpoint, the full log back to it must still be available. Checkpoints and logs therefore accumulate until a failure forces a recovery.

12. Exam Questions#

The exercises below are drawn from past exams of this course. Worked solutions are unofficial (the instructor does not publish official ones); where the recovery-line method is used, it follows exactly the two-graph procedure of section 10.3 and the worked example of section 10.4.

12.1 Classifying failures#

Solution

Classify along two axes (section 3).

By duration. Transient: a cosmic-ray bit flip that never recurs. Permanent: a disk whose controller has died and stays dead until replaced. Intermittent: a loose network cable that drops packets only when the rack vibrates, so a re-run often “works”.

By mode. Omission (an expected action is skipped): a process crash (fail-stop if detectable, fail-silent if it just goes quiet, fail-safe if it emits a recognisably wrong output), or a channel dropping a packet (send / channel / receive omission). Byzantine / arbitrary (the component runs on but is wrong): a process executing corrupted code and returning $11$ for $3+5$, or a channel delivering a corrupted packet. Timing (synchronous systems only): a reply that arrives after the assumed maximum latency, violating an assumed bound.

In practice channels tend to fail Byzantine (corruption), but a CRC turns that into omission; processes tend to fail by omission (crash), Byzantine process faults being rare and usually the mark of an attack.

12.2 Reliable group communication, with and without faulty processes#

Solution

Reliable processes, lossy channel (section 7). Building on a broadcast/multicast medium, positive ACKs cause ACK implosion. Invert the scheme: receivers stay silent and send a NACK only on detecting a gap in the sequence numbers. To avoid a NACK storm when a packet is lost near the source, use feedback suppression: each receiver waits a random time and then sends its NACK in broadcast; hearing another’s NACK cancels its own timer, so only one or two NACKs are sent per loss. This is Scalable Reliable Multicast. For very large groups, organise a hierarchy of subgroups, each running SRM internally with an elected leader, leaders linked by unicast.

If processes may fail (section 8), reliable delivery is no longer enough: a sender may crash mid-broadcast, leaving some members with its last message and others without. We now require virtual synchrony: a message multicast in a given group view is delivered to all members of that view or to none, and no member is told of the crash before receiving the message. It is implemented (as in ISIS) with a view-change protocol: on detecting a crash, members freeze delivery and flush their unstable messages (received but not yet acknowledged by everyone) to all others, so any message that reached at least one survivor reaches them all before the new view (without the crashed process) is installed. Message ordering within a view (unordered / FIFO / causal, each optionally totally ordered) is an orthogonal guarantee layered underneath.

12.3 Scalable reliable multicast#

Solution

Problem. Deliver a message reliably to every member of a group, efficiently, over a medium that can lose packets. Assumptions. An underlying broadcast/multicast medium (Ethernet, Wi-Fi, UDP multicast) that is cheap to broadcast on but unreliable; non-faulty processes (SRM addresses channel loss, not process crashes); packets carry sequence numbers and the sender’s flow is roughly continuous, so a gap is detectable.

Mechanism (section 7.2). Avoid ACK implosion by using negative acknowledgements: a receiver detects a loss as a gap in the sequence numbers (after a short wait for reordering) and, instead of ACKing every packet, NACKs only the missing one. Avoid NACK implosion (many receivers missing the same packet lost near the source) with feedback suppression: on detecting a loss, start a random timer; on expiry, send the NACK in broadcast; if another receiver’s NACK is heard first, cancel the timer. So at most one or two NACKs per lost packet, independent of group size. The trade-off is that every member processes every NACK, and the retransmission is likewise multicast. This design is also called non-hierarchical feedback control; for very large groups it is nested inside a hierarchy of subgroups.

12.4 Computing the recovery line#

All three exams pose the identical exercise on different diagrams. The method is the two-graph procedure of section 10.3, demonstrated end to end on the worked example of section 10.4; the when/how part is answered by section 10.2 (each process tags messages with its interval id, receivers record cross-interval dependencies, and on a failure all of this is shipped to a central coordinator that builds the graph and runs the algorithm).

Solution (method and how to read the answer off each figure)

For every one of these six diagrams, proceed exactly as in the worked example of section 10.4.

Using the RDG (first diagram of each pair).

1. Redraw the checkpoints and add, for each tagged message, an edge from the closing checkpoint of the sender’s interval to the closing checkpoint of the receiver’s interval; add the horizontal per-process edges.
2. Mark the crash state(s) of the failed process(es) (17 Jan: P1 and P3; 14 Feb: P3; 6 Sep: P1) and propagate the mark forward along every edge.
3. Read off, per process, the most recent unmarked checkpoint.

Using the CDG (second diagram of each pair).

1. Same, but each message edge runs from the opening checkpoint of the sender’s interval to the closing checkpoint of the receiver’s interval; drop the crash states.
2. Take the latest surviving checkpoint of each process; while some checkpoint in the line reaches another in the line, delete the arrival checkpoint of that dependency; stop when none does.

Reading the outcome. The failed process itself falls back to its last saved checkpoint (its volatile post-crash state is gone). The rollback then cascades only to a process that received a message which the rollback turns into an orphan (a receive with no matching send), and such a process is pulled back one checkpoint at a time until the cut is consistent; every other process keeps its most recent checkpoint. Concretely, a survivor is forced to roll back when it received a message that a crashed process sent in its final (now-lost) interval, or, transitively, from an interval that itself had to be rolled back. Trace each message in the printed diagram against this rule to obtain the line; both graphs must agree.

Because these worked answers are unofficial and depend on reading the exact endpoints of hand-drawn arrows, the reliable takeaway is the procedure and the fact that both graphs yield the same line, which is what the exam grades. As the instructor put it, “do your best to show that you captured the point and made the reasoning.”

12.5 Where to find the rest of this paper’s questions#

The other questions on these papers belong to neighbouring chapters: the FloodSet algorithm (17 Jan Q4) and Raft (17 Jan Q7, 6 Sep Q7) are in Agreement; the consistency schedules (17 Jan Q5, 6 Sep Q5) in Replication and Consistency; clock synchronization (14 Feb Q2, 6 Sep Q2) in Synchronization; Chord (14 Feb Q6) in Peer-to-Peer; the dataflow model (14 Feb Q7, 6 Sep Q6) in Distributed Analytics.

13. Glossary#

Term	Meaning
Dependability	Umbrella property: availability, reliability, safety, maintainability.
Availability	Fraction of time the system is ready to use.
Reliability	Ability to run continuously for a long time without interruption.
Fault / Error / Failure	Root cause / bad internal state / observable loss of service.
Omission failure	A component skips an expected action (crash, dropped packet).
Byzantine failure	A component keeps running but produces wrong output.
TMR	Triple Modular Redundancy: triplicate a module and majority-vote its output.
At-most-once / at-least-once	Delivery semantics: never a duplicate (may lose) / never a loss (may duplicate).
Idempotent	An operation whose repeated execution has the same effect as one execution.
Orphan	A server computation left running by a crashed client; or, in logging, a survivor depending on a message that can no longer be replayed.
Reliable multicast	Deliver a message to all group members despite channel loss.
SRM	Scalable Reliable Multicast: NACK-based reliable multicast with random-timer feedback suppression.
Virtual synchrony	A message multicast in a group view reaches all members of that view or none, ordered consistently with membership changes.
Atomic multicast	Totally ordered reliable multicast.
Consistent cut / recovery line	A global state with no orphan message; the most recent such set of checkpoints.
Coordinated / uncoordinated checkpointing	Processes checkpoint together (consistent by construction) / independently (cheap, may domino).
Domino effect	A cascade of rollbacks that can discard the whole execution history.
RDG / CDG	Rollback- / Checkpoint-dependency graph: the two algorithms that compute the recovery line.
Piecewise determinism	Between two message receipts, a process behaves deterministically (the logging assumption).
Pessimistic / optimistic logging	Stabilise before dependent sends (no orphans) / log asynchronously (orphans possible, rolled back).

Compiled from G. Cugola's lectures (A.Y. 2025/26), slides + class transcriptions. Not official course material.