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