In book Concurrent Programming: Algorithms, Principles, and Foundations of Michel Raynal, in Section 16.5.1, Theorem 75 says

Compare&swap objects have infinite consensus number.

and in Section 16.5.2, Lemma 40 says

The mem-to-mem-swap object type has consensus number n in a system of n processes.

Then, in Section 16.1, author puts in table both Compare&swap and men-to-mem-swap as objects with consensus number infinite.

So, what is the difference between objects with consensus number n and objects with consensus number infinite?


The consensus number of an object is the maximum number of concurrent processes that you can synchronize with one such object in a wait-free manner (I won't go into what wait-free means here). For example, a register with only read and write operations doesn't help with wait-free synchronization at all, so it has consensus number 1. A register with a test-and-set operation can be used to synchronize two processes in a wait-free manner, but not three or more, so the consensus number of test-and-set is 2.

$n$-register assignment, where a process can atomically write to multiple registers, allows up to $2n-2$ processes to synchronize wait-free if there are $n$ registers. More processes require more registers. Therefore the consensus number of an objet consisting of $n$ registers that can be assigned atomically is $2n-2$.

A single register with a compare-and-swap operation is sufficient to synchronize any number of processes wait-free. Therefore the consensus number of compare-and-swap is infinite.

Lemma 40 states that a mem-and-swap object allows the wait-free synchronization of all the processes in a system of $n$ concurrent processes, for any number $n$. This means that for any number $n$, the consensus number of mem-and-swap is at least $n$. (Stating that the consensus number is $n$ in a system of $n$ processes is a bit of a misnomer since the definition of the consensus number doesn't actually depend on the total number of processes.) Since consensus number of mem-and-swap is at least $n$ for any $n$, it's infinite.

If you prefer another source than Raynal's book, you can read the original paper by Maurice Herlihy.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.