Fault-scalable Byzantine fault-tolerant services

TLDR

A fault‑scalable service can be configured to tolerate increasing numbers of faults without significant decreases in performance. The authors propose the Query/Update (Q/U) protocol to construct fault‑scalable Byzantine fault‑tolerant services. The Q/U protocol is an optimistic quorum‑based scheme that allows queries and updates to proceed without waiting for agreement, enabling fault‑scalability. Experiments show that the Q/U protocol delivers higher throughput and fault‑scalability than agreement‑based replicated state machines, with only a 36 % performance drop when tolerating five Byzantine faults compared to an 83 % drop for the replicated state machine.

Abstract

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%.