k-of-n-completion · research · also k out of n completion

k-of-n completion

A k-of-n completion rule finishes a logical operation after any k of n eligible component responses have completed.

Related Observatory article: k-of-n completion on hesela.com

The collection time is the kth ordered response time, measured from a shared request origin, when any eligible subset of size k suffices. A coded read needs distinct valid fragments from one object generation and sufficient decoding rank; receiving k arbitrary messages is not enough. Metadata lookup and decoding may add time. [1] The linked exact example holds per-response late probability at 10% but changes the chance of a late two-of-three completion from 0% to 2.8% to 10% by changing the joint states. These are specified distributions, not fleet observations. [2]

Relations

related
Tail latency, Erasure coding, Fork-early-cancel, Hedged request

Citations

  1. Rashmi et al., EC-Cache, OSDI 2016; sections 2.2, 4.3 and 4.4 (accessed 2026-10-20)
  2. Hesela: k-of-n response collection and exact joint-state examples (accessed 2026-10-20)

JSON: /data/terms/k-of-n-completion.json

Published by Hesela team · Updated

Report a correction · Editorial standards · Reuse guidance

Cite this page
Hesela team. k-of-n completion. Hesela. 2026-10-20. https://hesela.dev/terms/k-of-n-completion/