A simple characterization of asynchronous computations

In this paper we investigate synchronous message-passing systems with reliable processors but different scenarios of message loss. In particular, we investigate and present the minimum set of messages whose delivery must be guaranteed to ensure the equivalence of this model to asynchronous wait-free shared-memory. Delivery guarantees were investigated in the past at the other extreme - delivery guarantees that ensure consensus.Because message failure is a more refined type of fault than processor crash failure, we were able to use in this paper an extremely simple message-passing model to characterize exactly what is computable in wait-free read-write shared memory. We use a synchronous complete network where in each round a subset from a defined family of subsets of messages, must be successfully delivered. With this model we obtain an extremely simple derivation of the Herlihy-Shavit condition that equates the wait-free read-write model with a subdivided-simplex. We show how each step in the computation inductively takes a subdivided-simplex and further subdivides it in the simplest way possible, making the characterization of read-write wait-free widely accessible.