pbs-k-staleness · research · also Probabilistically bounded version staleness

PBS k-staleness

PBS k-staleness describes a probabilistic guarantee that a read includes a version from the k latest completed writes or a newer in-flight write.

The 2012 formulation uses version count, not elapsed time; k=1 targets the latest completed version or a newer write. Its non-expanding uniform independent-placement model raises a single-write miss probability to k. [1]

The 2014 paper expresses version freshness using (K,p)-regular semantics, distinct from atomic semantics. A per-read freshness probability does not by itself establish a linearizable history. [2]

In Hesela's exact constructed mixture, K is chosen independently of replica placement. Equal mean K does not imply equal miss risk: the mixture averages conditional probabilities, not exponents. This is a deduction under stated assumptions, not a workload measurement. [3]

Relations

related

Partial quorum, PBS t-visibility, Monotonic reads, Regular register

Limitations

• The probability depends on a stated model; no particular production failure rate or deterministic bound is implied. [1, 2]

Citations

1. Bailis et al. Probabilistically Bounded Staleness for Practical Partial Quorums. PVLDB 5(8), 776-787 (2012), sections 3.1-3.4. DOI: 10.14778/2212351.2212359. (accessed 2026-11-11)
2. Bailis et al. Quantifying eventual consistency with PBS. The VLDB Journal 23, 279-302 (2014), sections 2.2-2.3, 4.1-4.2. DOI: 10.1007/s00778-013-0330-1. (accessed 2026-11-11)
3. Hesela: exact version-count mixtures, assumptions and executable source hashes. (accessed 2026-11-11)

JSON: /data/terms/pbs-k-staleness.json