On the use of registers in achieving wait-free consensus |
| |
Authors: | Rida A Bazzi Gil Neiger Gary L Peterson |
| |
Affiliation: | (1) Computer Science and Engineering Department, College of Engineering and Applied Sciences, Arizona State University, P.O. Box 875406, Tempe, AZ 85287-5406, USA, US;(2) Intel Corporation, JF3-359, 2111 N.E. 25th Avenue, Hillsboro, OR 97124-5964, USA, US;(3) Computer and Information Science Program, Spelman College, 350 Spelman Lane SW, P.O. Box 333, Atlanta, GA 30314-0339, USA, US |
| |
Abstract: | Summary. 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 implementation. He demonstrated
the significance of this distinction by exhibiting a nondeterministic type whose ability to implement consensus was increased
with the availability of registers. We show that registers cannot increase the ability to implement wait-free consensus of
any deterministic type or of any type that can, without them, implement consensus for at least two processes. These results
significantly impact 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. |
| |
Keywords: | : Registers Consensus Wait-free computation Wait-free hierarchies Robustness |
本文献已被 SpringerLink 等数据库收录! |
|