Task Computability in Unreliable Anonymous Networks

We consider the anonymous broadcast model: a set of n anonymous processes communicate via send-to-all primitives. We assume that underlying communication channels are asynchronous but reliable, and that the processes are subject to crash failures. We show first that in this model, even a single faulty process precludes implementations of atomic objects with non-commuting operations, even as simple as read-write registers or add-only sets. We, however, show that a sequentially consistent read-write memory and add-only sets can be implemented t-resiliently for t