I think that consensus number of mem-to-mem-swap(a,b) operation which atomically swaps the values between shared locations a and b (shared R/W memory) is infinite , but I'm having trouble proving it.
I thought about implementing CAS with mem-to-mem-swap but comparing atomically is problematic, I think there is straightforward consensus protocol but I can't think about one.


1 Answer 1


See Theorem 10 (Figure 13) of the paper "Wait-Free Synchronization " by Herlihy, 1991.

Theorem 10: An array of registers with memory-to-meory swap has infinite consensus number.

Proof: The protocol is shown in Figure 13. The processes share an array of registers $a[1 \ldots n]$ whose elements are initialized to $0$ and a single register $r$, initialized to $1$. The first process to swap $1$ into $a$ wins.


Footnote 4 of this paper remarks that:

The memory-to-memory swap should not be confused with the read-modify-write swap; the former exchanges the values of two public registers, while the latter exchanges the value of a public register with a processor’s private register.


This site is temporarily in read-only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .