All of us are smarter than any of us:
	  more on the robustness of the Consensus hierarchy
			      (Part II)

		Wai-Kau Lo and Vassos Hadzilacos


			     ABSTRACT

A \emph{wait-free hierarchy} classifies shared object types according to
their strength in supporting wait-free implementations of other types.
Such a hierarchy is \emph{robust} if it is not possible to implement
types the hierarchy classifies as strong by using only types that it
classifies as weak.  The Consensus hierarchy is the most closely studied
wait-free hierarchy.  In \cite{LH96} we proved that the Consensus
hierarchy is not robust if nondeterministic types are allowed.  This
naturally raises the question whether some other wait-free hierarchy is
robust.  In this paper we show that, if nondeterministic types areallowed,
the only robust wait-free hierarchy is the trivial one, which lumps all
types into a single level.