m-Consensus Objects Are Pretty Powerful

A recent paper by Afek, Ellen, and Gafni introduced a family of deterministic objects O_{m,k}, for m,k >= 2, with consensus numbers m such that, for each k >= 2, O_{m,k} is computationally less powerful than O_{m,k+1} in systems with at least mk+m+k processes. This paper gives a wait-free implementation of O_{m,k} from (m + 1)-consensus objects and registers in systems with any finite number of processes. In order to do so, it introduces a new family of objects which helps us to understand the power of m-consensus among more than m processes