Broadcast Gossip Algorithms for Consensus on Strongly Connected Digraphs
We study a general framework for broadcast gossip algorithms which use companion variables to solve the average consensus problem. Each node maintains an initial state and a companion variable. Iterative updates are performed asynchronously whereby one random node broadcasts its current state and co...
সংরক্ষণ করুন:
| প্রধান লেখক: | , |
|---|---|
| বিন্যাস: | প্রবন্ধ |
| প্রকাশিত: |
2012
|
| বিষয়গুলি: | |
| অনলাইন ব্যবহার করুন: | https://arxiv.org/abs/1208.4895 http://arxiv.org/abs/1208.4895 |
| ট্যাগগুলো: |
কোনো ট্যাগ নেই, প্রথমজন হিসাবে ট্যাগ করুন!
|
| _version_ | 1879179164756475904 |
|---|---|
| author | Shaochuan, Wu Rabbat, Michael G. |
| author_browse | Rabbat, Michael G. Shaochuan, Wu |
| author_facet | Shaochuan, Wu Rabbat, Michael G. |
| author_sort | Shaochuan, Wu |
| building | arXiv |
| collection | Acceso abierto |
| description | We study a general framework for broadcast gossip algorithms which use companion variables to solve the average consensus problem. Each node maintains an initial state and a companion variable. Iterative updates are performed asynchronously whereby one random node broadcasts its current state and companion variable and all other nodes receiving the broadcast update their state and companion variable. We provide conditions under which this scheme is guaranteed to converge to a consensus solution, where all nodes have the same limiting values, on any strongly connected directed graph. Under stronger conditions, which are reasonable when the underlying communication graph is undirected, we guarantee that the consensus value is equal to the average, both in expectation and in the mean-squared sense. Our analysis uses tools from non-negative matrix theory and perturbation theory. The perturbation results rely on a parameter being sufficiently small. We characterize the allowable upper bound as well as the optimal setting for the perturbation parameter as a function of the network topology, and this allows us to characterize the worst-case rate of convergence. Simulations illustrate that, in comparison to existing broadcast gossip algorithms, the approaches proposed in this paper have the advantage that they simultaneously can be guaranteed to converge to the average consensus and they converge in a small number of broadcasts. |
| first_indexed | 2026-10-16T01:28:18Z |
| format | Article |
| fullrecord | <oai_dc:dc xmlns:oai_dc="http://www.openarchives.org/OAI/2.0/oai_dc/" xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.openarchives.org/OAI/2.0/oai_dc/ https://www.openarchives.org/OAI/2.0/oai_dc.xsd"><identifier>arxiv-1208.4895</identifier><datestamp>2026-06-03</datestamp>
<dc:title>Broadcast Gossip Algorithms for Consensus on Strongly Connected Digraphs</dc:title>
<dc:creator>Shaochuan, Wu</dc:creator>
<dc:creator>Rabbat, Michael G.</dc:creator>
<dc:subject>Systems and Control</dc:subject>
<dc:subject>Distributed, Parallel, and Cluster Computing</dc:subject>
<dc:description>We study a general framework for broadcast gossip algorithms which use companion variables to solve the average consensus problem. Each node maintains an initial state and a companion variable. Iterative updates are performed asynchronously whereby one random node broadcasts its current state and companion variable and all other nodes receiving the broadcast update their state and companion variable. We provide conditions under which this scheme is guaranteed to converge to a consensus solution, where all nodes have the same limiting values, on any strongly connected directed graph. Under stronger conditions, which are reasonable when the underlying communication graph is undirected, we guarantee that the consensus value is equal to the average, both in expectation and in the mean-squared sense. Our analysis uses tools from non-negative matrix theory and perturbation theory. The perturbation results rely on a parameter being sufficiently small. We characterize the allowable upper bound as well as the optimal setting for the perturbation parameter as a function of the network topology, and this allows us to characterize the worst-case rate of convergence. Simulations illustrate that, in comparison to existing broadcast gossip algorithms, the approaches proposed in this paper have the advantage that they simultaneously can be guaranteed to converge to the average consensus and they converge in a small number of broadcasts. </dc:description>
<dc:description>30 pages, submitted</dc:description>
<dc:date>2012-08-24</dc:date>
<dc:date>2012-08-31</dc:date>
<dc:type>text</dc:type>
<dc:identifier>https://arxiv.org/abs/1208.4895</dc:identifier>
<dc:identifier>http://arxiv.org/abs/1208.4895</dc:identifier>
</oai_dc:dc> |
| id | arxiv-1208.4895 |
| institution | arXiv |
| last_indexed | 2026-10-16T01:28:18Z |
| publishDate | 2012 |
| publishDateRange | 2012 |
| publishDateSort | 2012 |
| record_format | oai_dc |
| spelling | arxiv-1208.48952026-06-03 Broadcast Gossip Algorithms for Consensus on Strongly Connected Digraphs Shaochuan, Wu Rabbat, Michael G. Systems and Control Distributed, Parallel, and Cluster Computing We study a general framework for broadcast gossip algorithms which use companion variables to solve the average consensus problem. Each node maintains an initial state and a companion variable. Iterative updates are performed asynchronously whereby one random node broadcasts its current state and companion variable and all other nodes receiving the broadcast update their state and companion variable. We provide conditions under which this scheme is guaranteed to converge to a consensus solution, where all nodes have the same limiting values, on any strongly connected directed graph. Under stronger conditions, which are reasonable when the underlying communication graph is undirected, we guarantee that the consensus value is equal to the average, both in expectation and in the mean-squared sense. Our analysis uses tools from non-negative matrix theory and perturbation theory. The perturbation results rely on a parameter being sufficiently small. We characterize the allowable upper bound as well as the optimal setting for the perturbation parameter as a function of the network topology, and this allows us to characterize the worst-case rate of convergence. Simulations illustrate that, in comparison to existing broadcast gossip algorithms, the approaches proposed in this paper have the advantage that they simultaneously can be guaranteed to converge to the average consensus and they converge in a small number of broadcasts. 30 pages, submitted 2012-08-24 2012-08-31 text https://arxiv.org/abs/1208.4895 http://arxiv.org/abs/1208.4895 |
| spellingShingle | Systems and Control Distributed, Parallel, and Cluster Computing Shaochuan, Wu Rabbat, Michael G. Broadcast Gossip Algorithms for Consensus on Strongly Connected Digraphs |
| title | Broadcast Gossip Algorithms for Consensus on Strongly Connected Digraphs |
| title_full | Broadcast Gossip Algorithms for Consensus on Strongly Connected Digraphs |
| title_fullStr | Broadcast Gossip Algorithms for Consensus on Strongly Connected Digraphs |
| title_full_unstemmed | Broadcast Gossip Algorithms for Consensus on Strongly Connected Digraphs |
| title_short | Broadcast Gossip Algorithms for Consensus on Strongly Connected Digraphs |
| title_sort | broadcast gossip algorithms for consensus on strongly connected digraphs |
| topic | Systems and Control Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/1208.4895 http://arxiv.org/abs/1208.4895 |
| work_keys_str_mv | AT shaochuanwu broadcastgossipalgorithmsforconsensusonstronglyconnecteddigraphs AT rabbatmichaelg broadcastgossipalgorithmsforconsensusonstronglyconnecteddigraphs |