What can be decided locally without identifiers?
Pierre Fraigniaud, Mika Göös, Amos Korman, Jukka Suomela · 2013
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.