Scholarlink

<p>Average consensus (AC) strategies have played a key role in every system that employs cooperation by means of distributed computations. To promote consensus, an <i>N</i>-agent network can repeatedly combine certain node estimates until their mean value is reached. Such algorithms are commonly formulated as (global) recursive matrix–vector products of size <i>N</i>, where consensus can be attained either asymptotically or in finite time. In this paper, we revisit some existing approaches in these directions and propose new iterative and exact extensions to the problem. This is carried out by interplaying with standalone conterparts, while underpinned by the so-called <i>eigenstep</i> method of finite-time convergence, which we generalize to directed graphs with arbitrary combination matrices. Also, by formulating the AC from a linearly-constrained problem, we compute the solution via an exact algorithm that requires as little as <InlineEquation ID="IEq1"><EquationSource Format="TEX">\(\mathcal{O}(N)\)</EquationSource></InlineEquation> additions in overall complexity. For undirected graphs, the latter compares favorably to existing schemes that require <InlineEquation ID="IEq2"><EquationSource Format="TEX">\(\mathcal{O}(K\!N^2)\)</EquationSource></InlineEquation> multiplications to deliver the AC, where <i>K</i> refers to the number of distinct eigenvalues of the underlying graph Laplacian matrix.&#xa0;&#xa0;&#xa0;&#xa0;</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

On fast and exact average consensus algorithms

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2026年6月26日

查看全文
  • Ricardo Merched

摘要

Average consensus (AC) strategies have played a key role in every system that employs cooperation by means of distributed computations. To promote consensus, an N-agent network can repeatedly combine certain node estimates until their mean value is reached. Such algorithms are commonly formulated as (global) recursive matrix–vector products of size N, where consensus can be attained either asymptotically or in finite time. In this paper, we revisit some existing approaches in these directions and propose new iterative and exact extensions to the problem. This is carried out by interplaying with standalone conterparts, while underpinned by the so-called eigenstep method of finite-time convergence, which we generalize to directed graphs with arbitrary combination matrices. Also, by formulating the AC from a linearly-constrained problem, we compute the solution via an exact algorithm that requires as little as \(\mathcal{O}(N)\) additions in overall complexity. For undirected graphs, the latter compares favorably to existing schemes that require \(\mathcal{O}(K\!N^2)\) multiplications to deliver the AC, where K refers to the number of distinct eigenvalues of the underlying graph Laplacian matrix.