{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T03:15:22Z","timestamp":1767928522711,"version":"3.49.0"},"publisher-location":"Cham","reference-count":31,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030719944","type":"print"},{"value":"9783030719951","type":"electronic"}],"license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,3,23]],"date-time":"2021-03-23T00:00:00Z","timestamp":1616457600000},"content-version":"vor","delay-in-days":81,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In rendez-vous protocols an arbitrarily large number of indistinguishable finite-state agents interact in pairs. The cut-off problem asks if there exists a number <jats:italic>B<\/jats:italic> such that all initial configurations of the protocol with at least <jats:italic>B<\/jats:italic> agents in a given initial state can reach a final configuration with all agents in a given final state. In a recent paper\u00a0[17], Horn and Sangnier prove that the cut-off problem is equivalent to the Petri net reachability problem for protocols with a leader, and in \n\n\"Image missing\"\n\nfor leaderless protocols. Further, for the special class of symmetric protocols they reduce these bounds to \n\n\"Image missing\"\n\nand \n\n\"Image missing\"\n\n, respectively. The problem of lowering these upper bounds or finding matching lower bounds is left open. We show that the cut-off problem is \n\n\"Image missing\"\n\n-complete for leaderless protocols, \n\n\"Image missing\"\n\n-complete for symmetric protocols with a leader, and in \n\n\"Image missing\"\n\nfor leaderless symmetric protocols, thereby solving all the problems left open in\u00a0[17].<\/jats:p>","DOI":"10.1007\/978-3-030-71995-1_3","type":"book-chapter","created":{"date-parts":[[2021,3,22]],"date-time":"2021-03-22T17:03:39Z","timestamp":1616432619000},"page":"42-61","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Finding Cut-Offs in Leaderless Rendez-Vous Protocols is Easy"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7258-5445","authenticated-orcid":false,"given":"A. R.","family":"Balasubramanian","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9862-4919","authenticated-orcid":false,"given":"Javier","family":"Esparza","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6660-5673","authenticated-orcid":false,"given":"Mikhail","family":"Raskin","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,3,23]]},"reference":[{"key":"3_CR1","unstructured":"Alla, H., David, R.: Continuous and hybrid Petri nets. J. Circuits Syst. Comput. 8(1), 159\u2013188 (1998)"},{"key":"3_CR2","doi-asserted-by":"publisher","unstructured":"Angluin, D., Aspnes, J., Diamadi, Z., Fischer, M.J., Peralta, R.: Computation in networks of passively mobile finite-state sensors. Distributed Computing 18(4), 235\u2013253 (2006). https:\/\/doi.org\/10.1007\/s00446-005-0138-3","DOI":"10.1007\/s00446-005-0138-3"},{"key":"3_CR3","doi-asserted-by":"publisher","unstructured":"Basler, G., Mazzucchi, M., Wahl, T., Kroening, D.: Symbolic counter abstraction for concurrent software. In: Bouajjani, A., Maler, O. (eds.) 21st International Conference on Computer Aided Verification, CAV 2009, Grenoble, France, June 26 - July 2, 2009, Proceedings. Lecture Notes in Computer Science, vol.\u00a05643, pp. 64\u201378. Springer (2009). https:\/\/doi.org\/10.1007\/978-3-642-02658-4_9","DOI":"10.1007\/978-3-642-02658-4_9"},{"key":"3_CR4","doi-asserted-by":"publisher","unstructured":"Bloem, R., Jacobs, S., Khalimov, A., Konnov, I., Rubin, S., Veith, H., Widder, J.: Decidability of Parameterized Verification. Synthesis Lectures on Distributed Computing Theory, Morgan & Claypool Publishers (2015).https:\/\/doi.org\/10.2200\/S00658ED1V01Y201508DCT013","DOI":"10.2200\/S00658ED1V01Y201508DCT013"},{"key":"3_CR5","doi-asserted-by":"crossref","unstructured":"Blondin, M.: The abc of Petri net reachability relaxations. ACM SIGLOG News 7(3) (2020)","DOI":"10.1145\/3436980.3436984"},{"key":"3_CR6","doi-asserted-by":"publisher","unstructured":"Czerwinski, W., Lasota, S., Lazic, R., Leroux, J., Mazowiecki, F.: The reachability problem for Petri nets is not elementary. In: Charikar, M., Cohen, E. (eds.) 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, Proceedings. pp. 24\u201333. ACM (2019). https:\/\/doi.org\/10.1145\/3313276.3316369","DOI":"10.1145\/3313276.3316369"},{"key":"3_CR7","unstructured":"Delzanno, G., Sangnier, A., Traverso, R., Zavattaro, G.: On the complexity of parameterized reachability in reconfigurable broadcast networks. In: FSTTCS. LIPIcs, vol.\u00a018, pp. 289\u2013300. Schloss Dagstuhl - Leibniz-Zentrumf\u00fcr Informatik (2012)"},{"key":"3_CR8","doi-asserted-by":"crossref","unstructured":"Emerson, E.A., Kahlon, V.: Model checking large-scale and parameterized resource allocation systems. In: TACAS. Lecture Notes in Computer Science, vol.\u00a02280, pp. 251\u2013265. Springer (2002)","DOI":"10.1007\/3-540-46002-0_18"},{"key":"3_CR9","doi-asserted-by":"crossref","unstructured":"Esparza, J.: Decidability and complexity of Petri net problems - an introduction. In: Petri Nets. Lecture Notes in Computer Science, vol.\u00a01491, pp. 374\u2013428. Springer (1996)","DOI":"10.1007\/3-540-65306-6_20"},{"key":"3_CR10","unstructured":"Esparza, J.: Parameterized verification of crowds of anonymous processes. In: Dependable Software Systems Engineering, NATO Science for Peace and Security Series - D: Information and Communication Security, vol.\u00a045, pp. 59\u201371. IOS Press (2016)"},{"key":"3_CR11","unstructured":"Esparza, J., Finkel, A., Mayr, R.: On the verification of broadcast protocols. In: LICS. pp. 352\u2013359. IEEE Computer Society (1999)"},{"key":"3_CR12","doi-asserted-by":"publisher","unstructured":"Esparza, J., Ganty, P., Leroux, J., Majumdar, R.: Verification of population protocols. Acta Informatica 54(2), 191\u2013215 (2017). https:\/\/doi.org\/10.1007\/s00236-016-0272-3","DOI":"10.1007\/s00236-016-0272-3"},{"key":"3_CR13","unstructured":"Esparza, J., Nielsen, M.: Decidability issues for Petri nets - a survey. J. Inf. Process. Cybern. 30(3), 143\u2013160 (1994)"},{"key":"3_CR14","unstructured":"Fraca, E., Haddad, S.: Complexity analysis of continuous Petri nets. Fundam. Informaticae 137(1), 1\u201328 (2015)"},{"key":"3_CR15","doi-asserted-by":"publisher","unstructured":"German, S.M., Sistla, A.P.: Reasoning about systems with many processes. Journal of the ACM 39(3), 675\u2013735 (1992). https:\/\/doi.org\/10.1145\/146637.146681","DOI":"10.1145\/146637.146681"},{"key":"3_CR16","doi-asserted-by":"crossref","unstructured":"Gmeiner, A., Konnov, I., Schmid, U., Veith, H., Widder, J.: Tutorial on parameterized model checking of fault-tolerant distributed algorithms. In: SFM. Lecture Notes in Computer Science, vol.\u00a08483, pp. 122\u2013171. Springer (2014)","DOI":"10.1007\/978-3-319-07317-0_4"},{"key":"3_CR17","unstructured":"Horn, F., Sangnier, A.: Deciding the existence of cut-off in parameterized rendez-vous networks. In: CONCUR. LIPIcs, vol.\u00a0171, pp. 46:1\u201346:16. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2020)"},{"key":"3_CR18","doi-asserted-by":"publisher","unstructured":"Kaiser, A., Kroening, D., Wahl, T.: Dynamic cutoff detection in parameterized concurrent programs. In: Touili, T., Cook, B., Jackson, P.B. (eds.) 22nd International Conference on Computer Aided Verification, CAV 2010, Edinburgh, UK, July 15-19, 2010, Proceedings. Lecture Notes in Computer Science, vol.\u00a06174, pp. 645\u2013659. Springer (2010). https:\/\/doi.org\/10.1007\/978-3-642-14295-6_55","DOI":"10.1007\/978-3-642-14295-6_55"},{"key":"3_CR19","unstructured":"Kannan, R., Bachem, A.: Polynomial algorithms for computing the Smith and Hermite normal forms of an integer matrix. SIAM J. Comput. 8(4), 499\u2013507 (1979)"},{"key":"3_CR20","doi-asserted-by":"crossref","unstructured":"Kannan, R., Monma, C.L.: On the computational complexity of integer programming problems. In: Henn, R., Korte, B., Oettli, W. (eds.) Optimization and Operations Research. pp. 161\u2013172. Springer Berlin Heidelberg, Berlin, Heidelberg (1978)","DOI":"10.1007\/978-3-642-95322-4_17"},{"key":"3_CR21","doi-asserted-by":"crossref","unstructured":"Ladner, R.E.: The circuit value problem is Log Space complete for P. SIGACT News 7(1), 18\u201320 (1975)","DOI":"10.1145\/990518.990519"},{"key":"3_CR22","doi-asserted-by":"crossref","unstructured":"Leroux, J., Schmitz, S.: Reachability in vector addition systems is primitive-recursive in fixed dimension. In: LICS. pp. 1\u201313. IEEE (2019)","DOI":"10.1109\/LICS.2019.8785796"},{"key":"3_CR23","doi-asserted-by":"publisher","unstructured":"Mulmuley, K.: A fast parallel algorithm to compute the rank of a matrix over an arbitrary field. Comb. 7(1), 101\u2013104 (1987). https:\/\/doi.org\/10.1007\/BF02579205","DOI":"10.1007\/BF02579205"},{"key":"3_CR24","doi-asserted-by":"crossref","unstructured":"Murata, T.: Petri nets: Properties, analysis and applications. Proceedings of the IEEE 77(4), 541\u2013580 (1989)","DOI":"10.1109\/5.24143"},{"key":"3_CR25","doi-asserted-by":"publisher","unstructured":"Navlakha, S., Bar-Joseph, Z.: Distributed information processing in biological and computational systems. Communications of the ACM 58(1), 94\u2013102 (2015). https:\/\/doi.org\/10.1145\/2678280","DOI":"10.1145\/2678280"},{"key":"3_CR26","doi-asserted-by":"publisher","unstructured":"Papadimitriou, C.H.: On the complexity of integer programming. J. ACM 28(4), 765\u2013768 (1981). https:\/\/doi.org\/10.1145\/322276.322287","DOI":"10.1145\/322276.322287"},{"key":"3_CR27","unstructured":"Papadimitriou, C.H.: Computational complexity. Academic Internet Publ. (2007)"},{"key":"3_CR28","doi-asserted-by":"crossref","unstructured":"Pnueli, A., Xu, J., Zuck, L.D.: Liveness with (0, 1, infty)-counter abstraction. In: CAV. Lecture Notes in Computer Science, vol.\u00a02404, pp. 107\u2013122. Springer (2002)","DOI":"10.1007\/3-540-45657-0_9"},{"key":"3_CR29","doi-asserted-by":"crossref","unstructured":"Pohst, M.E., Zassenhaus, H.: Algorithmic algebraic number theory, Encyclopedia of mathematics and its applications, vol.\u00a030. Cambridge University Press (1989)","DOI":"10.1017\/CBO9780511661952"},{"key":"3_CR30","unstructured":"Recalde, L., Haddad, S., Su\u00e1rez, M.S.: Continuous Petri nets: Expressive power and decidability issues. Int. J. Found. Comput. Sci. 21(2), 235\u2013256 (2010)"},{"key":"3_CR31","unstructured":"Soloveichik, D., Cook, M., Winfree, E., Bruck, J.: Computation with finite stochastic chemical reaction networks. Nat. Comput. 7(4), 615\u2013633 (2008)"}],"container-title":["Lecture Notes in Computer Science","Foundations of Software Science and Computation Structures"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-71995-1_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,22]],"date-time":"2021-03-22T17:05:32Z","timestamp":1616432732000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-71995-1_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030719944","9783030719951"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-71995-1_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"23 March 2021","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"FOSSACS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Foundations of Software Science and Computation Structures","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Luxembourg City","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Luxembourg","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2021","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27 March 2021","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"1 April 2021","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"fossacs2021","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/etaps.org\/2021\/fossacs","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"88","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"28","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"32% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3,2","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"The conference changed to an online format due to the COVID-19 pandemic","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}