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.