Probabilistically Bounded Staleness for Practical Partial Quorums
Data store replication results in a fundamental trade-off between operation latency and data consistency. In this paper, the authors examine this trade-off in the context of quorum-replicated data stores. Under partial or non-strict quorum replication, a data store waits for responses from a subset of replicas before answering a query, without guaranteeing that read and write replica sets intersect. As deployed in practice, these configurations provide only basic eventual consistency guarantees, with no limit to the recency of data returned. However, anecdotally, partial quorums are often "Good enough" for practitioners given their latency benefits.