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: 10519
Venue: VLDB
Year: 2012
Pagerank: 8.3633807e-05
Overall Rank: 2,653 | 81.55%
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,994	ACIDRain: Concurrency-Related Attacks on Database-Backed Web Applications	2017	SIGMOD	9.842936e-05
2,016	Bolt-on Causal Consistency	2013	SIGMOD	9.789465e-05
2,723	The Homeostasis Protocol: Avoiding Transaction Coordination Through Program Analysis	2015	SIGMOD	8.2306728e-05
3,274	Rethinking Eventual Consistency	2013	SIGMOD	7.2906895e-05
3,512	Feral Concurrency Control: An Empirical Investigation of Modern Application Integrity	2015	SIGMOD	7.0250008e-05
3,672	Implementation of Cluster-wide Logical Clock and Causal Consistency in MongoDB	2019	SIGMOD	6.8558714e-05
4,153	Enabling the Next Generation of Multi-Region Applications with CockroachDB	2022	SIGMOD	6.4045807e-05
6,358	Dissecting the Performance of Strongly-Consistent Replication Protocols	2019	SIGMOD	5.0969837e-05
6,463	PLANET: Making Progress with Commit Processing in Unpredictable Environments	2014	SIGMOD	5.0533198e-05
9,786	RALF: Accuracy-Aware Scheduling for Feature Store Maintenance	2024	VLDB	4.2827012e-05
11,336	Confidence Bounded Replica Currency Estimation	2022	SIGMOD	4.1945683e-05
11,803	Quaestor: Query Web Caching for Database-as-a-Service Providers	2017	VLDB	4.1945683e-05
12,093	DAX: A Widely Distributed Multi-tenant Storage Service for DBMS Hosting	2013	VLDB	4.1945683e-05
13,427	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,210	Building on Quicksand	2009	CIDR	0.00013260838
1,310	Consistency Analysis in Bloom: a CALM and Collected Approach	2011	CIDR	0.00012658593
1,544	Data Consistency Properties and the Trade-offs in Commercial Cloud Storages: the Consumers’ Perspective	2011	CIDR	0.00011450594
1,773	Offering a Precision-Performance Tradeoff for Aggregation Queries over Replicated Data	2000	VLDB	0.00010609478
2,056	PIQL: Success-Tolerant Query Processing in the Cloud	2012	VLDB	9.6645763e-05
4,944	The Tree Quorum Protocol: An Efficient Approach for Managing Replicated Data	1990	VLDB	5.8158546e-05
6,505	Resilient Logical Structures for Efficient Management of Replicated Data	1992	VLDB	5.0346484e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
796	Fast Algorithms for Maintaining Replica Consistency in Lazy Master Replicated Databases	1999	VLDB	0.00016595815
2,834	Low-Latency Multi-Datacenter Databases using Replicated Commit	2013	VLDB	8.0458206e-05
13,427	PBS at Work: Advancing Data Management with Consistency Metrics	2013	SIGMOD	-
3,274	Rethinking Eventual Consistency	2013	SIGMOD	7.2906895e-05
12,972	Reducing Storage for Quorum Consensus Algorithms	1988	VLDB	4.1945683e-05
2,380	Improving Performance in Replicated Databases through Relaxed Coherency	1995	VLDB	8.9377051e-05
5,400	Replication, Consistency, and Practicality: Are These Mutually Exclusive?	1998	SIGMOD	5.5290116e-05
12,903	A Tight Upper Bound on the Benefits of Replication and Consistency Control Protocols	1991	PODS	4.1945683e-05
11,336	Confidence Bounded Replica Currency Estimation	2022	SIGMOD	4.1945683e-05
6,358	Dissecting the Performance of Strongly-Consistent Replication Protocols	2019	SIGMOD	5.0969837e-05