Towards a complexity theory for local distributed computing

Abstract

A central theme in distributed network algorithms concerns understanding and coping with the issue of locality. Yet despite considerable progress, research efforts in this direction have not yet resulted in a solid basis in the form of a fundamental computational complexity theory for locality. Inspired by sequential complexity theory, we focus on a complexity theory for distributed decision problems. In the context of locality, solving a decision problem requires the processors to independently inspect their local neighborhoods and then collectively decide whether a given global input instance belongs to some specified language.

We consider the standard LOCAL model of computation and define LD(t) (for local decision) as the class of decision problems that can be solved in t communication rounds. We first study the intriguing question of whether randomization helps in local distributed computing, and to what extent. Specifically, we define the corresponding randomized class BPLD(t,p,q), containing all languages for which there exists a randomized algorithm that runs in t rounds, accepts correct instances with probability at least p, and rejects incorrect ones with probability at least q. We show that p² + q = 1 is a threshold for the containment of LD(t) in BPLD(t,p,q). More precisely, we show that there exists a language that does not belong to LD(t) for any t=o(n) but does belong to BPLD(0,p,q) for any p,q ∈ (0,1) such that p² + q ≤ 1. On the other hand, we show that, restricted to hereditary languages, BPLD(t,p,q)=LD(O(t)), for any function t, and any p, q ∈ (0,1) such that p² + q > 1.

In addition, we investigate the impact of nondeterminism on local decision, and establish several structural results inspired by classical computational complexity theory. Specifically, we show that nondeterminism does help, but that this help is limited, as there exist languages that cannot be decided locally nondeterministically. Perhaps surprisingly, it turns out that it is the combination of randomization with nondeterminism that enables to decide all languages in constant time. Finally, we introduce the notion of local reduction, and establish a couple of completeness results.

References

