In computer science, state machine replication (SMR) or state machine approach is a general method for implementing a fault-tolerant service by replicating servers and coordinating client interactions with server replicas. The approach also provides a framework for understanding and designing replication management protocols.
Problem definition
Distributed service In terms of clients and services, each service comprises one or more servers and exports operations that clients invoke by making requests. Although using a single, centralized server is the simplest way to implement a service, the resulting service can only be as fault tolerant as the processor executing that server. If this level of fault tolerance is unacceptable, then multiple servers that fail independently can be used. Usually, replicas of a single server are executed on separate processors of a distributed system, and protocols are used to coordinate client interactions with these replicas.
State machine
For the subsequent discussion a State Machine will be defined as the following tuple of values (See also Mealy machine and Moore Machine):
A set of States A set of Inputs A set of Outputs A transition function (Input × State → State) An output function (Input × State → Output) A distinguished State called Start. A State Machine begins at the State labeled Start. Each Input received is passed through the transition and output function to produce a new State and an Output. The State is held stable until a new Input is received, while the Output is communicated to the appropriate receiver. This discussion requires a State Machine to be deterministic: multiple copies of the same State Machine begin in the Start state, and receiving the same Inputs in the same order will arrive at the same State having generated the same Outputs. Typically, systems based on State Machine Replication voluntarily restrict their implementations to use finite-state machines to simplify error recovery.
Fault Tolerance Determinism is an ideal characteristic for providing fault-tolerance. Intuitively, if multiple copies of a system exist, a fault in one would be noticeable as a difference in the State or Output from the others. The minimum number of copies needed for fault-tolerance is three; one which has a fault, and two others to whom we compare State and Output. Two copies are not enough as there is no way to tell which copy is the faulty one. A three-copy system can support at most one failure (after which it must repair or replace the faulty copy). If more than one of the copies were to fail, all three States and Outputs might differ, and there would be no way to choose which is the correct one. In general, a system which supports F failures must have 2F+1 copies (also called replicas). The extra copies are used as evidence to decide which of the copies are correct and which are faulty. Special cases can improve these bounds. All of this deduction pre-supposes that replicas are experiencing only random independent faults such as memory errors or hard-drive crash. Failures caused by replicas which attempt to lie, deceive, or collude can also be handled by the State Machine Approach, with isolated changes. Failed replicas are not required to stop; they may continue operating, including generating spurious or incorrect Outputs.
Special Case: Fail-Stop Theoretically, if a failed replica is guaranteed to stop without generating outputs, only F+1 replicas are required, and clients may accept the first output generated by the system. No existing systems achieve this limit, but it is often used when analyzing systems built on top of a fault-tolerant layer (Since the fault-tolerant layer provides fail-stop semantics to all layers above it).
Special Case: Byzantine Failure Faults where a replica sends different values in different directions (for instance, the correct Output to some of its fellow replicas and incorrect Outputs to others) are called Byzantine Failures. Byzantine failures may be random, spurious faults, or malicious, intelligent attacks. 2F+1 replicas, with non-cryptographic hashes suffices to survive all non-malicious Byzantine failures (with high probability). Malicious attacks require cryptographic primitives to achieve 2F+1 (using message signatures), or non-cryptographic techniques can be applied but the number of replicas must be increased to 3F+1.
The State Machine Approach The preceding intuitive discussion implies simple technique for implementing a fault-tolerant service in terms of a State Machine:
Place copies of the State Machine on multiple, independent servers. Receive client requests, interpreted as Inputs to the State Machine. Choose an ordering for the Inputs. Execute Inputs in the chosen order on each server. Respond to clients with the Output from the State Machine. Monitor replicas for differences in State or Output. The remainder of this article develops the details of this technique.
Step 1 and 2 are outside the scope of this article. Step 3 is the critical operation, see Ordering Inputs. Step 4 is covered by the State machine definition. Step 5, see Sending Outputs. Step 6, see Auditing and Failure Detection. The appendix contains discussion on typical extensions used in real-world systems such as Logging, Checkpoints, Reconfiguration, and State Transfer.
… excerpt ends here. Continue reading the full article.
