Byzantine and Multi-writer K-Quorums

摘要

Single-writer κ-quorum protocols achieve high availability without incurring the risk of read operations returning arbitrarily stale values: in particular, they guarantee that, even in the presence of an adversarial scheduler, any read operation will return the value written by one of the last κ writes. In this paper, we expand our understanding of κ-quorums in two directions: first, we present a single-writer κ-quorum protocol that tolerates Byzantine server failures; second, we extend the single-writer κ-quorum protocol to a multi-writer solution that applies to both the benign and Byzantine cases. For a system with m writers, we prove a lower bound of ((2m - 1)(κ- 1) + 1) on the staleness of any multi-writer protocol built over a single-writer κ-quorum system and propose a multi-writer protocol that provides an almost matching staleness bound ofrn((2m-1)(κ-1)+m).