View Related Documents

Abstract

We consider the hierarchy of wait-free shared objects, and show that this hierarchy does not express the computational power of shared objects. We prove that there are objects that are classified high in the hierarchy, yet, they can not implement objects that are classified much lower in the hierarchy. Our main result is: for any two levels k 1gek 2 in the hierarchy, there are shared objects X 1 and X 2 that belong to k 1 and k 2, respectively, such that X 1 can not implement X 2. (We allow the specifications of the shared objects to be non deterministic.) This result implies not only that the current definition of the wait-free hierarchy does not express the computational power of shared objects, but also that there is no other hierarchy that does.

Fulltext Preview

Image of the first page of the fulltext document