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.
Recent comments
1 hour 18 min ago
20 hours 48 min ago
12 weeks 1 day ago
12 weeks 2 days ago
12 weeks 3 days ago
12 weeks 3 days ago
13 weeks 1 day ago
13 weeks 1 day ago
13 weeks 1 day ago
16 weeks 1 day ago