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.
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
