论文标题
人口方案的近乎最佳领导者选举
Near-Optimal Leader Election in Population Protocols on Graphs
论文作者
论文摘要
在随机总体协议模型中，我们获得了一个带有$ n $节点的连接图，并且在每个时间步骤中，调度程序在随机的情况下均匀地对图的边缘进行样品，并通过此边缘交互连接的节点。该模型中的一个基本任务是稳定的领导者选举，其中所有节点以相同的状态开始，目的是达到一种配置，在该配置中，（1）（1）确切地将一个节点当选为领导者，（2）无论互动的顺序如何，该节点仍然是独特的领导者。在集团上，最近解决了此问题的复杂性：使用$θ（\ log \ log n）$状态的时间 - 最佳协议稳定在$θ（n \ log n）$中，而使用$ o（1）$状态的协议则需要$θ（n^2）$预期步骤。 在这项工作中，我们研究了图表上稳定的领导者选举的复杂性。我们在一般图上提供了第一个非平凡的时间下限，这表明，当超越集团移动时，稳定的领导者选举的复杂性可以从$ o（1）$到$θ（n^3）$预期步骤。我们描述了一个在许多图系列中最佳时间最佳的协议，但使用多项式态度。相比之下，我们提供了一个仅使用$ o（\ log^2n）$状态的近时间优势协议，最多是一个因子$ o（\ log n）$慢。最后，我们观察到，对于许多图，Beauquier等人的恒定状态方案。 [Opodis 2013]最多是一个因子$ o（N \ log n）$比快速多项式状态协议慢，并且在恒定状态协议中，该协议在密集的随机图上具有接近最佳的平均病例复杂性。
In the stochastic population protocol model, we are given a connected graph with $n$ nodes, and in every time step, a scheduler samples an edge of the graph uniformly at random and the nodes connected by this edge interact. A fundamental task in this model is stable leader election, in which all nodes start in an identical state and the aim is to reach a configuration in which (1) exactly one node is elected as leader and (2) this node remains as the unique leader no matter what sequence of interactions follows. On cliques, the complexity of this problem has recently been settled: time-optimal protocols stabilize in $Θ(n \log n)$ expected steps using $Θ(\log \log n)$ states, whereas protocols that use $O(1)$ states require $Θ(n^2)$ expected steps. In this work, we investigate the complexity of stable leader election on graphs. We provide the first non-trivial time lower bounds on general graphs, showing that, when moving beyond cliques, the complexity of stable leader election can range from $O(1)$ to $Θ(n^3)$ expected steps. We describe a protocol that is time-optimal on many graph families, but uses polynomially-many states. In contrast, we give a near-time-optimal protocol that uses only $O(\log^2n)$ states that is at most a factor $O(\log n)$ slower. Finally, we observe that for many graphs the constant-state protocol of Beauquier et al. [OPODIS 2013] is at most a factor $O(n \log n)$ slower than the fast polynomial-state protocol, and among constant-state protocols, this protocol has near-optimal average case complexity on dense random graphs.
