Resource Bounds and Combinations of Consensus Objects
No Access Until
Permanent Link(s)
Collections
Other Titles
Author(s)
Abstract
The shared-memory model of computation typically provides processes with an arbitrary number of copies of the available object types; yet a simple argument shows that any consensus protocol can only make use of some finite subset of these. Thus we believe it is useful to consider the problem of consensus from the point of view of resource bounds, determining whether consensus can still be solved when the number of copies of the system's shared objects is limited. This approach leads to a general technique which we call the combination protocol, in which the number of processes that can achieve consensus with a given object increases as more copies of it are made available. Such a phenomenon brings up questions about the robustness of Herlihy's consensus hierarchy, in that objects are being combined to solve