pbs-t-visibility · research · also Probabilistically bounded time visibility

PBS t-visibility

PBS t-visibility describes a probabilistic guarantee that a read started at least t after a write commits includes that write's version or a newer one.

This is the 2012 PBS time-based formulation; the reference event is write commit, not submission. Its estimates require a propagation model and do not impose a deterministic visibility deadline. [1]

The later journal treatment separates time-based regular and atomic semantics. A result about freshness is not automatically a result about atomic read ordering. [2]

A version-count distribution alone cannot determine elapsed-time freshness. Hesela's count-mixture example deliberately supplies no message-delay distribution and makes no time-visibility claim. [3]

Relations

related

Partial quorum, PBS k-staleness, Eventual consistency, Replication lag

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-t-visibility.json