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
6 weeks 4 days ago
6 weeks 6 days ago
7 weeks 13 hours ago
14 weeks 11 hours ago
19 weeks 5 days ago
19 weeks 6 days ago
20 weeks 5 days ago
23 weeks 3 days ago
24 weeks 6 days ago
25 weeks 2 hours ago