Consider as an example a machine with two processors,

It is unfortunately proved in [Fisher et al., 1985] that this is not possible -- in fact it was proven for the equivalent case of an asynchronous message-passing system, in the general 1-resilient case. The article used an argument from graph theory (but already quite geometric in nature). It has in fact originated the geometric point of view on this field of research as we are going to explain

Figure 7: The binary consensus decision map from initial global states to final global states

Further work generalizes this simple geometric argument to the needed higher-dimensio-nal cases. In [Biran et al., 1988] a characterization of a class of problems solvable in asynchronous message-passing systems in the presence of a single failure was given. No generalization to more failures has since been solved using the same kinds of graph techniques. It was then a rather shared belief that one would have to use more powerful techniques in that case. The conjecture [Chaudhuri, 1990] that the

Figure 8: The synchronous protocol complex (for 3 processes) after one round

The basic idea of [Herlihy and Shavit, 1993] is to generalize such pictures as the one of Figure 7 using

The renaming task (processes must try to agree on a smaller set of names between each other than the original set of names), proposed in [Attiya et al., 1990] was also finally solved in [Herlihy and Shavit, 1993]. There is a wait-free protocol for the renaming task in certain asynchronous systems if the output name space is sufficiently large. It was already known that there is a wait-free solution for the renaming task for 2

Not only impossibility results can be given but also constructive means for finding algorithms follow from this work (for instance [Herlihy and Shavit, 1994]).

More generally, datatypes do matter for computability results. It is known for quite a long time that consensus for two processes can be solved with shared memory with atomic reads and writes plus a FIFO queue, or plus an atomic test&set operation. If we define the consensus number of a data type as the maximal number of asynchronous processors (having atomic read and write) on which it can implement wait-free consensus, then,

- atomic read/write registers have consensus number 1,
- test&set and fetch&add registers, queues, and stacks have consensus number 2,
*n*-register assignment has consensus number 2*n*-2,- load-locked, store-conditional and compare-and-swap registers have consensus number ¥.

Further work on this can be found in [Jayanti, 1993], [Jayanti, 1997] and [Schenk, 1997]. In particular, the problem identified in [Jayanti, 1997] is that the hierarchy of data objects as briefly sketched above is not robust, in the sense that it is possible to implement some datatypes with consensus number

This of course is due to some subtle interactions between the use of these data objects and we could hope that the more general study of the schedules with such datatypes could lead to some better classifications.

In ``Algebraic Spans'' in a forthcoming issue of Mathematical Structures in Computer Science, M. Herlihy and S. Rajsbaum introduce a new tool (related to the one described in [Herlihy and Rajsbaum, 1995] for proving impossibility results, based on a core theorem of algebraic topology, the acyclic carrier theorem, which unifies, generalizes and extends earlier results.