ON THE USE OF REGISTERS IN ACHIEVING WAIT-FREE CONSENSUS

The computational power of concurrent data types has been the focus of much recent research. Herlihy showed that such power may be measured by the type's ability to implement wait-free consensus. Jayanti argued that this ability could be measured in different ways, depending, for example, on whether or not read/write registers could be used in an i mplementation. He demonstrated the significance of this distinction by exhibiting a nondeterministic type whose ability to implement consens us was increased with the availability of registers. We show that regi sters cannot increase the ability to implement wait-free consensus of any deterministic type or of any type that can, without them, implemen t consensus for at least two processes. These results significantly im pact the study of the wait-free hierarchies of concurrent data types. In particular, the combination of these results with other recent work suggests that Jayanti's h(m) hierarchy is robust for certain classes of deterministic types.