论文标题
在Leaders Rendez-Vous协议中查找截止值很容易
Finding Cut-Offs in Leaderless Rendez-Vous Protocols is Easy
论文作者
论文摘要
在Rendez-Vous方案中，任意大量的没有区别的有限状态代理成对相互作用。截止问题询问是否存在数字$ b $，以便在给定初始状态下至少具有至少$ b $代理的协议的所有初始配置都可以在给定的最终状态下与所有代理达到最终配置。在最近的一篇论文（Horn and Sangnier，同意2020年）中，Horn和Sangnier证明了与领导者的协议以及无领导者协议的Expspace，截止问题是可决定的（至少与Petri net net可达性问题一样困难）。此外，对于特殊类别的对称协议，它们分别将这些界限降低到Pspace和NP。降低这些上限或找到匹配的下限的问题是打开的。我们表明，对于无领导者协议，对于无领导者对称协议而言，截止问题是p的完整问题。此外，我们还考虑了（Horn and Sangnier，Con Concur 2020）中提出的截止问题的一种变体，我们称之为有限的损坏截止问题，并证明了无领导者协议和无领导者对称协议的NL完整问题是P-Complete。最后，通过重用用于分析无领导者协议的某些技术，我们表明，具有领导者的对称协议的截止问题是NP完整的，从而改善了所有基本上限（Horn and Sangnier，Concur，Concur 2020）。
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 (Horn and Sangnier, CONCUR 2020), Horn and Sangnier proved that the cut-off problem is decidable (and at least as hard as 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 was left open. We show that the cut-off problem is P-complete for leaderless protocols and in NC for leaderless symmetric protocols. Further, we also consider a variant of the cut-off problem suggested in (Horn and Sangnier, CONCUR 2020), which we call the bounded-loss cut-off problem and prove that this problem is P-complete for leaderless protocols and NL-complete for leaderless symmetric protocols. Finally, by reusing some of the techniques applied for the analysis of leaderless protocols, we show that the cut-off problem for symmetric protocols with a leader is NP-complete, thereby improving upon all the elementary upper bounds of (Horn and Sangnier, CONCUR 2020).
