Byzantine and multi-writer k-quorums

Single-writer k-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 k writes. In this paper, we expand our understanding of k-quorums in two directions: first, we present a single-writer k-quorum protocol that tolerates Byzantine server failures; second, we extend the single-writer k-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)(k - 1) + 1) on the staleness of any multi-writer protocol built over a single-writer k-quorum system and propose a multi-writer protocol that provides an almost matching staleness bound of ((2m - 1)(k - 1) + m).