On the relative power of shared objects in fault-tolerant distributed systems
Vassoe Hadzilacos, Wai-Kau Lo · 1997
A fundamental question in distributed computing is to determine whether a given set of base shared object types can be used to implement a new type. In this thesis we study this problem in a fault-tolerant setting, where implementations must work even if some of the processes that share the objects may crash. An implementation is t-resilient, if it tolerates the crash of t processes; it is wait-free, if it is $(n - 1)$-resilient, where n is the number of processes. This thesis makes two contributions. The first concerns the classification of shared object types according to their ability to support wait-free implementations. A wait-free hierarchy assigns object types to levels in $\{1,2,\...\}$ such that, using only objects of any type assigned to level n, in conjunction with registers, we can implement an object of any type in a wait-free manner in a system of n processes. Such a hierarchy is robust if, in a system of n processes, it is not possible to implement objects of types at level n in a wait-free manner, using any number and combination of objects of types that are below level n. We show that, if nondeterministic types are allowed, then the only robust wait-free hierarchy is the trivial one, which lumps all types into level one. One important and useful object type is consensus, because consensus objects and registers alone can be used to implement objects of any type. The second contribution of the thesis concerns the ability of object types to support one-resilient implementations of the type consensus. Specifically, we study the relationship between the one-resilient implementability of consensus objects for n processes and that for $n - 1$ processes, for every $n \ge 3.$ On the one hand, the following is shown for n = 3: there exists a deterministic type that can be used to implement a one-resilient consensus object for three, but not two, processes. On the other hand, for every $n \ge 4$, we show that given any set ${\cal B}$ of object types, there is a one-resilient implementation of a consensus object for n processes using ${\cal B}$ if and only if there is a one-resilient implementation of a consensus object for $n - 1$ processes using ${\cal B}.$