What cannot be computed locally!
Top Cited Papers
- 25 July 2004
- proceedings article
- Published by Association for Computing Machinery (ACM)
- p. 300-309
- https://doi.org/10.1145/1011767.1011811
Abstract
No abstract availableKeywords
This publication has 16 references indexed in Scilit:
- Hundreds of impossibility results for distributed computingDistributed Computing, 2003
- A Near-Tight Lower Bound on the Time Complexity of Distributed Minimum-Weight Spanning Tree ConstructionSIAM Journal on Computing, 2000
- A threshold of ln n for approximating set coverJournal of the ACM, 1998
- An $\Omega(D\log (N/D))$ Lower Bound for Broadcast in Radio NetworksSIAM Journal on Computing, 1998
- The local detection paradigm and its applications to self-stabilizationTheoretical Computer Science, 1997
- Explicit construction of graphs with an arbitrary large girth and of large sizeDiscrete Applied Mathematics, 1995
- Locality in Distributed Graph AlgorithmsSIAM Journal on Computing, 1992
- Deterministic coin tossing with applications to optimal parallel list rankingInformation and Control, 1986
- A fast and simple randomized parallel algorithm for maximal matchingInformation Processing Letters, 1986
- Impossibility of distributed consensus with one faulty processJournal of the ACM, 1985