Agreeing within a few writes

The notion of adopt-commit object [29] is of pivotal importance in understanding the consensus problem. This object models an attempt of the processes to agree on some common value, and precisely captures the cost of the fast path a process takes during a solo run. In this paper, we address the problem of implementing an adopt-commit object in the shared memory model in the minimal number of write operations. We consider that the number of processes (n), their identities (c), as well as the size of the input set (m) may all vary. Our first contribution is an algorithm that executes three write operations, a value we show optimal in the general case. We also prove that this number reduces to two when either m is known and bounded, or n identities are available. In the corner case where n=2, and either c=2 or the input set is finite, a single write suffices. Further, we introduce Janus, an elegant adopt-commit implementation that executes O(n) shared memory operations, including O(n) writes. Building upon Janus, we explain how to design an adopt-commit object that executes O(n−c+1) write operations. We prove that this last value is tight when the number of registers in use is bounded and m is unknown.