@inbook {IOPORT.05266617,
    author       = {Gafni, Eli and Kuznetsov, Petr},
    title        = {$N$-consensus is the second strongest object for $N + 1$ processes.},
    year         = {2007},
    booktitle    = {Principles of distributed systems. 11th international conference, OPODIS 2007, Guadeloupe, French West Indies, December 17--20, 2007. Proceedings},
    isbn         = {978-3-540-77095-4},
    pages        = {260-273},
    publisher    = {Berlin: Springer},
    doi          = {10.1007/978-3-540-77096-1_19},
    abstract     = {Summary: Objects like queue, swap, and test-and-set allow two processes to reach consensus, and are consequently ``universal'' for a system of two processes. But are there deterministic objects that do not solve 2-process consensus, and nevertheless allow two processes to solve a task that is not otherwise wait-free solvable in read-write shared memory? The answer ``no'' is a simple corollary of the main result of this paper: Let $A$ be a deterministic object such that no protocol solves consensus among $n + 1$ processes using copies of $A$ and read-write registers. If a task $T$ is wait-free solvable by $n + 1$ processes using read-write shared-memory and copies of $A$, then $T$ is also wait-free solvable when copies of $A$ are replaced with $n$-consensus objects. Thus, from the task-solvability perspective, $n$-consensus is the second strongest object (after $(n + 1)$-consensus) in deterministic shared memory systems of $n + 1$ processes, i.e., there is a distinct gap between $n$- and $(n + 1)$-consensus. We derive this result by showing that any $(n + 1)$-process protocol $P$ that uses objects $A$ can be emulated using only $n$-consensus objects. The resulting emulation is non-blocking and relies on an a priori knowledge of $P$. The emulation technique is another important contribution of this paper.},
    identifier   = {05266617},
}