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: 10707
Venue: VLDB
Year: 2012
Pagerank: 8.280143e-05
Overall Rank: 2,665 | 81.72%
DOI: 10.14778/2212351.2212357

Incoming Non-self Citations Over Time

Authors

1. Peter Bailis (University of California Berkeley)
2. Shivaram Venkataraman (University of California Berkeley)
3. Michael J. Franklin (University of California Berkeley)
4. Joseph M. Hellerstein (University of California Berkeley)
5. Ion Stoica (University of California Berkeley)

BibTeX Citation

@article{bailis_vldb12,
        title = {{Probabilistically Bounded Staleness for Practical Partial Quorums}},
        author = {Bailis, Peter and Venkataraman, Shivaram and Franklin, Michael J. and Hellerstein, Joseph M. and Stoica, Ion},
        journal = {PVLDB},
        series = {{VLDB} '12},
        volume = {5},
        number = {8},
        pages = {776--787},
        doi = {10.14778/2212351.2212357},
        url = {https://doi.org/10.14778/2212351.2212357},
        year = {2012}
}

Incoming Citations (Sorted by Pagerank)

Showing 14 of 14 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,850	Bolt-on Causal Consistency	2013	SIGMOD	9.6167827e-05
2,052	ACIDRain: Concurrency-Related Attacks on Database-Backed Web Applications	2017	SIGMOD	9.251901e-05
2,439	The Homeostasis Protocol: Avoiding Transaction Coordination Through Program Analysis	2015	SIGMOD	8.5785386e-05
3,186	Feral Concurrency Control: An Empirical Investigation of Modern Application Integrity	2015	SIGMOD	7.6559187e-05
3,328	Rethinking Eventual Consistency	2013	SIGMOD	7.5177778e-05
3,418	Implementation of Cluster-wide Logical Clock and Causal Consistency in MongoDB	2019	SIGMOD	7.429422e-05
3,683	Enabling the Next Generation of Multi-Region Applications with CockroachDB	2022	SIGMOD	7.2035148e-05
6,296	Dissecting the Performance of Strongly-Consistent Replication Protocols	2019	SIGMOD	5.922816e-05
6,477	PLANET: Making Progress with Commit Processing in Unpredictable Environments	2014	SIGMOD	5.8682525e-05
9,940	RALF: Accuracy-Aware Scheduling for Feature Store Maintenance	2024	VLDB	5.1924403e-05
11,535	Confidence Bounded Replica Currency Estimation	2022	SIGMOD	5.093636e-05
12,007	Quaestor: Query Web Caching for Database-as-a-Service Providers	2017	VLDB	5.093636e-05
12,290	DAX: A Widely Distributed Multi-tenant Storage Service for DBMS Hosting	2013	VLDB	5.093636e-05
13,628	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,240	Consistency Analysis in Bloom: a CALM and Collected Approach	2011	CIDR	0.00011536847
1,457	Building on Quicksand	2009	CIDR	0.00010726983
1,716	Offering a Precision-Performance Tradeoff for Aggregation Queries over Replicated Data	2000	VLDB	9.9330086e-05
1,969	PIQL: Success-Tolerant Query Processing in the Cloud	2012	VLDB	9.3749819e-05
2,228	Data Consistency Properties and the Trade-offs in Commercial Cloud Storages: the Consumers’ Perspective	2011	CIDR	8.9082751e-05
4,328	The Tree Quorum Protocol: An Efficient Approach for Managing Replicated Data	1990	VLDB	6.7568642e-05
7,163	Resilient Logical Structures for Efficient Management of Replicated Data	1992	VLDB	5.6850747e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,152	Fast Algorithms for Maintaining Replica Consistency in Lazy Master Replicated Databases	1999	VLDB
2	2,497	Low-Latency Multi-Datacenter Databases using Replicated Commit	2013	VLDB
3	13,628	PBS at Work: Advancing Data Management with Consistency Metrics	2013	SIGMOD
4	3,328	Rethinking Eventual Consistency	2013	SIGMOD
5	13,169	Reducing Storage for Quorum Consensus Algorithms	1988	VLDB
6	2,837	Improving Performance in Replicated Databases through Relaxed Coherency	1995	VLDB
7	5,910	Replication, Consistency, and Practicality: Are These Mutually Exclusive?	1998	SIGMOD
8	13,098	A Tight Upper Bound on the Benefits of Replication and Consistency Control Protocols	1991	PODS
9	11,535	Confidence Bounded Replica Currency Estimation	2022	SIGMOD
10	6,296	Dissecting the Performance of Strongly-Consistent Replication Protocols	2019	SIGMOD