Hundreds of Impossibility Results for Distributed Computing

Hundreds of Impossibility Results for Distributed Computing
This paper is not as sad as its title impies: it surveys what assumptions and resources are necessary to achieve some specific results in distributed computing. Or if you insist on being pessimistic: what results are impossible without certain assumptions and resources.

We survey results from distributed computing that show tasks to be impossible, either outright or within given resource bounds, in various models. The parameters of the models considered include synchrony, fault-tolerance, different communication media, and randomization. The resource bounds refer to time, space and message complexity.
These results are useful in understanding the inherent difficulty of individual problems and in studying the power of different models of distributed computing. There is a strong emphasis in our presentation on explaining the wide variety of techniques that are used to obtain the results described.

Looks to be helpful for a strategic planning of a distributed PL design and implementation.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Looks real interesting

One of my favorite subjects, and the paper looks very nice.

Games failures play

I especially enjoyed their methodology of viewing failures as being managed by an adversary - sounds like game semantcis :-)