Herlihy's wait-free hierarchy

From dankwiki
Revision as of 05:33, 6 May 2013 by Dank (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

A hierarchy of concurrency objects and their consensus numbers.

Consensus number Object
1 Atomic read/write registers
2 Test-and-set, fetch-and-add
2n-2 n-register assignment
Compare-and-swap, FIFO queue with peek