On the equivalence of strongly t-resilient and wait-free implementations of consensus

In this thesis, we study the relationship between the implementability of type consensus, in a strongly t-resilient and in a wait-free manner, from an arbitrary set of object types, in the asynchronous shared memory model and in the presence of process crashes. We show that, for all n > t ≥ 0, and sets $S$ of types that include type register, there is a strongly t-resilient implementation of an n-ported consensus object from objects of types in $S$, if and only if there is a wait-free implementation of a (t + 1)-ported consensus object from objects of types in $S$. This equivalence is a generalization of a similar result suggested by Chandra et al. [CHJT94] for a restricted class of object types and connectivity rules of processes to shared objects. An important corollary of our result is that, if a (t + 1)-ported consensus object has a wait-free implementation from objects of types in $S$, then any n-ported object has a strongly t-resilient implementation from objects of types in $S$.