DIMACS TR: 97-10
Optimal Byzantine Quorum Systems
Authors: Dahlia Malkhi, Michael Reiter and Avishai Wool
ABSTRACT
Replicated services accessed via quorums enable each access to
be performed at only a subset (quorum) of the servers, and achieve
consistency across accesses by requiring any two quorums to
intersect. Recently, b-masking quorum systems, whose
intersections contain at least 2b+1 servers, have been proposed to
construct replicated services tolerant of b arbitrary (Byzantine)
server failures. In this paper we consider a hybrid fault model
allowing benign failures in addition to the Byzantine ones. We
present four novel constructions for b-masking quorum systems,
each of which has optimal load (the probability of access of
the busiest server) or optimal availability (probability of some
quorum surviving failures). To show optimality we also prove lower
bounds on the load and availability of any b-masking quorum system
in this model.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-10.ps.gz
DIMACS Home Page