What can be decided locally without identifiers?

DOI10.1145/2484239.2484264MaRDI QIDQ5176091zbMATH OpenOpenAlexFDO

Authors Pierre Fraigniaud, Mika Göös, Amos Korman, Jukka Suomela

Publication date 2 March 2015

Published in Proceedings of the 2013 ACM symposium on Principles of distributed computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1302.2570

zbMATH Keywords

computability theorydistributed complexityidentifierslocal decision

Mathematics Subject Classification ID

Distributed systems (68M14) Analysis of algorithms and problem complexity (68Q25) Distributed algorithms (68W15)

Abstract: 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 $GinP$ by having each node run a constant-time distributed decision algorithm. If $GinP$, all the nodes should output yes; if $GotinP$, at least one node should output no. A recent work (Fraigniaud et al., OPODIS 2012) studied the role of identifiers in local decision and gave several conditions under which identifiers are not needed. In this article, we answer their original question. More than that, we do so under all combinations of the following two critical variations on the underlying model of distributed computing: ($B$): the size of the identifiers is bounded by a function of the size of the input network; as opposed to ($egB$): the identifiers are unbounded. ($C$): the nodes run a computable algorithm; as opposed to ($egC$): the nodes can compute any, possibly uncomputable function. While it is easy to see that under ($egB,egC$) identifiers are not needed, we show that under all other combinations there are properties that can be decided locally if and only if identifiers are present. Our constructions use ideas from classical computability theory.

Recommendations

• On the Impact of Identifiers on Local Decision
• What Can be Computed Locally?
• What can be verified locally?
• What can be verified locally?
• A hierarchy of local decision
• scientific article; zbMATH DE number 6820307
• What cannot be computed locally!
• On the investigation of local identifiability: A counterexample
• What can be sampled locally?
• What Can be Sampled Locally?

Cited in

(16)

• What can be verified locally?
• Local checkability, no strings attached: (a)cyclicity, reachability, loop free updates in SDNs
• On mobile agent verifiable problems
• Deciding and verifying network properties locally with few output bits
• Randomized proof-labeling schemes
• A hierarchy of local decision
• Identifiers in registers. Describing network algorithms with logic
• Proof-labeling schemes: broadcast, unicast and in between
• What can be verified locally?
• What Can be Computed Locally?
• Introduction to local certification
• What Can be Sampled Locally?
• On the Impact of Identifiers on Local Decision
• Approximate proof-labeling schemes
• Locally verifiable distributed SNARGs
• Distributed model checking on graphs of bounded treedepth

This page was built for publication: What can be decided locally without identifiers?

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5176091)