{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T16:56:18Z","timestamp":1780073778910,"version":"3.54.0"},"reference-count":54,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2013,10,1]],"date-time":"2013-10-01T00:00:00Z","timestamp":1380585600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"name":"INRIA project GANG"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2013,10]]},"abstract":"\n A central theme in distributed network algorithms concerns understanding and coping with the issue of\n locality<\/jats:italic>\n . 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\n distributed decision problems<\/jats:italic>\n . 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.\n <\/jats:p>\n \n We consider the standard LOCAL model of computation and define LD(\n t<\/jats:italic>\n ) (for\n local decision<\/jats:italic>\n ) as the class of decision problems that can be solved in\n t<\/jats:italic>\n 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(\n t<\/jats:italic>\n ,\n p<\/jats:italic>\n ,\n q<\/jats:italic>\n ), containing all languages for which there exists a randomized algorithm that runs in\n t<\/jats:italic>\n rounds, accepts correct instances with probability at least\n p<\/jats:italic>\n , and rejects incorrect ones with probability at least\n q<\/jats:italic>\n . We show that\n p<\/jats:italic>\n 2<\/jats:sup>\n + q = 1 is a threshold for the containment of LD(\n t<\/jats:italic>\n ) in BPLD(\n t<\/jats:italic>\n ,\n p<\/jats:italic>\n ,\n q<\/jats:italic>\n ). More precisely, we show that there exists a language that does not belong to LD(\n t<\/jats:italic>\n ) for any\n t<\/jats:italic>\n =\n o<\/jats:italic>\n (\n n<\/jats:italic>\n ) but does belong to BPLD(\n 0<\/jats:italic>\n ,\n p<\/jats:italic>\n ,\n q<\/jats:italic>\n ) for any\n p<\/jats:italic>\n ,\n q<\/jats:italic>\n \u2208 (0,1) such that\n p<\/jats:italic>\n 2<\/jats:sup>\n + q \u2264 1. On the other hand, we show that, restricted to hereditary languages, BPLD(\n t<\/jats:italic>\n ,\n p<\/jats:italic>\n ,\n q<\/jats:italic>\n )=LD(\n O<\/jats:italic>\n (\n t<\/jats:italic>\n )), for any function\n t<\/jats:italic>\n , and any\n p<\/jats:italic>\n ,\n q<\/jats:italic>\n \u2208 (0,1) such that\n p<\/jats:italic>\n 2<\/jats:sup>\n + q > 1.\n <\/jats:p>\n \n 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\n in constant time<\/jats:italic>\n . Finally, we introduce the notion of local reduction, and establish a couple of completeness results.\n <\/jats:p>","DOI":"10.1145\/2499228","type":"journal-article","created":{"date-parts":[[2013,10,23]],"date-time":"2013-10-23T15:29:17Z","timestamp":1382542157000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":83,"title":["Towards a complexity theory for local distributed computing"],"prefix":"10.1145","volume":"60","author":[{"given":"Pierre","family":"Fraigniaud","sequence":"first","affiliation":[{"name":"CNRS and University Paris Diderot, Paris Cedex"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Amos","family":"Korman","sequence":"additional","affiliation":[{"name":"CNRS and University Paris Diderot, Paris Cedex"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David","family":"Peleg","sequence":"additional","affiliation":[{"name":"The Weizmann Institute of Science, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2013,10,28]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(96)00286-1"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90019-2"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 12th ACM-SIAM Symposium on Discrete Algorithms (SODA). 883--894","author":"Amit A.","unstructured":"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 . 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."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/200836.200869"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1991.185378"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/645951.675485"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536432"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.60"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/226643.226647"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/234533.234549"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993686"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 23rd Symposium on Distributed Computing (DISC), 176--190","author":"Derbel B.","unstructured":"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 . 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."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/361179.361202"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002360050180"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.07.002"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-005-0147-2"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3149.214121"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2009.07.002"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 34th Colloquium on Automata, Languages and Programming (ICALP). 231--242","author":"Fraigniaud P.","unstructured":"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 . 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."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2484239.2484264"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the 16th International Conference on Principles of Distributed Systems (OPODIS). 224--238","author":"Fraigniaud P.","unstructured":"Fraigniaud , P. , Halld\u00f3rsson , 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 . Fraigniaud, P., Halld\u00f3rsson, 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."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1248377.1248402"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33651-5_26"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.17"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the 25th International Symposium on Distributed Computing (DISC). 333--347","author":"Fraigniaud P.","unstructured":"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 . 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."},{"key":"e_1_2_1_26_1","unstructured":"Fraigniaud P. Rajsbaum S. and Travers C. 2012c. Universal distributed checkers and orientation-detection tasks. Submitted. Fraigniaud P. Rajsbaum S. and Travers C. 2012c. Universal distributed checkers and orientation-detection tasks. Submitted."},{"key":"e_1_2_1_27_1","volume-title":"ed","author":"Goldreich O.","year":"2010","unstructured":"Goldreich , O. ed . 2010 . Property Testing\u2014Current Research and Surveys. Lecture Notes in Computer Science, vol. 6390 , Springer . Goldreich, O. ed. 2010. Property Testing\u2014Current Research and Surveys. Lecture Notes in Computer Science, vol. 6390, Springer."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0078-7"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993806.1993829"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/114005.102808"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480100373121"},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science (STACS). 69--80","author":"Kor L.","unstructured":"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 . 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."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-007-0025-1"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993806.1993866"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-010-0095-3"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993806.1993814"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1583991.1584032"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1011767.1011811"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1998.0929"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1146381.1146387"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1378533.1378540"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1137\/0221015"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1137\/080714403"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/1378533.1378558"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215074"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1137\/0404036"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793254571"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0017"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.5555\/355459"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700369740"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-009-0091-7"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835698.1835760"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(74)90063-X"},{"key":"e_1_2_1_54_1","volume-title":"Proceedings of the 18th Symposium on Distributed Computing (DISC). 335--348","author":"Wattenhofer M.","unstructured":"Wattenhofer , M. and Wattenhofer , R . 2004. Distributed weighted matching . In Proceedings of the 18th Symposium on Distributed Computing (DISC). 335--348 . Wattenhofer, M. and Wattenhofer, R. 2004. Distributed weighted matching. In Proceedings of the 18th Symposium on Distributed Computing (DISC). 335--348."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2499228","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2499228","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:35:50Z","timestamp":1750235750000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2499228"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,10]]},"references-count":54,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2013,10]]}},"alternative-id":["10.1145\/2499228"],"URL":"https:\/\/doi.org\/10.1145\/2499228","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,10]]},"assertion":[{"value":"2012-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-10-28","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}