Computability in distributed computing
Maurice P. Herlihy, Sergio Rajsbaum, Michel Raynal · ACM SIGACT News · 2012
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. This tutorial surveys some important results about computability in the canonical distributed system model, where processes execute asynchronously, they communicate by reading and writing shared memory, and they fail by crashing. It explains the fundamental role that topology plays in the distributed computability theory.