2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

memory-to-memory-swap

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.

$\endgroup$

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.