Summary: 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: 1. We show that leader election among $n$ processes can be solved using a compare \& swap register that can hold $\approx\log n/\log\log n$ values and $n$ read/write registers of size $2\log n$ bits. That is, $n=(k- 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. 2. 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\ge \log n/\log\log n$, must have a run that accesses the compare \& swap register $Θ(\log_kn)$ times. We conjecture that for $k<\log n/\log\log n$ there is 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.