Herlihy's wait-free hierarchy

From dankwiki
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

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