Advertisement
Published in:
2012 | OriginalPaper | Chapter
Renaming Is Weaker Than Set Agreement But for Perfect Renaming: A Map of Sub-consensus Tasks
Authors : Armando Castañeda, Damien Imbs, Sergio Rajsbaum, Michel Raynal
Published in: LATIN 2012: Theoretical Informatics
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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 ≤
k
≤
n
− 1 and
n
≤
M
≤ 2
n
− 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.