Failure Models

Failure models specify which anomalies are permitted in proofs and designs. Saying a protocol “can tolerate 1 failure” only makes sense when combined with the failure type, persistence assumptions, communication conditions, and failure domains. Process exit, data disk loss, one-way packet loss, and node message forgery are not the same thing.

How Nodes Can Fail

Fail-stop, in strict usage, includes the stronger assumption that other nodes can reliably detect the stop, and should not always be treated as a synonym for crash-stop. A stopped process in an asynchronous network may be indistinguishable from an extremely slow one.

The pure crash-stop model does not need to discuss what a node saves after recovery, but this does not mean real services do not require persistence. A product that requires confirmed data to be retained after a power-off restart introduces additional storage and recovery requirements.

Crash-recovery: Forgetting a commitment is itself a protocol error

If a Raft node forgets who it voted for in the current term after restarting, it may vote again; if a Paxos acceptor forgets the Promise it has made, it may accept an old proposal it had previously committed to reject. Therefore, persistence saves not only user data but also the protocol history that constrains future behavior.

It is also necessary to distinguish between “data written to the OS cache” and “meeting post-crash persistence requirements.” The actual guarantees of disks, controllers, and file systems are part of the failure model. A new machine coming online with an old node ID and an empty data directory cannot be unconditionally treated as a normal recovery of the original node.

How one crash can give two candidates a majority

Consider three voters A, B, and C, with equally fresh logs. In term 7, A votes for itself, and B replies with approval to A, so A obtains the two votes of A+B. If B’s vote is written only to memory and B crashes after replying but before persisting, it may forget it voted for A upon recovery. Subsequently, C votes for itself in the same term, and B approves C, resulting in two election majorities: A+B and B+C.

The two majorities still intersect, but the problem is that the intersection node B did not retain state constraining its future behavior. Therefore, “majorities must intersect” must be paired with “intersecting members do not violate voting rules” to form a complete safety argument.

Below, we simplify the stable state into an immutable tuple. durable=False intentionally simulates an incorrect early reply; restarts recover only from the stable tuple. To focus on persistence order, all requests are assumed to pass the log freshness eligibility check, and the code does not implement a full RequestVote.

class Voter:
    def __init__(self):
        self.stable = (0, None)
        self.reboot()

    def reboot(self):
        self.term, self.voted_for = self.stable

    def request(self, term, candidate, durable=True):
        if term < self.term:
            return False
        if term > self.term:
            self.term, self.voted_for = term, None
        if self.voted_for not in (None, candidate):
            return False
        self.voted_for = candidate
        if durable:
            self.stable = (self.term, self.voted_for)
        return True

broken = Voter()
assert broken.request(7, "A", durable=False)  # A has already counted this vote in its majority
broken.reboot()
assert broken.request(7, "C")                # B incorrectly votes for another candidate

safe = Voter()
assert safe.request(7, "A")
safe.reboot()
assert not safe.request(7, "C")
assert safe.request(7, "A")                  # Duplicate requests can still reply with the same vote
assert safe.request(8, "C")                  # New term can choose again
safe.reboot()
assert not safe.request(7, "A")              # Old term is still rejected

Actual implementations must complete the protocol-required stable storage updates before sending responses that depend on this state. If persistence completes but the response is lost, retries will see the old decision; if the response has been sent but allows the decision to be lost, other nodes may continue acting on a commitment that no longer holds after recovery. The safety implications of these two crash positions differ. Raft Figure 2: Update persistent state before responding

Tuple assignment is used only to express recovery boundaries, not to verify filesystem fsync, atomic writes, or power-off behavior. Real failure tests must specify whether the process, kernel, or entire machine crashed, and which storage layers still retain data.

Byzantine Failures: Authentication Does Not Equal Honesty

An authenticated node may still claim value X to A and value Y to B. Signatures indicate who sent the message, but do not automatically ensure the sender adheres to the protocol. Implementation errors, memory corruption, or compromise can cause node behavior to exceed a simple crash model.

Classic PBFT tolerates f Byzantine faults with at least 3f+1 replicas under its asynchronous safety and eventual progress conditions. Intuitively, two quorums of size 2f+1 intersect in at least f+1 nodes out of 3f+1, at least one of which is honest; however, safety also relies on honest nodes adhering to the protocol’s voting and locking rules.

This is not a unified lower bound on the number of nodes across all models such as synchronous, authenticated, or trusted hardware. When comparing 2f+1 with 3f+1, assumptions must be kept clear. In non-Byzantine majority consensus, intersecting nodes are assumed to follow the protocol, whereas the Byzantine model must also prevent the intersection from consisting entirely of nodes that lie.

Why Intersecting on One Node Is Not Enough in the Byzantine Model

In a three-node set A, B, C, the intersection of two two-vote sets {A,B} and {A,C} is only A. If A can sign X for B and Y for C, both sides obtain signatures from two different identities; authentication does not make this intersection honest.

The classic 3f+1 layout uses larger intersections to offset up to f dishonest members. From set sizes:

|Q1 ∩ Q2| ≥ |Q1| + |Q2| − N = 2(2f+1) − (3f+1) = f+1.

