Quorum systems are well-known tools for ensuring the consistency and availability
of replicated data despite the benign failure of data repositories. In this paper we
consider the arbitrary (Byzantine) failure of data repositories and present the first
study of quorum system requirements and constructions that ensure data availability and
consistency despite these failures. We also consider the load associated with our quorum
systems, i.e., the minimal access probability of the busiest server. For services
subject to arbitrary failures, we demonstrate quorum systems over n servers with a load
of O(1/sqrt(n)), thus meeting the lower bound on load for benignly fault-tolerant
quorum systems. We explore several variations of our quorum systems and extend our
constructions to cope with arbitrary client failures.