Fault Tolerance Bounds for Asynchronous Memory Consistency

A wait-free distributed algorithm is one in which every process can complete anoperation in a finite number of steps. A generalization of wait-freedom ist-resilience, in which every process can complete an operation in a finitenumber of steps if no more than t processes fail (by stopping). We study theconditions under which algorithms that implement distributed shared memory(DSM) can be implemented resiliently and in a nonblocking manner onasynchronous systems, in which there is no known upper bound on messagelatencies. We derive upper bounds on the number of faults that can betolerated by an object, based on the consistency of histories of certainforms. From these general bounds, we derive bounds for linearizability,sequential consistency, processor consistency, and some weaker memories. Weshow that these latter bounds are tight by displaying implementations thatachieve them. The proof technique for the upper bounds is of independentinterest, due to its applicability to other objects.