Practical Byzantine Fault Tolerance
Miguel Castro and Barbara Liskov
MIT Laboratory for Computer Science,
545 Technology Square, Cambridge, MA 02139
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.
A PostScript version of this paper is available.
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.