Read–modify–write

To solve the consensus problem in a shared-memory system, concurrent objects must be introduced. A concurrent object, or shared object, is a data structure which helps concurrent processes communicate to reach an agreement. Traditional implementations using critical sections face the risk of crashing if some process dies inside the critical section or sleeps for an intolerably long time. Researchers defined wait-freedom as the guarantee that the algorithm completes in a finite number of steps.

The consensus number of a concurrent object is defined to be the maximum number of processes in the system which can reach consensus by the given object in a wait-free implementation.^[3] Objects with a consensus number of ${\displaystyle n}$ can implement any object with a consensus number of ${\displaystyle n}$ or lower, but cannot implement any objects with a higher consensus number. The consensus numbers form what is called Herlihy's hierarchy of synchronization objects.^[4]

Consensus number	Objects
${\displaystyle 1}$	atomic read/write registers, mutex
${\displaystyle 2}$	test-and-set, swap, fetch-and-add, wait-free queue or stack
...	...
${\displaystyle 2n-2}$	n-register assignment
...	...
${\displaystyle \infty }$	compare-and-swap, load-link/store-conditional,[5] memory-to-memory move and swap, queue with peek operation, fetch&cons, sticky byte

According to the hierarchy, read/write registers cannot solve consensus even in a 2-process system. Data structures like stacks and queues can only solve consensus between two processes. However, some concurrent objects are universal (notated in the table with ${\displaystyle \infty }$), which means they can solve consensus among any number of processes and they can simulate any other objects through an operation sequence.^[3]