Department of Computer Science Colloquium
Thursday, October 17, 2002, 4:15pm 
Upson Hall B17

Practical Byzantine Quorum Systems

Lorenzo Alvisi
University of Texas at Austin 

One approach to integrating fault-tolerance and security in distributed systems is to harden the mechanisms we use to build highly available services so they operate correctly even when faulty components behave in arbitrarily malicious ways. Byzantine Quorum Systems (BQSs) are an example of this approach. By hardening quorum systems, a well-known mechanism for building highly-available data repositories, they guarantee the consistency of replicated data even if a subset of the replicas, up to a given threshold, is compromised.
In this talk, I will discuss some issues of practical and theoretical interest that arise when trying to make BQSs a viable option for building real systems:
* I will present a non-blocking protocol that can reconfigure a BQS dynamically so that it operates efficiently in the absence of faults, increasing and decreasing the quorum size (and thus the tolerance) as faults appear and are dealt with, respectively.
* I will discuss protocols that use non-confirmable writes to reduce by as much as 33% the minimum number of replicas required to implement a BQS in an asynchronous systems with reliable communication channels.
* I will introduce lower bounds on the number of replicas required to implement BQSs using confirmable and non-confirmable writes, as well as protocols that match these bounds.