Finding Cut-Offs in Leaderless Rendez-Vous Protocols is Easy

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 [Image: see text] for leaderless protocols. Further, for the special class of symmetric protocols they reduce these bounds to [Image: see text] and [Image: see text] , respectively. The problem of lowering these upper bounds or finding matching lower bounds is left open. We show that the cut-off problem is [Image: see text] -complete for leaderless protocols, [Image: see text] -complete for symmetric protocols with a leader, and in [Image: see text] for leaderless symmetric protocols, thereby solving all the problems left open in [17].