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

What can be decided locally without identifiers?

PODC 2013 · 32nd Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, Montreal, Canada, July 2013 · doi:10.1145/2484239.2484264

authors’ version publisher’s version arXiv.org

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 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.

Recently, Fraigniaud et al. (OPODIS 2012) gave several conditions under which identifiers are not needed, and they conjectured that identifiers are not needed in any decision problem. In the present work, we disprove the conjecture.

More than that, we analyse two critical variations of the underlying model of distributed computing:

  • (B): the size of the identifiers is bounded by a function of the size of the input network,
  • (¬B): the identifiers are unbounded,
  • (C): the nodes run a computable algorithm,
  • (¬C): the nodes can compute any, possibly uncomputable function.

While it is easy to see that under (¬B,¬C) 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.

Publication

Panagiota Fatourou and Gadi Taubenfeld (Eds.): PODC’13, Proceedings of the 2013 ACM Symposium on Principles of Distributed Computing, July 22–24, 2013, Montreal, QC, Canada, pages 157–165, ACM Press, New York, 2013

ISBN 978-1-4503-2065-8

Links

© Fraigniaud et al. 2013. This is the author’s version of the work. It is posted here for your personal use. Not for redistribution. The definitive version was published in Proc. PODC 2013.

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author’s copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.