The Life in 1-Consensus

Abstract

This paper introduces the atomic Write and Read Next (${\text{WRN}}_k$) deterministic shared memory object, that for any $k\ge 3$, is stronger than read-write registers, but is unable to implement $2$-processor consensus. In particular, it refutes the conjecture claiming that every deterministic object of consensus number $1$ is computationally equivalent to read-write registers.

8 pages