Difference between consensus number n and consensus number infinite

Question

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?

Answer 1

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.