2013 · 38 citations · 15 references
ComputingComputer ScienceAlgorithmsDecision TheoryDistributed SystemsDistributed AlgorithmsDistributed ComputingComputabilityDistributed Computation Models
Do unique node identifiers help in deciding whether a network G has a prescribed property P? We study this question in the context of distributed local decision, where the objective is to decide whether G has property P by having each node run a constant-time distributed decision algorithm. In a yes-instance all nodes should output yes, while in a no-instance at least one node should output no.
15
Locality in Distributed Graph Algorithms
Nathan Linial · SIAM Journal on Computing · 1992 · 885 citations
Moni Naor, Larry Stockmeyer · SIAM Journal on Computing · 1995 · 317 citations
Distributed Verification and Hardness of Distributed Approximation
Atish Das Sarma, Stephan Holzer, Liah Kor et al. · SIAM Journal on Computing · 2012 · 215 citations · Full text
Amos Korman, Shay Kutten, David Peleg · Distributed Computing · 2010 · 188 citations