\input zb-basic
\input zb-ioport
\iteman{io-port 06051293}
\itemau{Casta\~neda, Armando; Imbs, Damien; Rajsbaum, Sergio; Raynal, Michel}
\itemti{Renaming is weaker than set agreement but for perfect renaming: A map of sub-consensus tasks.}
\itemso{Fern\'andez-Baca, David (ed.), LATIN 2012: Theoretical informatics. 10th Latin American symposium, Arequipa, Peru, April 16--20, 2012. Proceedings. Berlin: Springer (ISBN 978-3-642-29343-6/pbk). Lecture Notes in Computer Science 7256, 145-156 (2012).}
\itemab
Summary: In the wait-free shared memory model substantial attention has been devoted to understanding the relative power of sub-consensus tasks. Two important sub-consensus families of tasks have been identified: $k$-set agreement and $M$-renaming. When $2 \leq k \leq n - 1$ and $n \leq M \leq 2n - 2$, these tasks are more powerful than read/write registers, but not strong enough to solve consensus for two processes. This paper studies the power of renaming with respect to set agreement. It shows that, in a system of $n$ processes, $n$-renaming is strictly stronger than $(n - 1)$-set agreement, but not stronger than $(n - 2)$-set agreement. Furthermore, $(n + 1)$-renaming cannot solve even $(n - 1)$-set agreement. As a consequence, there are cases where set agreement and renaming are incomparable when looking at their power to implement each other.
\itemrv{~}
\itemcc{}
\itemut{decision task; distributed computability; problem hierarchy; renaming; $k$-set agreement; symmetry breaking; wait-freedom}
\itemli{doi:10.1007/978-3-642-29344-3\_13}
\end