On the Space Complexity of Randomized Synchronization

1. Introduction Traditionally, the theory of interprocess synchronization has centered around the notion of mutual exclusion: ensuring that only one process at a time is allowed to modify complex shared […]
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, Ω([square root of 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. We then use this result to relate the randomized space complexity of basic multiprocessor synchronization primitives such as shared counters, fetch&add registers, and compare&swap registers. Viewed collectively, our results imply that there is a separation based on space complexity for synchronization primitives in randomized computation, and that this separation differs from that implied by the deterministic "wait-free hierarchy." Categories and Subject Descriptors: F.1.2 [Computation by Abstract Devices]: Modes of Computation-parallelism and concurrency; F.1.3 [Computation by Abstract Devices]: Complexity Measures and Classes--complexity hierarchies Gerneral Terms: Algorithms, Theory Additional Key Words and Phrases: Consensus, lower bounds, space complexity