|
Abstract : |
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 certain limited types of services we exhibit a quorum system over n servers with a load of O( 1 p n), thus meeting the lower bound on load for benignly fault-tolerant quorum systems. For arbitrary services subject to arbitrary failures, we prove a lower bound of 1 2 on quorum system load, and demonstrate a novel construction meeting that bound. Finally, we extend our constructions to cope with arbitrary client failures., |
