Practical Byzantine Fault Tolerance

Download: pdf, ps, html.

“Practical Byzantine Fault Tolerance” by Miguel Castro and Barbara Liskov. In Third Symposium on Operating Systems Design and Implementation (OSDI), (New Orleans, Louisiana), Feb. 1999.

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.

Download: pdf, ps, html.

BibTeX entry:

@inproceedings{castro99practical,
   author = {Miguel Castro and Barbara Liskov},
   title = {Practical Byzantine Fault Tolerance},
   booktitle = {Third Symposium on Operating Systems Design and
	Implementation (OSDI)},
   publisher = {USENIX Association, Co-sponsored by IEEE TCOS and ACM SIGOPS},
   address = {New Orleans, Louisiana},
   month = feb,
   year = {1999}
}