[PDF][PDF] Finding Cut-Offs in Leaderless Rendez-Vous Protocols is Easy.

AR Balasubramanian, J Esparza, MA Raskin - FoSSaCS, 2021 - library.oapen.org
FoSSaCS, 2021library.oapen.org
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 …
Abstract
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].
library.oapen.org
以上显示的是最相近的搜索结果。 查看全部搜索结果