Proactive Recovery in a Byzantine-Fault-Tolerant System

Download: pdf, ps, html.

“Proactive Recovery in a Byzantine-Fault-Tolerant System” by Miguel Castro and Barbara Liskov. In Fourth Symposium on Operating Systems Design and Implementation (OSDI), (San Diego, USA), Oct. 2000.


This paper describes an asynchronous state-machine replication system that tolerates Byzantine faults, which can be caused by malicious attacks or software errors. Our system is the first to recover Byzantine-faulty replicas proactively and it performs well because it uses symmetric rather than public-key cryptography for authentication. The recovery mechanism allows us to tolerate any number of faults over the lifetime of the system provided fewer than 1/3 of the replicas become faulty within a window of vulnerability that is small under normal conditions. The window may increase under a denial-of-service attack but we can detect and respond to such attacks. The paper presents results of experiments showing that overall performance is good and that even a small window of vulnerability has little impact on service latency.

Download: pdf, ps, html.

BibTeX entry:

   author = {Miguel Castro and Barbara Liskov},
   title = {Proactive Recovery in a Byzantine-Fault-Tolerant System},
   booktitle = {Fourth Symposium on Operating Systems Design and
	Implementation (OSDI)},
   address = {San Diego, USA},
   month = oct,
   year = {2000}

Also see all authors, all publications by date, and all publications by topic.

Programming Methodology Group