What can be decided locally without identifiers?

DOI10.1145/2484239.2484264zbMath1323.68031arXiv1302.2570OpenAlexW2054573207MaRDI QIDQ5176091

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

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 complexitylocal decisionidentifiers

Mathematics Subject Classification ID

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

Related Items (10)

Node labels in local decision ⋮ What can be verified locally? ⋮ Proof-labeling schemes: broadcast, unicast and in between ⋮ Local checkability, no strings attached: (a)cyclicity, reachability, loop free updates in SDNs ⋮ A hierarchy of local decision ⋮ Deciding and verifying network properties locally with few output bits ⋮ On mobile agent verifiable problems ⋮ Randomized proof-labeling schemes ⋮ Approximate proof-labeling schemes ⋮ Introduction to local certification

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