Power and limits of distributed computing shared memory models

What can and cannot be computed in a distributed system is a complex function of the system's communication model, timing model, and failure model. Considering a canonical distributed system model, where processes execute asynchronously, communicate by reading and writing shared memory, and fail by crashing, this paper surveys important results about computability, and explains the fundamental role that topology plays in the distributed computability theory. The paper also considers different types of additional assumptions that allow impossibility results to be circumvented. These assumptions are known under the names failure detectors and adversaries. Finally, it presents a powerful simulation technique (known under the name BG simulation), which allows to show that, from a computability point of view, t-resilience is not different from wait-freedom. When pieced together, the aim of all the concepts, notions, models, and algorithms presented in the paper, is to provide the reader with a synthetic view of important results on the distributed asynchronous read/write shared-memory model, its power and its limits.