BFT - Practical Byzantine Fault Tolerance
The mechanism needs to make a synchrony assumption in order to provide liveness; otherwise it could be used to implement consensus in an asynchronous system, which is not possible. Liveness is guaranteed, i.e., clients eventually receive replies to their requests, provided at most floor((n-1)/3) replicas are faulty and delay(t) does not grow faster than t indefinitely. Here, delay(t) is the time between the moment t when a message is sent for the first time and the moment when it is received by its destination (assuming the sender keeps retransmitting the message until it is received). This is a rather weak synchrony assumption that is likely to be true in any real system provided network faults are eventually repaired, yet it enables the mechanism to circumvent the impossibility result.
In order to cope with Byzantine failure modes, a consensus-based system requires 3m+1 replicas in order to tolerate m independent faults. Various forms of diversity and replication can be used to ensure that faults are independent, depending on the fault hypothesis, but in the worst case, both software and hardware diversity is needed in order to cope with malicious faults.
A practical implementation of Byzantine Fault Tolerance that can be used in asynchronous environments like the Internet. The mechanism guarantees safety, but needs to make a weak synchrony assumption in order to guarantee liveness.
This paper describes a new replication algorithm that is able to tolerate Byzantine faults. We believe that Byzantine-fault-tolerant algorithms will be increasingly important in the future because malicious attacks and software errors are increasingly common and can cause faulty nodes to exhibit arbitrary behavior. Whereas previous algorithms assumed a synchronous system or were too slow to be used in practice, the algorithm described in this paper is practical: it works in asynchronous environments like the Internet and incorporates several important optimizations that improve the response time of previous algorithms by more than an order of magnitude. We implemented a Byzantine-fault-tolerant NFS service using our algorithm and measured its performance. The results show that our service is only 3% slower than a standard unreplicated NFS.