Practical Byzantine Fault Tolerance

Miguel Castro and Barbara Liskov

MIT Laboratory for Computer Science,
545 Technology Square, Cambridge, MA 02139
{castro,liskov}@lcs.mit.edu

 

Abstract:

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.

This paper and the technical memos it references are also available in PostScript or PDF:

Contents:


Published in the Proceedings of the Third Symposium on Operating Systems Design and Implementation, New Orleans, USA, February 1999.

This research was supported in part by DARPA under contract DABT63-95-C-005,  monitored by Army Fort Huachuca, and under contract F30602-98-1-0237, monitored by the Air Force Research Laboratory, and in part by NEC.  Miguel Castro was partially supported by a PRAXIS XXI fellowship.