1. Afek, Y., Kutten, S., and Yung, M. 1997. The local detection paradigm and its applications to self stabilization. Theoret. Comput. Sci. 186, 1--2, 199--230.
2. Alon, N., Babai, L., and Itai, A. 1986. A fast and simple randomized parallel algorithm for the maximal independent set problem. J. Algor. 7, 4, 567--583.
3. Amit, A., Linial, N., Matousek, J., and Rozenman, E. 2001. Random lifts of graphs. In Proceedings of the 12th ACM-SIAM Symposium on Discrete Algorithms (SODA). 883--894.
4. Attiya, H., Bar-Noy, A., and Dolev, D. 1995. Sharing memory robustly in message-passing systems. J. ACM 42, 1, 124--142.
5. Awerbuch, B., Patt-Shamir, B., and Varghese, G. 1991. self-stabilization by local checking and correction. In Proceedings of the IEEE Symposium on the Foundations of Computer Science (FOCS). 268--277.
6. Awerbuch, B., Patt-Shamir, B., Varghese, G., and Dolev, S. 1994. Self-stabilization by local checking and global reset. In Proceedings of the Workshop on Distributed Algorithms. Lecture Notes in Computer Science, vol. 857, Springer, 326--339.
7. Barenboim, L. and Elkin, M. 2009. Distributed (Δ + 1)-coloring in linear (in delta) time. In Proceedings of the 41st ACM Symposium on Theory of Computing (STOC). 111--120.
8. Barenboim, L., Elkin, M., Pettie, S., and Schneider, J. 2012. The locality of distributed symmetry breaking. In Proceedings of the 53rd IEEE Symposium on Foundations of Computer Science (FOCS). 321--330.
9. Chandra, T. D. and Toueg, S. 1996. Unreliable failure detectors for reliable distributed systems. J. ACM 43, 2, 225--267.
10. Chandra, T. D., Hadzilacos, V., and Toueg, S. 1996. The weakest failure detector for solving consensus. J. ACM 43, 4, 685--722.
11. Das Sarma, A., Holzer, S., Kor, L., Korman, A., Nanongkai, D., Pandurangan, G., Peleg, D., and Wattenhofer, R. 2011. Distributed verification and hardness of distributed approximation. In Proceedings of the 43rd ACM Symposium on Theory of Computing (STOC). 363--372.
12. Derbel, B., Gavoille, C., Peleg, D., and Viennot, L. 2009. Local computation of nearly additive spanners. In Proceedings of the 23rd Symposium on Distributed Computing (DISC), 176--190.
13. Dijkstra, E. W. 1974. Self-stabilization in spite of distributed control. Commun. ACM 17, 11, 643--644.
14. Dolev, S., Gouda, M., and Schneider, M. 1999. Requirements for silent stabilization. Acta Inf. 36, 6, 447--462.
15. Elkin, M. 2006. A faster distributed protocol for constructing a minimum spanning tree. J. Comput. Syst. Sci. 72, 8, 1282--1308.
16. Elkin, M. and Zhang, J. 2006. Efficient algorithms for constructing (1 + ε, β)-spanners in the distributed and streaming models. Distrib. Comput. 18, 5, 375--385.
17. Fischer, M. J., Lynch, N. A., and Paterson, M. 1985. Impossibility of distributed consensus with one faulty process. J. ACM, 32, 2, 374--382.
18. Fraigniaud, P., Ilcinkas, D., and Pelc, A. 2008. Communication algorithms with advice. J. Comput. Syst. Sci. 76, 3--4, 222--232.
19. Fraigniaud, P., Gavoille, C., Ilcinkas, D., and Pelc, A. 2007a. Distributed computing with advice: Information sensitivity of graph coloring. In Proceedings of the 34th Colloquium on Automata, Languages and Programming (ICALP). 231--242.
20. Fraigniaud, P., Göös, M., Korman, A., and Suomela, J. 2013. What can be decided locally without identifiers? In Proceedings of the 32nd ACM Symposium on Principles of Distributed Computing. 157--165.
21. Fraigniaud, P., Halldórsson, M., and Korman, A. 2012a. On the impact of identifiers on local decision. In Proceedings of the 16th International Conference on Principles of Distributed Systems (OPODIS). 224--238.
22. Fraigniaud, P., Korman, A., and Lebhar, E. 2007b. Local MST computation with short advice. In Proceedings of the 19th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 154--160.
23. Fraigniaud, P., Korman, A., Parter, M., and Peleg, D. 2012b. Randomized distributed decision. In Proceedings of the 26th International Symposium on Distributed Computing (DISC). Spinger, Lecture Notes in Computer Science, vol. 7611, 371--385.
24. Fraigniaud, P., Korman, A., and Peleg, D. 2011a. Local distributed decision. In Proceedings of the 52nd IEEE Symposium on Foundations of Computer Science (FOCS). 708--717.
25. Fraigniaud, P., Rajsbaum, S., and Travers, C. 2011b. Locality and checkability in wait-free computing. In Proceedings of the 25th International Symposium on Distributed Computing (DISC). 333--347.
26. Fraigniaud, P., Rajsbaum, S., and Travers, C. 2012c. Universal distributed checkers and orientation-detection tasks. Submitted.
27. Goldreich, O. ed. 2010. Property Testing—Current Research and Surveys. Lecture Notes in Computer Science, vol. 6390, Springer.
28. Goldreich, O. and Ron, D. 2002. Property testing in bounded degree graphs. Algorithmica 32, 2, 302--343.
29. Göös, M. and Suomela, J. 2011. Locally checkable proofs. In Proceedings of the 30th ACM Symposium on Principles of Distributed Computing (PODC). 159--168.
30. Herlihy, M. 1991. Wait-free synchronization. ACM Trans. Prog. Lang. Syst. 13, 1, 124--149.
31. Hanckowiak, M., Karonski, M., and Panconesi, A. 2001. On the distributed complexity of computing maximal matchings. SIAM J. Discrete Math. 15, 1, 41--57.
32. Kor, L., Korman, A., and Peleg, D. 2011. Tight bounds for distributed MST verification. In Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science (STACS). 69--80.
33. Korman, A. and Kutten, S. 2007. Distributed verification of minimum spanning trees. Distrib. Comput. 20, 253--266.
34. Korman, A., Kutten, S., and Masuzawa, T. 2011a. Fast and compact self-stabilizing verification, computation, and fault detection of an MST. In Proceedings of the 30th ACM Symposium on Principles of Distributed Computing (PODC). 311--320.
35. Korman, A., Kutten, S., and Peleg, D. 2010. Proof labeling schemes. Distrib. Comput. 22, 215--233.
36. Korman, A., Sereni, J. S., and Viennot, L. 2011b. Toward more localized local algorithms: Removing assumptions concerning global knowledge. In Proceedings of the 30th ACM Symposium on Principles of Distributed Computing (PODC). 49--58.
37. Kuhn F. 2009. Weak graph colorings: distributed algorithms and applications. In Proceedings of the 21st ACM Symposium on Parallel Algorithms and Architectures (SPAA). 138--144.
38. Kuhn, F., Moscibroda, T., and Wattenhofer, R. 2004. What cannot be computed locally! In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC). 300--309.
39. Kutten, S. and Peleg, D. 1998. Fast distributed construction of small k-dominating sets and applications. J. Algor. 28, 1, 40--66.
40. Kuhn, F. and Wattenhofer, R. 2006. On the complexity of distributed graph coloring. In Proceedings of the 25th ACM Symposium on Principles of Distributed Computing (PODC). 7--15.
41. Lenzen, C., Oswald, Y. A., and Wattenhofer, R. 2008. What can be approximated locally?: Case study: Dominating sets in planar graphs. In Proceedings of the 20th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 46--54.
42. Linial, N. 1992. Locality in distributed graph algorithms. SIAM J. Comput. 21, 1, 193--201.
43. Lotker, Z., Patt-Shamir, B., and Rosen, A. 2009. Distributed approximate matching. SIAM J. Comput. 39, 2, 445--460.
44. Lotker, Z., Patt-Shamir, B., and Pettie, S. 2008. Improved distributed approximate matching. In Proceedings of the 20th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 129--136.
45. Luby, M. 1986. A simple parallel algorithm for the maximal independent set problem. SIAM J. Comput. 15, 1036--1053.
46. Naor, M. 1991. A lower bound on probabilistic algorithms for distributive ring coloring. SIAM J. Disc. Math, 4, 3, 409--412.
47. Naor, M. and Stockmeyer, L. 1995. What can be computed locally? SIAM J. Comput. 24, 6, 1259--1277.
48. Panconesi, A. and Srinivasan, A. 1996. On the complexity of distributed network decomposition. J. Algor. 20, 2, 356--374.
49. Peleg, D. 2000. Distributed Computing: A Locality-Sensitive Approach. SIAM.
50. Peleg, D. and Rubinovich, V. 2000. A near-tight lower bound on the time complexity of distributed minimum-weight spanning tree construction. SIAM J. Comput. 30, 5, 1427--1442.
51. Pettie, S. 2010. Distributed algorithms for ultrasparse spanners and linear size skeletons. Distrib. Comput. 22, 3, 147--166.
52. Schneider, J. and Wattenhofer, R. 2010. A new technique for distributed symmetry breaking. In Proceedings of the 29th ACM Symposium on Principles of Distributed Computing (PODC). 257--266.
53. Seinsche, D. 1974. On a property of the class of n-colorable graphs. J. Combinat. Theory, Ser. B, 16, 191--193.
54. Wattenhofer, M. and Wattenhofer, R. 2004. Distributed weighted matching. In Proceedings of the 18th Symposium on Distributed Computing (DISC). 335--348.

Index Terms

• Computer systems organization

  • Architectures

    • Distributed architectures

• Hardware

  • Hardware test

  • Robustness

• Mathematics of computing

  • Discrete mathematics

    • Graph theory

• Networks

  • Network protocols

    • Protocol correctness

      • Protocol testing and verification

• Software and its engineering

  • Software organization and properties

    • Software system structures

      • Distributed systems organizing principles

• Theory of computation

  • Computational complexity and cryptography

    • Complexity classes