{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:32:12Z","timestamp":1750221132208,"version":"3.41.0"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2019,9,30]],"date-time":"2019-09-30T00:00:00Z","timestamp":1569801600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100002341","name":"Academy of Finland","doi-asserted-by":"publisher","award":["285721"],"award-info":[{"award-number":["285721"]}],"id":[{"id":"10.13039\/501100002341","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100008952","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["DESCARTES"],"award-info":[{"award-number":["DESCARTES"]}],"id":[{"id":"10.13039\/501100008952","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Parallel Comput."],"published-print":{"date-parts":[[2019,9,30]]},"abstract":"<jats:p>\n            Distributed property testing in networks has been introduced by Brakerski and Patt-Shamir [6], with the objective of detecting the presence of large dense sub-networks in a distributed manner. Recently, Censor-Hillel et al. [7] have revisited this notion and formalized it in a broader context. In particular, they have shown how to detect 3-cycles in a constant number of rounds by a distributed algorithm. In a follow-up work, Fraigniaud et al. [21] have shown how to detect 4-cycles in a constant number of rounds as well. However, the techniques in these latter works were shown not to generalize to larger cycles\n            <jats:italic>C<\/jats:italic>\n            <jats:sub>\n              <jats:italic>k<\/jats:italic>\n            <\/jats:sub>\n            with\n            <jats:italic>k<\/jats:italic>\n            \u2265 5. In this article, we completely settle the problem of cycle detection by establishing the following result: For every\n            <jats:italic>k<\/jats:italic>\n            \u2265 3, there exists a distributed property testing algorithm for\n            <jats:italic>C<\/jats:italic>\n            <jats:sub>\n              <jats:italic>k<\/jats:italic>\n            <\/jats:sub>\n            -freeness, performing in a constant number of rounds. All these results hold in the classical congest model for distributed network computing. Our algorithm is 1-sided error. Its round-complexity is\n            <jats:italic>O<\/jats:italic>\n            (1\u03f5) where \u03f5 \u2208 (0,1) is the property-testing parameter measuring the gap between legal and illegal instances.\n          <\/jats:p>","DOI":"10.1145\/3322811","type":"journal-article","created":{"date-parts":[[2019,10,15]],"date-time":"2019-10-15T16:35:58Z","timestamp":1571157358000},"page":"1-20","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["Distributed Detection of Cycles"],"prefix":"10.1145","volume":"6","author":[{"given":"Pierre","family":"Fraigniaud","sequence":"first","affiliation":[{"name":"CNRS and University Paris Diderot, Paris, France"}]},{"given":"Dennis","family":"Olivetti","sequence":"additional","affiliation":[{"name":"Aalto University, Konemiehentie, Espoo, Finland"}]}],"member":"320","published-online":{"date-parts":[[2019,10,15]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004930070001"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/07067917X"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548306007759"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science (STACS\u201917)","author":"Balliu Alkida","year":"2017","unstructured":"Alkida Balliu , Gianlorenzo D\u2019Angelo , Pierre Fraigniaud , and Dennis Olivetti . 2017 . What can be verified locally? In Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science (STACS\u201917) . Alkida Balliu, Gianlorenzo D\u2019Angelo, Pierre Fraigniaud, and Dennis Olivetti. 2017. What can be verified locally? In Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science (STACS\u201917)."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.706047"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-011-0132-x"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53426-7_4"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1622"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1063\/1.1454355"},{"key":"e_1_2_1_10_1","volume-title":"Graph removal lemmas. Retrieved from CoRR abs\/1211.3487","author":"Conlon David","year":"2012","unstructured":"David Conlon and Jacob Fox . 2012. Graph removal lemmas. Retrieved from CoRR abs\/1211.3487 ( 2012 ). David Conlon and Jacob Fox. 2012. Graph removal lemmas. Retrieved from CoRR abs\/1211.3487 (2012)."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20462"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2611462.2611478"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01788085"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.2307\/2311408"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 31st International Symposium on Distributed Computing (DISC\u201917)","author":"Even Guy","year":"2017","unstructured":"Guy Even , Orr Fischer , Pierre Fraigniaud , Tzlil Gonen , Reut Levi , Moti Medina , Pedro Montealegre , Dennis Olivetti , Rotem Oshman , Ivan Rapaport , and Ioan Todinca . 2017 . Three notes on distributed property testing . In Proceedings of the 31st International Symposium on Distributed Computing (DISC\u201917) . 15:1--15:30. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.DISC.2017.15 10.4230\/LIPIcs.DISC.2017.15 Guy Even, Orr Fischer, Pierre Fraigniaud, Tzlil Gonen, Reut Levi, Moti Medina, Pedro Montealegre, Dennis Olivetti, Rotem Oshman, Ivan Rapaport, and Ioan Todinca. 2017. Three notes on distributed property testing. In Proceedings of the 31st International Symposium on Distributed Computing (DISC\u201917). 15:1--15:30. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.DISC.2017.15"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2755573.2755596"},{"key":"e_1_2_1_17_1","first-page":"41","article-title":"Survey of distributed decision","volume":"119","author":"Feuilloley Laurent","year":"2016","unstructured":"Laurent Feuilloley and Pierre Fraigniaud . 2016 . Survey of distributed decision . Bull. EATCS 119 (2016), 41 -- 65 . Laurent Feuilloley and Pierre Fraigniaud. 2016. Survey of distributed decision. Bull. EATCS 119 (2016), 41--65.","journal-title":"Bull. EATCS"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP\u201916)","author":"Feuilloley Laurent","year":"2016","unstructured":"Laurent Feuilloley , Pierre Fraigniaud , and Juho Hirvonen . 2016 . A hierarchy of local decision . In Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP\u201916) . 118:1--118:15. Laurent Feuilloley, Pierre Fraigniaud, and Juho Hirvonen. 2016. A hierarchy of local decision. In Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP\u201916). 118:1--118:15."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-014-0211-x"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2499228"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53426-7_25"},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","unstructured":"Oded Goldreich (Ed.). 2010. Property Testing\u2014Current Research and Surveys. Vol. LNCS 6390. Springer.  Oded Goldreich (Ed.). 2010. Property Testing\u2014Current Research and Surveys. Vol. LNCS 6390. Springer.","DOI":"10.1007\/978-3-642-16367-8"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0078-7"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10078"},{"key":"e_1_2_1_25_1","first-page":"1","article-title":"Locally checkable proofs in distributed computing","volume":"12","author":"G\u00f6\u00f6s Mika","year":"2016","unstructured":"Mika G\u00f6\u00f6s and Jukka Suomela . 2016 . Locally checkable proofs in distributed computing . Theor. Comput. 12 , 1 (2016), 1 -- 33 . Mika G\u00f6\u00f6s and Jukka Suomela. 2016. Locally checkable proofs in distributed computing. Theor. Comput. 12, 1 (2016), 1--33.","journal-title":"Theor. Comput."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-010-0095-3"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-0208(08)73110-4"},{"volume-title":"Proceedings of the 19th ACM Symposium on Theory of Computing. 345--354","author":"Mulmuley Ketan","key":"e_1_2_1_28_1","unstructured":"Ketan Mulmuley , Umesh V. Vazirani , and Vijay V. Vazirani . 1987. Matching is as easy as matrix inversion . In Proceedings of the 19th ACM Symposium on Theory of Computing. 345--354 . DOI:https:\/\/doi.org\/10.1145\/28395.383347 10.1145\/28395.383347 Ketan Mulmuley, Umesh V. Vazirani, and Vijay V. Vazirani. 1987. Matching is as easy as matrix inversion. In Proceedings of the 19th ACM Symposium on Theory of Computing. 345--354. DOI:https:\/\/doi.org\/10.1145\/28395.383347"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793254571"},{"key":"e_1_2_1_30_1","volume-title":"Hadjicostis","author":"Oliva Gabriele","year":"2016","unstructured":"Gabriele Oliva , Roberto Setola , Luigi Glielmo , and Christoforos N . Hadjicostis . 2016 . Distributed cycle detection and removal. IEEE Trans. Cont. Netw. Syst. PP , 99 (2016). Gabriele Oliva, Roberto Setola, Luigi Glielmo, and Christoforos N. Hadjicostis. 2016. Distributed cycle detection and removal. IEEE Trans. Cont. Netw. Syst. PP, 99 (2016)."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719772"},{"volume-title":"Proceedings of Simp\u00f3sio Brasileiro de Pesquisa Operacional (SBPO\u201915)","author":"Rocha Rodrigo Caetano","key":"e_1_2_1_32_1","unstructured":"Rodrigo Caetano Rocha and Bhalchandra D. Thatte . 2015. Distributed cycle detection in large-scale sparse graphs . In Proceedings of Simp\u00f3sio Brasileiro de Pesquisa Operacional (SBPO\u201915) . 1--11. Rodrigo Caetano Rocha and Bhalchandra D. Thatte. 2015. Distributed cycle detection in large-scale sparse graphs. In Proceedings of Simp\u00f3sio Brasileiro de Pesquisa Operacional (SBPO\u201915). 1--11."}],"container-title":["ACM Transactions on Parallel Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3322811","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3322811","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:02:26Z","timestamp":1750208546000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3322811"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,9,30]]},"references-count":32,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,9,30]]}},"alternative-id":["10.1145\/3322811"],"URL":"https:\/\/doi.org\/10.1145\/3322811","relation":{},"ISSN":["2329-4949","2329-4957"],"issn-type":[{"type":"print","value":"2329-4949"},{"type":"electronic","value":"2329-4957"}],"subject":[],"published":{"date-parts":[[2019,9,30]]},"assertion":[{"value":"2017-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-10-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}