Implementing Fault-Tolerant Services Using the State Machine Approach

A state machine consists of state variables, which encode its state, and commands, which transform its state. The execution of the command is atomic in respect to the other commands and modifies the state variables and produces some output.

Byzantine Failures - the component can exhibit arbitrary and malicious behaviour, perhaps evolving collusion with other faulty components. If a process is faulty, it can overwrite all memory locations, and destroy information. If several machines collude, the processes can write the same wrong result in memory.

Fail-stop Failures - In response to a failure, the component changes to a state that permits other processes to detect that.

When processors can experience Byzantine failures, an ensemble implementing a $t$ fault-tolerant state machine must have at least $2t+1$ replicas, and the output of the ensemble is the output produced by the majority of the replicas. This is because with $2t+1$ replicas, the majority of the outputs remain correct even after as many as $t$ failures.

In case of fail-stop failures, then it is only necessary $t+1$ replicas, because only correct outputs are produces by correct processes, and after $t$ failures there is still one process that produces the output.

To implement a fault-tolerant state machine it is necessary to ensure the following:

• Replica Coordination. All replicas receive and process the same sequence of requests. This can be decomposed into two requirements concerning dissemination of requests to replicas in an ensemble.
• Agreement. Every nonfaulty state machine replica receives every request.
• Order. Every nonfaulty state machine replica processes the requests it receives in the same relative order.

The Agreement is concerned to the client interaction with the state machine replicas, and the Order concerns with the behaviour of the state machine replica with respect to the requests. Sometimes, according to the use case, the implementation of the Agreement and Order can be relaxed.

The Agreement can be relaxed for read-only requests when fail-stop processors are being assumed. A request can only be sent to a single nonfaulty state machine replica. This is possible because the response from the replica is always guaranteed to be correct.

Another example of relaxation of the Order property is when 2 requests $r$ and $rʹ$ can commute in a state machine because the result will be always the same independently $r$ is processed before or after $rʹ$.

It just makes sense to guarantee the Order property if the Agreement property is also guaranteed.

The Agreement requirement is guaranteed if:

• IC1. All nonfaulty processors agree on the same value.
• IC2. If the transmitter is non faulty, then all nonfaulty processors use its value as the one on which they agree.

The Order of the requests can be guaranteed if the algorithm uses logical clocks or synchronized real-time clocks to timestamp requests.

Depending on whether the output of the state machine implemented by the ensemble is to be used within the system or outside the system, different architectures must be provided.

If the outputs of the state machine are used by external components, then that device is already a single component whose failure cannot be tolerated. The usual solution to this problem is to replicate the output device and voter. Each voter gets the output of each state machine replica, votes the result and produces a signal that drives one output device. E.g., a flap on an airplane wing might be designed so that when the $2t+1$ actuators that control it do not agree, the flap always moves in the direction of the majority (rather than twisting). So, each voter have sent the result to one actuator.

If output devices exhibit only fail-stop failures then it is only necessary to the output device get one result. In this case, it is assumed that the result that the output device receives is correct.

If the outputs of the state machine are used by the client, then the client itself can combine the outputs of state machine replicas in the ensemble. When Byzantine failures are possible, the client waits until it has received $t+1$ identical responses, each from a different replicas, and takes that as the response from the $t$ fault-tolerant state machine. When only fail-stop failures are possible, the client can proceed as soon as it has received a response.