Implementing Fault-Tolerant Services Using the State Machine Approach: A Tutorial

PublishedACM Computing Surveys

It appeared in a journal, conference or book, which normally review work before accepting it. Even so, one study is never the final word.

Abstract

The state machine approach is a general method for implementing fault-tolerant services in distributed systems. This paper reviews the approach and describes protocols for two different failure models: Byzantine and fail stop. System reconfiguration techniques for removing faulty components and integrating repaired components are also discussed.

Research Analysis

Written by Kurz, not by the authors of the paper. The abstract above is the authors' own.

Last revised
Version
1.0

Overview

This tutorial appeared in ACM Computing Surveys in December 1990, when replication protocols were mostly described one by one. Schneider's point is that many of them are instances of one idea. Model the service as a state machine, keep a replica of it on each of several processors that fail independently, and make sure every replica receives and processes the same sequence of requests. Most of the protocols he discusses were not actually derived this way, but, as he puts it, viewing them as state machines helps explain how and why they work.

The paper sits between the theory and the systems that came after it. It leans on Time, Clocks, and the Ordering of Events, where Lamport first described the approach, and it cites the FLP result to explain why some failure environments have no workable solution. It also mentions the Paxon Synod protocol as something that can be understood in these terms, which is the algorithm of The Part-Time Parliament and, later, Paxos Made Simple.

Worth knowing first: logical clocks, the difference between Byzantine failures (arbitrary, possibly colluding behavior) and fail-stop failures (the component stops and others can detect it), and the idea of a synchronous system with bounds on message delay.

Contribution

  • A precise notion of a state machine. State variables plus commands, each a deterministic and atomic program. The semantic characterization is that outputs depend only on the sequence of requests processed, not on time or other activity. A sensor-polling loop inside the machine would violate that, so the loop moves into a client.
  • Replica Coordination split into Agreement and Order. Every nonfaulty replica receives every request (Agreement) and processes them in the same relative order (Order). The split follows the existing separation between clients and replicas.
  • Replica counts. With Byzantine failures, tolerating t faults takes at least 2t + 1 replicas and a majority vote on the outputs. With fail-stop failures, t + 1 replicas suffice and any output can be used.
  • Order through unique identifiers and stability. A request is stable at a replica once no request with a lower identifier can still arrive, and a replica processes the stable request with the smallest identifier. The paper gives three ways to assign identifiers: logical clocks, synchronized real-time clocks, and identifiers generated by the replicas themselves.
  • Relaxations. Agreement can be weakened for read-only requests under fail-stop, and Order can be dropped for requests that commute.
  • Faulty outputs and clients. Replicated output devices and voters, client-side voting, replicated clients, defensive command design, and requests carried by the passage of time.
  • Reconfiguration. A Combining Condition on the number of faulty processors, and protocols to remove faulty and integrate repaired elements, including a new replica.

Methodology

This is a tutorial, so the method is exposition and proof by argument. Small state machines written in a guarded-command notation (a memory, a mutual exclusion resource allocator called mutex, and an election called tally) carry the examples. Each protocol is stated as a requirement plus an implementation, and its correctness is argued informally, for instance the argument that once a request passes the stability test no request with a smaller identifier can arrive.

Failures are handled in two representative models, Byzantine and fail-stop, rather than in general. The reasoning is also organized by what is being replicated: the state machine itself (Section 3), output devices (Section 4), clients (Section 5), and the configuration (Section 7). There is no implementation and no measurement in the paper. For performance it points to experiments by Pittelli and Garcia-Molina with stability tests on SUN workstations.

Findings

These are the results the paper establishes, in its own terms.

  • Two conditions give a t fault-tolerant machine. If every nonfaulty replica starts in the same state and executes the same requests in the same order, all produce the same output, and combining the ensemble's outputs masks up to t failures.
  • Logical clocks work only with fail-stop and a stability test. The test requires every client to make periodic, possibly null, requests, and relies on FIFO channels and on the Failure Detection Assumption. With Byzantine failures and unbounded delays the paper says there is no point in a stability test, because the FLP result rules out deterministic agreement in that setting.
  • Real-time clocks give two tests. One waits until the local clock passes the request identifier plus a delay bound, so the machine lags its clients by that bound. The other waits for a request with a larger identifier from every client. The two can be combined so the lag appears only when faulty processors or the network force it.
  • Replica-generated identifiers need no all-to-all communication. Each replica proposes a candidate identifier, the largest candidate becomes the identifier, and the paper proves the protocol satisfies its constraints. An optimization of it is the basis of the ABCAST protocol in the ISIS Toolkit.
  • Unbounded faults over time are possible. If faulty replicas are removed and repaired ones added fast enough, the Combining Condition can hold forever, so the total number of faults tolerated is unbounded.
  • Joining a replica is subtle. The donor replica must send its state and then relay requests for a time, which forces a modified stability test during restart.

Critical Analysis

The paper is a clear and well-organized synthesis, and its Agreement and Order vocabulary is still the standard way to talk about replication. The limits below are mostly consequences of when it was written. The comparison with later work is an editorial reading, not something the paper claims.

  • The fail-stop model hides the hard part. Using t + 1 replicas depends on the Failure Detection Assumption, which gives perfect and timely failure detection. In an asynchronous network a slow process cannot be told apart from a crashed one, so practical protocols such as Paxos and Raft use majority quorums of 2t + 1 replicas to tolerate t crashes.
  • Order is described, not solved under asynchrony. The paper explains why the case of arbitrary delays with Byzantine failures is hopeless, but it offers no protocol that stays safe when timing assumptions break and live when they hold. That is the contribution of the consensus protocols.
  • Byzantine numbers depend on synchrony. The 2t + 1 ensemble comes with an ordering (Section 3.2.2) that assumes synchronized real-time clocks and bounded message delays, as the paper states. Byzantine protocols for partially synchronous networks, as far as I know, use larger ensembles, so these figures should not be carried over to such systems.
  • No evaluation. Costs are discussed qualitatively, and the ordering protocols assume that a client's requests, or at least null requests, arrive regularly.
  • Crash recovery is thin. Repaired elements are re-integrated from a running replica, with no treatment of durable logs or snapshots, which real systems spend most of their effort on.

Further Research

  • Consensus protocols that implement Order in partially synchronous networks without perfect failure detection, such as Paxos and Raft, with the log as the unit of agreement.
  • Reconfiguration as part of the replicated log itself, instead of a separate configurator and failure detector.
  • Cheaper handling of read-only requests while keeping linearizability, for example Bodega and its leases, which revisits the relaxation of Agreement for reads.
  • Byzantine fault-tolerant replication for asynchronous or partially synchronous settings, and its cost compared with crash-only protocols.
  • Exploiting commutativity to skip ordering, which the paper shows with the tally example.

Full text

Loading the paper…

Discussion · 0

No posts yet. Be the first to start the discussion.