2005/10/20 by Michael Abd-El-Malek, Gregory R. Ganger, Garth R. Goodson +2 · 4 citations
Computer Science · Psychology · #Age of Information Optimization #Algorithm #Byzantine fault tolerance #Cognitive Functions and Memory #Computer network #Computer science #Distributed computing #Distributed systems and fault tolerance #Fault tolerance #Operating system #Protocol (science) #Quantum Byzantine agreement #Scalability #Service (business) #State (computer science) #Throughput #Wireless
paper · doi:10.1145/1095809.1095817
crossref issued 2005/10/20 · crossref published 2005/10/20 · crossref published-online 2005/10/20 · crossref published-print 2005/10/20 · openalex publication_date 2005/10/20 · crossref created 2005/11/07 · crossref deposited 2025/06/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/19 · crossref indexed 2026/08/05
A fault-scalable service can be configured to tolerate increasing numbers of faults without significant decreases in performance. The Query/Update (Q/U) protocol is a new tool that enables construction of fault-scalable Byzantine fault-tolerant services. The optimistic quorum-based nature of the Q/U protocol allows it to provide better throughput and fault-scalability than replicated state machines using agreement-based protocols. A prototype service built using the Q/U protocol outperforms the same service built using a popular replicated state machine implementation at all system sizes in experiments that permit an optimistic execution. Moreover, the performance of the Q/U protocol decreases by only 36% as the number of Byzantine faults tolerated increases from one to five, whereas the performance of the replicated state machine decreases by 83%.