{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,1]],"date-time":"2026-10-01T00:17:35Z","timestamp":1790813855013,"version":"4.1.0"},"reference-count":0,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>In rendez-vous protocols an arbitrarily large number of indistinguishable\nfinite-state agents interact in pairs. The cut-off problem asks if there exists\na number $B$ such that all initial configurations of the protocol with at least\n$B$ agents in a given initial state can reach a final configuration with all\nagents in a given final state. In a recent paper (Horn and Sangnier, CONCUR\n2020), Horn and Sangnier proved that the cut-off problem is decidable (and at\nleast as hard as the Petri net reachability problem) for protocols with a\nleader, and in EXPSPACE for leaderless protocols. Further, for the special\nclass of symmetric protocols they reduce these bounds to PSPACE and NP,\nrespectively. The problem of lowering these upper bounds or finding matching\nlower bounds was left open. We show that the cut-off problem is P-complete for\nleaderless protocols and in NC for leaderless symmetric protocols. Further, we\nalso consider a variant of the cut-off problem suggested in (Horn and Sangnier,\nCONCUR 2020), which we call the bounded-loss cut-off problem and prove that\nthis problem is P-complete for leaderless protocols and NL-complete for\nleaderless symmetric protocols. Finally, by reusing some of the techniques\napplied for the analysis of leaderless protocols, we show that the cut-off\nproblem for symmetric protocols with a leader is NP-complete, thereby improving\nupon all the elementary upper bounds of (Horn and Sangnier, CONCUR 2020).<\/jats:p>","DOI":"10.46298\/lmcs-19(4:2)2023","type":"journal-article","created":{"date-parts":[[2023,10,12]],"date-time":"2023-10-12T15:15:08Z","timestamp":1697123708000},"source":"Crossref","is-referenced-by-count":2,"title":["Finding Cut-Offs in Leaderless Rendez-Vous Protocols is Easy"],"prefix":"10.46298","volume":"Volume 19, Issue 4","author":[{"given":"A. R.","family":"Balasubramanian","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Javier","family":"Esparza","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mikhail","family":"Raskin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"25203","published-online":{"date-parts":[[2023,10,12]]},"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/lmcs.episciences.org\/12402\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/lmcs.episciences.org\/12402\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,12]],"date-time":"2023-10-12T15:15:09Z","timestamp":1697123709000},"score":1,"resource":{"primary":{"URL":"http:\/\/lmcs.episciences.org\/8354"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,10,12]]},"references-count":0,"URL":"https:\/\/doi.org\/10.46298\/lmcs-19(4:2)2023","relation":{"has-preprint":[{"id-type":"arxiv","id":"2010.09471v3","asserted-by":"subject"},{"id-type":"arxiv","id":"2010.09471v2","asserted-by":"subject"}],"is-same-as":[{"id-type":"arxiv","id":"2010.09471","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.2010.09471","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"value":"1860-5974","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,10,12]]},"article-number":"8354"}}