Probabilistically Bounded Staleness for Practical Partial Quorums

Summary: Proposes Probabilistically Bounded Staleness (PBS) to quantify staleness under partial quorums in Dynamo-like stores. Derives closed-form versioned staleness and real-time models; shows latency gains with practical freshness (tens of ms) despite non-intersecting replicas. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 10520
Venue: VLDB
Year: 2012
Pagerank: 8.3639933e-05
Overall Rank: 2,654 | 81.56%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 14 of 14 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,985	ACIDRain: Concurrency-Related Attacks on Database-Backed Web Applications	2017	SIGMOD	9.8619045e-05
2,008	Bolt-on Causal Consistency	2013	SIGMOD	9.8120677e-05
2,724	The Homeostasis Protocol: Avoiding Transaction Coordination Through Program Analysis	2015	SIGMOD	8.2300934e-05
3,272	Rethinking Eventual Consistency	2013	SIGMOD	7.290716e-05
3,517	Feral Concurrency Control: An Empirical Investigation of Modern Application Integrity	2015	SIGMOD	7.0183022e-05
3,654	Implementation of Cluster-wide Logical Clock and Causal Consistency in MongoDB	2019	SIGMOD	6.87251e-05
4,044	Enabling the Next Generation of Multi-Region Applications with CockroachDB	2022	SIGMOD	6.5030191e-05
6,357	Dissecting the Performance of Strongly-Consistent Replication Protocols	2019	SIGMOD	5.0921164e-05
6,437	PLANET: Making Progress with Commit Processing in Unpredictable Environments	2014	SIGMOD	5.0554119e-05
9,789	RALF: Accuracy-Aware Scheduling for Feature Store Maintenance	2024	VLDB	4.2786659e-05
11,338	Confidence Bounded Replica Currency Estimation	2022	SIGMOD	4.1905499e-05
11,811	Quaestor: Query Web Caching for Database-as-a-Service Providers	2017	VLDB	4.1905499e-05
12,101	DAX: A Widely Distributed Multi-tenant Storage Service for DBMS Hosting	2013	VLDB	4.1905499e-05
13,440	PBS at Work: Advancing Data Management with Consistency Metrics	2013	SIGMOD	-

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
1,213	Building on Quicksand	2009	CIDR	0.00013251295
1,311	Consistency Analysis in Bloom: a CALM and Collected Approach	2011	CIDR	0.00012650881
1,541	Data Consistency Properties and the Trade-offs in Commercial Cloud Storages: the Consumers’ Perspective	2011	CIDR	0.00011449679
1,771	Offering a Precision-Performance Tradeoff for Aggregation Queries over Replicated Data	2000	VLDB	0.00010606967
2,062	PIQL: Success-Tolerant Query Processing in the Cloud	2012	VLDB	9.654149e-05
4,946	The Tree Quorum Protocol: An Efficient Approach for Managing Replicated Data	1990	VLDB	5.8113399e-05
6,500	Resilient Logical Structures for Efficient Management of Replicated Data	1992	VLDB	5.0306915e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
795	Fast Algorithms for Maintaining Replica Consistency in Lazy Master Replicated Databases	1999	VLDB	0.00016560364
2,820	Low-Latency Multi-Datacenter Databases using Replicated Commit	2013	VLDB	8.0655916e-05
13,440	PBS at Work: Advancing Data Management with Consistency Metrics	2013	SIGMOD	-
3,272	Rethinking Eventual Consistency	2013	SIGMOD	7.290716e-05
12,982	Reducing Storage for Quorum Consensus Algorithms	1988	VLDB	4.1905499e-05
2,380	Improving Performance in Replicated Databases through Relaxed Coherency	1995	VLDB	8.928101e-05
5,402	Replication, Consistency, and Practicality: Are These Mutually Exclusive?	1998	SIGMOD	5.5253784e-05
12,913	A Tight Upper Bound on the Benefits of Replication and Consistency Control Protocols	1991	PODS	4.1905499e-05
11,338	Confidence Bounded Replica Currency Estimation	2022	SIGMOD	4.1905499e-05
6,357	Dissecting the Performance of Strongly-Consistent Replication Protocols	2019	SIGMOD	5.0921164e-05