Hundreds of impossibility results for distributed computing

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 t...

Full description

Saved in:
Bibliographic Details
Published in:Distributed computing 2003-09, Vol.16 (2-3), p.121-163
Main Authors: Fich, Faith, Ruppert, Eric
Format: Article
Language:English
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0178-2770
1432-0452
DOI:10.1007/s00446-003-0091-y