Abstract
The issue of identifiers is crucial in distributed computing. Informally, identities are used for tackling two of the fundamental difficulties that are inherent to deterministic distributed computing, namely: (1) symmetry breaking, and (2) topological information gathering. In the context of local computation, i.e., when nodes can gather information only from nodes at bounded distances, some insight regarding the role of identities has been established. For instance, it was shown that, for large classes of construction problems, the role of the identities can be rather small. However, for the identities to play no role, some other kinds of mechanisms for breaking symmetry must be employed, such as edge-labeling or sense of direction. When it comes to local distributed decision problems, the specification of the decision task does not seem to involve symmetry breaking. Therefore, it is expected that, assuming nodes can gather sufficient information about their neighborhood, one could get rid of the identities, without employing extra mechanisms for breaking symmetry. We tackle this question in the framework of the \(\mathcal{LOCAL}\) model.
Let LD be the class of all problems that can be decided in a constant number of rounds in the \(\mathcal{LOCAL}\) model. Similarly, let LD* be the class of all problems that can be decided at constant cost in the anonymous variant of the \(\mathcal{LOCAL}\) model, in which nodes have no identities, but each node can get access to the (anonymous) ball of radius t around it, for any t, at a cost of t. It is clear that LD* ⊆ LD. We conjecture that LD*=LD. In this paper, we give several evidences supporting this conjecture. In particular, we show that it holds for hereditary problems, as well as when the nodes know an arbitrary upper bound on the total number of nodes. Moreover, we prove that the conjecture holds in the context of non-deterministic local decision, where nodes are given certificates (independent of the identities, if they exist), and the decision consists in verifying these certificates. In short, we prove that NLD*=NLD.
This work is supported by the Jules Verne Franco-Icelandic bilateral scientific framework.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Afek, Y., Kutten, S., Yung, M.: The local detection paradigm and its applications to self stabilization. Theoretical Computer Science 186(1-2), 199–230 (1997)
Angluin, D.: Local and Global Properties in Networks of Processors. In: Proc. Twelfth ACM Symp. on Theory of Computing, STOC, pp. 82–93 (1980)
Amit, A., Linial, N., Matousek, J., Rozenman, E.: Random lifts of graphs. In: Proc. 12th ACM-SIAM Symp. on Discrete Algorithms, SODA, pp. 883–894 (2001)
Awerbuch, B., Patt-Shamir, B., Varghese, G.: Self-Stabilization By Local Checking and Correction. In: Proc. IEEE Symp. on the Foundations of Computer Science, FOCS, pp. 268–277 (1991)
Barenboim, L., Elkin, M.: Distributed (Δ + 1)-coloring in linear (in delta) time. In: Proc. 41st ACM Symp. on Theory of Computing, STOC, pp. 111–120 (2009)
Das Sarma, A., Holzer, S., Kor, L., Korman, A., Nanongkai, D., Pandurangan, G., Peleg, D., Wattenhofer, R.: Distributed Verification and Hardness of Distributed Approximation. In: Proc. 43rd ACM Symp. on Theory of Computing, STOC (2011)
Dereniowski, D., Pelc, A.: Drawing maps with advice. Journal of Parallel and Distributed Computing 72, 132–143 (2012)
Dolev, S., Gouda, M., Schneider, M.: Requirements for silent stabilization. Acta Informatica 36(6), 447–462 (1999)
Gallager, R.G., Humblet, P.A., Spira, P.M.: A distributed algorithm for minimum-weight spanning trees. ACM Trans. on Programming Languages and Systems 5, 66–77 (1983)
Fraigniaud, P., Gavoille, C., Ilcinkas, D., Pelc, A.: Distributed Computing with Advice: Information Sensitivity of Graph Coloring. In: Arge, L., Cachin, C., Jurdziński, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol. 4596, pp. 231–242. Springer, Heidelberg (2007)
Fraigniaud, P., Ilcinkas, D., Pelc, A.: Communication algorithms with advice. J. Comput. Syst. Sci. 76(3-4), 222–232 (2008)
Fraigniaud, P., Korman, A., Lebhar, E.: Local MST computation with short advice. In: Proc. 19th ACM Symp. on Parallelism in Algorithms and Architectures, SPAA, pp. 154–160 (2007)
Fraigniaud, P., Korman, A., Peleg, D.: Local Distributed Decision. In: Proc. 52nd Annual IEEE Symposium on Foundations of Computer Science, FOCS, pp. 708–717 (2011)
Fraigniaud, P., Korman, A., Parter, M., Peleg, D.: Randomized Distributed Decision, http://arxiv.org/abs/1207.0252
Fraigniaud, P., Pelc, A.: Decidability Classes for Mobile Agents Computing. In: Fernández-Baca, D. (ed.) LATIN 2012. LNCS, vol. 7256, pp. 362–374. Springer, Heidelberg (2012)
Fraigniaud, P., Rajsbaum, S., Travers, C.: Locality and Checkability in Wait-Free Computing. In: Peleg, D. (ed.) DISC 2011. LNCS, vol. 6950, pp. 333–347. Springer, Heidelberg (2011)
Fraigniaud, P., Rajsbaum, S., Travers, C.: Universal Distributed Checkers and Orientation-Detection Tasks (submitted, 2012)
Fusco, E.G., Pelc, A.: Communication Complexity of Consensus in Anonymous Message Passing Systems. In: Fernàndez Anta, A., Lipari, G., Roy, M. (eds.) OPODIS 2011. LNCS, vol. 7109, pp. 191–206. Springer, Heidelberg (2011)
Göös, M., Suomela, J.: Locally checkable proofs. In: Proc. 30th ACM Symp. on Principles of Distributed Computing, PODC (2011)
Göös, M., Hirvonen, J., Suomela, J.: Lower bounds for local approximation. In: Proc. 31st Symposium on Principles of Distributed Computing, PODC (2012)
Hasemann, H., Hirvonen, J., Rybicki, J., Suomela, J.: Deterministic Local Algorithms, Unique Identifiers, and Fractional Graph Colouring. In: Even, G., Halldórsson, M.M. (eds.) SIROCCO 2012. LNCS, vol. 7355, pp. 48–60. Springer, Heidelberg (2012)
Hanckowiak, M., Karonski, M., Panconesi, A.: On the Distributed Complexity of Computing Maximal Matchings. SIAM J. Discrete Math. 15(1), 41–57 (2001)
Kor, L., Korman, A., Peleg, D.: Tight Bounds For Distributed MST Verification. In: Proc. 28th Int. Symp. on Theoretical Aspects of Computer Science, STACS (2011)
Korman, A., Kutten, S.: Distributed verification of minimum spanning trees. Distributed Computing 20, 253–266 (2007)
Korman, A., Kutten, S., Masuzawa, T.: Fast and Compact Self-Stabilizing Verification, Computation, and Fault Detection of an MST. In: Proc. 30th ACM Symp. on Principles of Distributed Computing, PODC (2011)
Korman, A., Kutten, S., Peleg, D.: Proof labeling schemes. Distributed Computing 22, 215–233 (2010)
Korman, A., Kutten, S., Peleg, D.: Proof labeling schemes. Detailed version, http://ie.technion.ac.il/~kutten/ps-links/ProofLabelingSchemes.ps
Korman, A., Sereni, J.S., Viennot, L.: Toward More Localized Local Algorithms: Removing Assumptions Concerning Global Knowledge. In: Proc. 30th ACM Symp. on Principles of Distributed Computing, PODC, pp. 49–58 (2011)
Kuhn, F.: Weak graph colorings: distributed algorithms and applications. In: Proc. 21st ACM Symp. on Parallel Algorithms and Architectures, SPAA, pp. 138–144 (2009)
Linial, N.: Locality in distributed graph algorithms. SIAM J. Comput. 21(1), 193–201 (1992)
Lotker, Z., Patt-Shamir, B., Rosen, A.: Distributed Approximate Matching. SIAM J. Comput. 39(2), 445–460 (2009)
Luby, M.: A simple parallel algorithm for the maximal independent set problem. SIAM J. Comput. 15, 1036–1053 (1986)
Naor, M., Stockmeyer, L.: What can be computed locally? SIAM J. Comput. 24(6), 1259–1277 (1995)
Panconesi, A., Srinivasan, A.: On the Complexity of Distributed Network Decomposition. J. Algorithms 20(2), 356–374 (1996)
Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. SIAM (2000)
Seinsche, D.: On a property of the class of n-colorable graphs. J. Combinatorial Theory, Ser. B 16, 191–193 (1974)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fraigniaud, P., Halldórsson, M.M., Korman, A. (2012). On the Impact of Identifiers on Local Decision. In: Baldoni, R., Flocchini, P., Binoy, R. (eds) Principles of Distributed Systems. OPODIS 2012. Lecture Notes in Computer Science, vol 7702. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-35476-2_16
Download citation
DOI: https://doi.org/10.1007/978-3-642-35476-2_16
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-35475-5
Online ISBN: 978-3-642-35476-2
eBook Packages: Computer ScienceComputer Science (R0)