{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T11:36:28Z","timestamp":1770896188305,"version":"3.50.1"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2019,6,13]],"date-time":"2019-06-13T00:00:00Z","timestamp":1560384000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,6,13]],"date-time":"2019-06-13T00:00:00Z","timestamp":1560384000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-16-CE40-0023"],"award-info":[{"award-number":["ANR-16-CE40-0023"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100012950","name":"Institut national de recherche en informatique et en automatique","doi-asserted-by":"publisher","award":["GANG"],"award-info":[{"award-number":["GANG"]}],"id":[{"id":"10.13039\/100012950","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-16-CE25-0009"],"award-info":[{"award-number":["ANR-16-CE25-0009"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-10-IDEX-03-02"],"award-info":[{"award-number":["ANR-10-IDEX-03-02"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["2018-03899"],"award-info":[{"award-number":["2018-03899"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2020,4]]},"DOI":"10.1007\/s00446-019-00355-1","type":"journal-article","created":{"date-parts":[[2019,6,13]],"date-time":"2019-06-13T12:02:22Z","timestamp":1560427342000},"page":"169-187","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Deciding and verifying network properties locally with few output bits"],"prefix":"10.1007","volume":"33","author":[{"given":"Heger","family":"Arfaoui","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4534-4803","authenticated-orcid":false,"given":"Pierre","family":"Fraigniaud","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Ilcinkas","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1362-0359","authenticated-orcid":false,"given":"Fabien","family":"Mathieu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrzej","family":"Pelc","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,6,13]]},"reference":[{"issue":"1\u20132","key":"355_CR1","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1016\/S0304-3975(96)00286-1","volume":"186","author":"Y Afek","year":"1997","unstructured":"Afek, Y., Kutten, S., Yung, M.: The local detection paradigm and its applications to self stabilization. Theor. Comput. Sci. 186(1\u20132), 199\u2013230 (1997)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"355_CR2","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1002\/jgt.3190180406","volume":"18","author":"N Alon","year":"1994","unstructured":"Alon, N.: Subdivided graphs have linear ramsey numbers. J. Graph Theory 18(4), 343\u2013347 (1994)","journal-title":"J. Graph Theory"},{"key":"355_CR3","doi-asserted-by":"crossref","unstructured":"Angluin, D.: Local and global properties in networks of processors (Extended Abstract). In: Proceedings of 12th Annual ACM Symposium on Theory of Computing (STOC), pp. 82\u201393 (1980)","DOI":"10.1145\/800141.804655"},{"key":"355_CR4","doi-asserted-by":"crossref","unstructured":"Arfaoui, H., Fraigniaud, P., Ilcinkas, D., Mathieu, F.: Distributedly testing cycle-freeness. In: Proceedings of 40th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), pp. 15\u201328 (2014)","DOI":"10.1007\/978-3-319-12340-0_2"},{"key":"355_CR5","doi-asserted-by":"crossref","unstructured":"Arfaoui, H., Fraigniaud, P., Pelc, A.: Local decision and verification with bounded-size outputs. In: Proceedings of 15th Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), pp. 133\u2013147 (2013)","DOI":"10.1007\/978-3-319-03089-0_10"},{"key":"355_CR6","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Patt-Shamir, B., Varghese G., Dolev, S.: Self-stabilization by local checking and global reset. In: Proceedings of Workshop on Distributed Algorithms and Graphs (WDAG), Springer, LNCS 857, pp. 326\u2013339 (1994)","DOI":"10.1007\/BFb0020443"},{"key":"355_CR7","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1016\/j.jcss.2018.05.004","volume":"97","author":"A Balliu","year":"2018","unstructured":"Balliu, A., D\u2019Angelo, G., Fraigniaud, P., Olivetti, D.: What can be verified locally? J. Comput. Syst. Sci. 97, 106\u2013120 (2018)","journal-title":"J. Comput. Syst. Sci."},{"key":"355_CR8","doi-asserted-by":"crossref","unstructured":"Becker, F., Kosowski, A., Nisse, N., Rapaport, I., Suchan,K.: Allowing each node to communicate only once in a distributed system: shared whiteboard models. In: Proceedings of 24th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 11\u201317 (2012)","DOI":"10.1145\/2312005.2312008"},{"key":"355_CR9","doi-asserted-by":"crossref","unstructured":"Becker, F., Matamala, M., Nisse, N., Rapaport, I., Suchan, K., Todinca, I.: Adding a referee to an interconnection network: What can(not) be computed in one round. In: Proceedings of 25th IEEE International Symposium on Parallel and Distributed Proceedings (IPDPS), pp. 508\u2013514 (2011)","DOI":"10.1109\/IPDPS.2011.55"},{"key":"355_CR10","unstructured":"Bonakdarpour, B., Fraigniaud, P., Rajsbaum, S., Travers, C.: Challenges in fault-tolerant distributed runtime verification. In: proceedings of 7th International Symposium on Leveraging Applications of Formal Methods, Verification and Validation"},{"key":"355_CR11","doi-asserted-by":"crossref","unstructured":"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: Proceedings of 43rd ACM Symposium on Theory of Computing (STOC), (2011)","DOI":"10.1145\/1993636.1993686"},{"issue":"6","key":"355_CR12","doi-asserted-by":"publisher","first-page":"447","DOI":"10.1007\/s002360050180","volume":"36","author":"S Dolev","year":"1999","unstructured":"Dolev, S., Gouda, M.G., Schneider, M.: Memory requirements for silent stabilization. Acta Inf. 36(6), 447\u2013462 (1999)","journal-title":"Acta Inf."},{"issue":"3\u20134","key":"355_CR13","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/BF01895716","volume":"14","author":"P Erd\u0151s","year":"1963","unstructured":"Erd\u0151s, P., R\u00e9nyi, A.: Asymmetric graphs. Acta Math. Acad. Sci. Hung. 14(3\u20134), 295\u2013315 (1963)","journal-title":"Acta Math. Acad. Sci. Hung."},{"key":"355_CR14","unstructured":"Even, G., Fischer, O., Fraigniaud, P., Gonen, T., Levi, R., Medina, M., Montealegre, P., Olivetti, D., Oshman, R., Rapaport, I., Todinca,I.: Three notes on distributed property testing. In: Proceedings on 31st International Symposium on Distributed Computing (DISC), pp. 15:1\u201315:30 (2017)"},{"key":"355_CR15","doi-asserted-by":"crossref","unstructured":"Feuilloley, L., Fraigniaud, P.: Randomized local network computing. In: Proceedings of 27th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 340\u2013349 (2015)","DOI":"10.1145\/2755573.2755596"},{"key":"355_CR16","unstructured":"Feuilloley, L., Fraigniaud, P.: Survey of distributed decision. Bull. EATCS 119, 1\u201325 (2016)"},{"key":"355_CR17","doi-asserted-by":"crossref","unstructured":"Fraigniaud,P., G\u00f6\u00f6s, M., Korman, A., Suomela, J.: What can be decided locally without identifiers? In: Proceedings on 32nd ACM Symposium on Principles of Distributed Computing (PODC), pp. 157\u2013165 (2013)","DOI":"10.1145\/2484239.2484264"},{"key":"355_CR18","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P., Halld\u00f3rsson, M.M., Korman, A.: On the impact of identifiers on local decision. In: Proceedings on 16th International Conference on Principles of Distributed Systems (OPODIS), pp. 224\u2013238 (2012)","DOI":"10.1007\/978-3-642-35476-2_16"},{"key":"355_CR19","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P., Hirvonen, J., Suomela, J.: Node labels in local decision. In: Proceedings of 22nd International Colloquium on Structural Information and Communication Complexity (SIROCCO), pp. 31\u201345 (2015)","DOI":"10.1007\/978-3-319-25258-2_3"},{"key":"355_CR20","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P., Korman, A., Parter, M., Peleg, D.: Randomized distributed decision. In: Proceedings of 26th International Symposium on Distributed Computing (DISC), pp. 371\u2013385 (2012)","DOI":"10.1007\/978-3-642-33651-5_26"},{"issue":"5","key":"355_CR21","doi-asserted-by":"publisher","first-page":"35:1","DOI":"10.1145\/2499228","volume":"60","author":"P Fraigniaud","year":"2013","unstructured":"Fraigniaud, P., Korman, A., Peleg, D.: Towards a complexity theory for local distributed computing. J. ACM 60(5), 35:1\u201335:6 (2013)","journal-title":"J. ACM"},{"key":"355_CR22","unstructured":"Fraigniaud, P., Montealegre, P., Oshman, R., Rapaport, I., Todinca, I.: Lower bounds for single-interaction distributed Arthur\u2013Merlin and Merlin\u2013Arthur protocols. In: Proceedings of 26th International Colloquium on Structural Information and Communication Complexity (SIROCCO) (2019)"},{"key":"355_CR23","doi-asserted-by":"crossref","unstructured":"G\u00f6\u00f6s M., Suomela, J.: Locally checkable proofs. In: Proceedings of 30th ACM Symposium on Principles of Distributed Computing (PODC), pp. 159\u2013168 (2011)","DOI":"10.1145\/1993806.1993829"},{"key":"355_CR24","unstructured":"Itkis, G., Levin, L. A.: Fast and lean self-stabilizing asynchronous protocols. In: Proceedings of 35th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 226\u2013239 (1994)"},{"key":"355_CR25","volume-title":"Protocols and Architectures for Wireless Sensor Networks","author":"H Karl","year":"2007","unstructured":"Karl, H., Willig, A.: Protocols and Architectures for Wireless Sensor Networks. Wiley, Hoboken (2007)"},{"key":"355_CR26","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/BF02278852","volume":"7","author":"S Katz","year":"1993","unstructured":"Katz, S., Perry, K.: Self-stabilizing extensions to for message-passing systems. Distrib. Comput. 7, 17\u201326 (1993)","journal-title":"Distrib. Comput."},{"key":"355_CR27","doi-asserted-by":"crossref","unstructured":"Kol, G., Oshman, R., Saxena, R.R.: Interactive distributed proofs. In: 37th ACM Symposium on Principles of Distributed Computing (PODC), pp. 255\u2013264 (2018)","DOI":"10.1145\/3212734.3212771"},{"issue":"4","key":"355_CR28","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1007\/s00446-010-0095-3","volume":"22","author":"A Korman","year":"2010","unstructured":"Korman, A., Kutten, S., Peleg, D.: Proof labeling schemes. Distrib. Comput. 22(4), 215\u2013233 (2010)","journal-title":"Distrib. Comput."},{"key":"355_CR29","volume-title":"Communication Complexity","author":"E Kushilevitz","year":"1997","unstructured":"Kushilevitz, E., Nisan, N.: Communication Complexity. Cambridge University Press, Cambridge (1997)"},{"issue":"1","key":"355_CR30","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1006\/inco.1995.1056","volume":"118","author":"I Litovsky","year":"1995","unstructured":"Litovsky, I., Metivier, Y., Zielonka, W.: On the recognition of families of graphs with local computations. Inf. Comput. 118(1), 110\u2013119 (1995)","journal-title":"Inf. Comput."},{"key":"355_CR31","unstructured":"Naor, Moni, Parter, Merav, Yogev, Eylon.: The power of distributed verifiers in interactive proofs, CoRR, \narXiv:1812.10917\n\n (2018)"},{"issue":"6","key":"355_CR32","doi-asserted-by":"publisher","first-page":"1259","DOI":"10.1137\/S0097539793254571","volume":"24","author":"M Naor","year":"1995","unstructured":"Naor, M., Stockmeyer, L.: What can be computed locally? SIAM J. Comput. 24(6), 1259\u20131277 (1995)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"355_CR33","doi-asserted-by":"publisher","first-page":"1","DOI":"10.2307\/2372087","volume":"71","author":"BH Neumann","year":"1949","unstructured":"Neumann, B.H.: On ordered groups. Am. J. Math. 71(1), 1\u201318 (1949)","journal-title":"Am. J. Math."},{"key":"355_CR34","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719772","volume-title":"Distributed Computing: A Locality-Sensitive Approach","author":"D Peleg","year":"2000","unstructured":"Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. SIAM, Philadelphia (2000)"},{"issue":"1","key":"355_CR35","doi-asserted-by":"publisher","first-page":"264","DOI":"10.1112\/plms\/s2-30.1.264","volume":"2","author":"FP Ramsey","year":"1930","unstructured":"Ramsey, F.P.: On a problem of formal logic. Proc. Lond. Math. Soc. 2(1), 264\u2013286 (1930)","journal-title":"Proc. Lond. Math. Soc."},{"key":"355_CR36","doi-asserted-by":"crossref","unstructured":"Yao, A.C.: Some complexity questions related to distributed computing. In: Proceedings of 11th ACM Symposium on Theory of Computing (STOC), pp. 209\u2013213 (1979)","DOI":"10.1145\/800135.804414"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-019-00355-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00446-019-00355-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-019-00355-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,6,11]],"date-time":"2020-06-11T23:15:55Z","timestamp":1591917355000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00446-019-00355-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,13]]},"references-count":36,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,4]]}},"alternative-id":["355"],"URL":"https:\/\/doi.org\/10.1007\/s00446-019-00355-1","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"value":"0178-2770","type":"print"},{"value":"1432-0452","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,6,13]]},"assertion":[{"value":"19 October 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 May 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 June 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}