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

           Wai-Kau Lo and Vassos Hadzilacos


                       ABSTRACT

We consider objects accessed by concurrent processes.  The
Consensus hierarchy \cite{Her91a,Jay93} classifies object
types on the basis of their strength in supporting wait-free
implementations of other types.  In the context of the present
paper, an implementation may use any number of objects of the
given types, as well as read/write registers.  We prove that,
if nondeterministic types are allowed, the Consensus hierarchy
is not robust: It is possible to implement objects of types
classified as ``strong'' by combining objects of types that
are individually classified as ``weak''.  Thus, in general,
it is not possible to determine the power of a concurrent
system that supports a given set of primitive object types by
reasoning about the power of each primitive type in isolation.