Computing Outside the Box: Average Consensus over Dynamic Networks
Computing Outside the Box: Average Consensus over Dynamic Networks
复制标题
跳出框框计算：动态网络上的平均共识
DOI：
--
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Patrick Lambein
中科院分区：
文献类型：
--
作者：
Bernadette Charron;Patrick Lambein
自主代理的网络系统及其应用程序通常依赖于平均共识的控制原始，其中代理人要计算私人初始值的平均值，以提供易于部署的可靠服务，当时平均共识应继续运行。该网络经常受到不可预测的变化，并且应该动员很少的计算资源，以便确定性，低功率和匿名代理可以在这种严格的对抗环境中参与网络。具有双向但可能短暂的沟通链接的网络，灵感来自多代理系统的凸复发规则，尤其是大都会平均共识规则，我们设计了确定的分布式算法在同步临时模型中的多项式时间里据我们所知，我们采用的分散模型没有其他分布式的共识算法具有更好的临时复杂性。我们的收敛结合需要微妙的分析，进行算法的句法简单性。
Networked systems of autonomous agents, and applications thereof, often rely on the control primitive of average consensus , where the agents are to compute the average of private initial values. To provide reliable services that are easy to deploy, average consensus should continue to operate when the network is subject to frequent and unpredictable change, and should mobilize few computational resources, so that deterministic, low powered, and anonymous agents can partake in the network. In this stringent adversarial context, we investigate the implementation of average consensus by distributed algorithms over networks with bidirectional, but potentially short-lived, communication links. Inspired by convex recurrence rules for multi-agent systems, and the Metropolis average consensus rule in particular, we design a deterministic distributed algorithm that achieves asymptotic average consensus, which we show to operate in polynomial time in a synchronous temporal model. The algorithm is easy to implement, has low space and computational complexity, and is fully distributed, requiring neither symmetry-breaking devices like unique identifiers, nor global control or knowledge of the network. In the fully decentralized model that we adopt, to our knowledge, no other distributed average consensus algorithm has a better temporal complexity. Our approach distinguishes itself from classical convex recurrence rules in that the agent’s values may sometimes leave their previous convex hull. As a consequence, our convergence bound requires a subtle analysis, despite the syntactic simplicity of our algorithm.