This extensive survey begins with a concise overview of models, problems, and proof techniques for distributed computing, which establishes a common nomenclature used throughout the work. It proceeds with the illustration of known unsolvability results for several problem categories on synchronous and asynchronous models. Next, a section on model comparison discusses the relevance and suitability of using a computational model to prove some property of a problem. Undecidability and decidability are also addressed, as well as robustness, space complexity, time complexity, and message complexity on different networks. The intent is to offer an analytical and theoretical perspective on the difficulties arising from the lack of global knowledge in distributed computing.

The explicit aim of this survey is to “improve and enable” the contribution of new impossibility results and techniques. As such, it is written for, and addressed to, computational theorists, and the more theoretically inclined practitioners. The coverage favors breadth over depth, even if, in many cases of greater interest, the survey includes outlines of proofs, and details of technique. This survey paper is a great guide to its opulent list of references, which includes 300 works on the subject matter; some of these citations are as new as 2003, and most have been published within the preceding decade.