On the Impact of Identifiers on Local Decision

DOI10.1007/978-3-642-35476-2_16zbMath1323.68032arXiv1512.06989OpenAlexW2123081773MaRDI QIDQ5499979

Amos Korman, Pierre Fraigniaud, Magnús M. Halldórsson

Publication date: 5 August 2015

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

identitiesdecision problemssymmetry breakinglocalitynon-determinismdistributed complexity

Mathematics Subject Classification ID

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

Related Items (13)

Node labels in local decision ⋮ Planarity can be verified by an approximate proof labeling scheme in constant-time ⋮ 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 ⋮ Fast and compact self-stabilizing verification, computation, and fault detection of an MST ⋮ Deciding and verifying network properties locally with few output bits ⋮ On mobile agent verifiable problems ⋮ Randomized proof-labeling schemes ⋮ Approximate proof-labeling schemes ⋮ Proof labeling schemes for reachability-related problems in directed graphs ⋮ Introduction to local certification

This page was built for publication: On the Impact of Identifiers on Local Decision