一句话：证明无领导者会合协议的 cut-off 问题是 P 完全的，对称协议在 NC 中，并改进有领导者对称协议的复杂度上界。
会合协议中任意多不可区分有限状态代理成对交互，cut-off 问题询问是否存在 B，使给定初始状态下至少 B 个代理的初始配置都能到达所有代理处于给定最终状态的配置。Horn 和 Sangnier 已证有领导者协议可判定、无领导者协议在 EXPSPACE，对称协议为 PSPACE/NP，但上下界未紧。本文重新分析无领导者协议，证明其 cut-off 问题 P 完全，无领导者对称协议在 NC；对 bounded-loss cut-off 变体证明无领导者 P 完全、对称 NL 完全；并复用相关技术证明有领导者对称协议 cut-off 为 NP 完全，改进原有初等上界。
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).
@article{paperbot2192,
title = {Finding Cut-Offs in Leaderless Rendez-Vous Protocols is Easy},
author = {A. R. Balasubramanian and Javier Esparza and Mikhail Raskin},
journal = {Logical Methods in Computer Science},
volume = {Volume 19, Issue 4},
year = {2023},
doi = {10.46298/lmcs-19(4:2)2023}
}