Even if the intersection contains all f bad nodes, at least one honest member remains. The table below expands the formula to facilitate checking whether “replica count,” “evidence threshold,” and “fault budget” are using consistent metrics.

from itertools import combinations

assert (set("AB") & set("AC")) - {"A"} == set()
for f in (1, 2, 3):
    n, q = 3 * f + 1, 2 * f + 1
    quorums = [set(c) for c in combinations(range(n), q)]
    smallest = min(len(a & b) for a in quorums for b in quorums)
    assert smallest == f + 1
    assert smallest - f >= 1

This enumeration only checks set conditions, not the PBFT implementation or safety proof. A complete protocol also needs to distinguish phases, views, and sequence numbers, and specify when honest nodes vote, lock, and what evidence to inherit during leader changes. You cannot declare a commit based on any 2f+1 messages; stitching together signatures from different views or different log positions does not form valid evidence for a single decision. PBFT Service Guarantees and Model

Can every node in the intersection be faulty?

Distinguish the actual overlap of two selected sets from the overlap guaranteed by their sizes alone. Protocols need the latter because responders vary. Below N=7. Two sets of five guarantee three shared members; with at most two dishonest members, at least one shared member is honest.

$$h_{\min }=\max (0,|Q_1|+|Q_2|-N-f)$$

Network Partitions: Direction and Size Are Two Dimensions

Partitions can leave nodes running but unable to exchange necessary messages. Symmetric disconnection affects both directions, while asymmetric disconnection means one direction works and the other does not; this is not defined by “splitting evenly” vs. “isolating one node.”

In a fixed member set, two disjoint partitions cannot both contain a strict majority. The majority side in a 3+2 partition is not necessarily healthy immediately; it may need to re-elect or be affected by slow disks and overload. If split into 2+2+1, no side has a majority.

Split-brain usually refers to a situation where multiple actual writers exist for a service authority that should be unique. Legitimate multi-master systems allow concurrent writes and define conflict resolution; they should not be called protocol failures simply because they have multiple writers. Single-master systems should prevent stale writers from continuing to cause effects through quorum, term, or external fencing.

Time Models: Conditions for Guaranteeing Progress

Synchronous models assume known upper bounds on relevant processing and communication; asynchronous models do not provide such speed upper bounds; partial synchronous models allow obtaining sufficient timing constraints under certain eventual stability conditions. These are assumptions for protocol reasoning, not simply calling “data center LAN” synchronous and “public internet” asynchronous.

FLP shows that in a fully asynchronous model allowing one process crash, deterministic consensus cannot guarantee that all allowed executions terminate. It does not say consensus cannot achieve safety, nor does it say Raft or Paxos cannot work in stable real-world networks. Engineering protocols typically preserve safety rules and pursue progress under available quorum, eventual stable communication, randomization, or failure detection assumptions. Gilbert and Lynch on Impossibility Results

Timeouts Are Evidence, Not Proof of Node Death

A response not arriving by the deadline may come from peer failure, network congestion, local scheduling pauses, or reply loss. If the request has already taken effect on the peer, retrying after a timeout may cause duplicate execution. Failure detection, business retries, and takeover authorization need to be designed separately.

Timeouts that are too short amplify long-tail latency into retries and elections, further increasing load; timeouts that are too long delay recovery. They should be set based on end-to-end latency distributions, pauses, acceptable false positives, and recovery goals, with retries limited during overload. Statistical values like P99 reflect observed samples, not hard upper bounds for future latency.

φ-accrual detectors convert heartbeat intervals into degrees of suspicion, helping express continuous evidence; they still do not provide perfect failure determination. For specific reasoning, see Failure Detection.

Correlated Failures: Replica Count Cannot Replace Failure Domains

If three machines share the same power supply, switch, or have the same software defect, they may fail simultaneously. Distributing replicas across different failure domains can reduce certain correlated risks, but cannot eliminate common failures caused by public control planes, certificate expiration, or erroneous releases.

Backup and replication are also different: accidental deletion may be correctly replicated to all replicas. For goals requiring historical data recovery, backup, retention, and recovery verification must be defined separately, rather than using “three replicas” to replace all data protection requirements.

Design and Verification Checklist

1. What data is allowed to be lost after a successful write, and which node or storage failures are tolerated?
2. What protocol state is preserved on restart, and how do nodes with lost disks rejoin?
3. Does the network model consider one-way failures, latency, duplication, and disconnection recovery?
4. Which operations wait, reject, or allow reading old state when no quorum is available?
5. How do old processes, upon recovery, actually reject expired permissions?
6. Do safety checks cover anomalous executions, and are there clear prerequisites for recovery progress?

These questions can be directly translated into failure injection scenarios: crashing before/after responses, power loss after persistence, recovering after isolating the old leader, delaying and duplicating requests, and node restarts during membership changes. Expected results should be written as invariants and recovery conditions, not just checking “the service came up at the end.”

References

• Perspectives on the CAP Theorem: Safety, liveness, and system assumptions.
• The Raft Paper: Non-Byzantine replication and recovery.
• Practical Byzantine Fault Tolerance: Classic PBFT model and protocol.

Keywords: crash-stop, crash-recovery, fail-stop, Byzantine, partition, partial synchrony, FLP, safety, liveness