On the space complexity of randomized synchronization

Abstract. The “wait-free hierarchy ” provides a classification of multiprocessor synchronization primitives based on the values of n for which there are deterministic wait-free implementations of n-process consensus using instances of these objects and read-write registers. In a randomized wait-free setting, this classification is degenerate, since n-process consensus can be solved using only O(n) read-write registers. In this paper, we propose a classification of synchronization primitives based on the space complexity of randomized solutions to n-process consensus. A historyless object, such as a read-write register, a swap register, or a test&set register, is an object whose state depends only on the last nontrivial operation that was applied to it. We show that, using historyless objects, �(�n) object instances are necessary to solve n-process consensus. This lower bound holds even if the objects have unbounded size and the termination requirement is nondeterministic solo termination, a property strictly weaker than randomized wait-freedom