Though it is common practice to treat synchronization primitives for multiprocessors as abstract data types, they are in reality machine instructions on registers. A crucial theoretical question with practical implications is the relationship between the size of the register and its computational power. We wish to study this question and choose as a first target the popular compare & swap operation Ž . which is the basis for many modern multiprocessor architectures . Our main results are:
-
We show that leader election among n processes can be solved using a compare & swap register that can hold f log nrlog log n values and n readrwrite Ž . registers of size 2 log n bits. That is, n s k y 1 ! where k is the number of values Ž in the compare & swap register, so the compare & swap register has only O log . log n bits.
-
We prove a tight tradeoff between the space and time necessary to solve leader election with a compare & swap register. Specifically, we show that any algorithm for leader election among n processes with a k value compare & swap register, where k G log nrlog log n, must have a run that accesses the compare & Ž . swap register ⌰ log n times. We conjecture that for klog nrlog log n there is k no solution.
The results of this paper suggest that a complexity hierarchy for multiprocessor synchronization operations should be based on the space complexity of synchronization registers and their type.