1997/01/01 by Dahlia Malkhi, Michael K. Reiter · 2 citations
Computer Science · #Advanced Data Storage Technologies #Distributed systems and fault tolerance #Security and Verification in Computing
paper · doi:10.1145/258533.258650
openalex publication_date 1997/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
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 p n ), thus meeting the lower bound on load for benignly faulttolerant quorum systems. We explore several variations of our quorum systems and extend our constructions to cope with arbitrary client failures. 1 Introduction A well known way to enhance the availability and efficiency of replicated data is by using quorums . A quorum system for a universe of data servers is a collection o...