BFT can be used to build replicated systems that work correctly and remain available even when some of their replicas behave arbitrarily due to malicious attacks, software errors, or hardware failures. Whereas previous Byzantine-fault-tolerant replication techniques relied on unrealistic assumptions or were too slow to be used in practice, BFT can be used to build practical systems: it works in asynchronous environments like the Internet; it uses bounded storage; and it incorporates several important optimizations that improve the response time over previous techniques by more than an order of magnitude. BFT is also the first to recover Byzantine-faulty replicas proactively. As a result, it can tolerate any number of faults over the lifetime of the system provided less than 1/3 of the replicas become faulty within a small window of vulnerability.

This talk describes the algorithms used by BFT and the implementation of BFT and BFS -- a Byzantine-fault-tolerant NFS service built using BFT. The talk also presents results from a performance evaluation of BFT and BFS. Preliminary results show that BFS is only 3% slower than a standard unreplicated NFS when running the Andrew benchmark.