BYZANTINE QUORUM SYSTEMS

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