TY - GEN
T1 - Finding cut-offs in leaderless rendez-vous protocols is easy
AU - Balasubramanian, A. R.
AU - Esparza, Javier
AU - Raskin, Mikhail
N1 - Publisher Copyright:
© The Author(s) 2021.
PY - 2021
Y1 - 2021
N2 - 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 B such that all initial configurations of the protocol with at least B agents in a given initial state can reach a final configuration with all agents in a given final state. In a recent paper [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 EXPSPACE for leaderless protocols. Further, for the special class of symmetric protocols they reduce these bounds to PSPACE and NP, respectively. The problem of lowering these upper bounds or finding matching lower bounds is left open. We show that the cut-off problem is P-complete for leaderless protocols, NP-complete for symmetric protocols with a leader, and in NC for leaderless symmetric protocols, thereby solving all the problems left open in [17].
AB - 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 B such that all initial configurations of the protocol with at least B agents in a given initial state can reach a final configuration with all agents in a given final state. In a recent paper [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 EXPSPACE for leaderless protocols. Further, for the special class of symmetric protocols they reduce these bounds to PSPACE and NP, respectively. The problem of lowering these upper bounds or finding matching lower bounds is left open. We show that the cut-off problem is P-complete for leaderless protocols, NP-complete for symmetric protocols with a leader, and in NC for leaderless symmetric protocols, thereby solving all the problems left open in [17].
KW - Cut-off problem
KW - Petri nets
KW - Rendez-vous protocols
UR - http://www.scopus.com/inward/record.url?scp=85108906652&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-71995-1_3
DO - 10.1007/978-3-030-71995-1_3
M3 - Conference contribution
AN - SCOPUS:85108906652
SN - 9783030719944
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 42
EP - 61
BT - Foundations of Software Science and Computation Structures - 24th International Conference, FOSSACS 2021 Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2021, Proceedings
A2 - Kiefer, Stefan
A2 - Tasson, Christine
PB - Springer Science and Business Media Deutschland GmbH
T2 - 24th International Conference on Foundations of Software Science and Computation Structures, FOSSACS 2021 held as part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2021
Y2 - 27 March 2021 through 1 April 2021
ER -