Randomized gossiping with effective resistance weights: performance guarantees and applications

Bugra Can; Saeed Soori; Necdet Serhat Aybat; Maryam Mehri Dehnavi; Mert Gürbüzbalaban

doi:10.1109/TCNS.2022.3161201

Journal article, 2022

Randomized gossiping with effective resistance weights: performance guarantees and applications

Bugra Can, Saeed Soori, Necdet Serhat Aybat, Maryam Mehri Dehnavi, Mert Gürbüzbalaban

IEEE Transactions on Control of Network Systems, 9(2), pp. 524–536, 2022.

Publisher (DOI)Code

In brief

Asks how to pick which pair of neighbors should average their values in randomized gossip. Choosing edges with probability proportional to their effective resistance — a quantity that measures how much an edge matters for connectivity — comes with convergence-rate guarantees that improve on uniform gossip, markedly so on poorly connected graphs, and the scheme plugs into decentralized optimization algorithms whose communication step is gossip.

Topics

Distributed & decentralized learning

Cite

@article{can2022gossiping,
  title   = {Randomized gossiping with effective resistance weights: performance guarantees and applications},
  author  = {Bugra Can and Saeed Soori and Necdet Serhat Aybat and Maryam Mehri Dehnavi and Mert Gürbüzbalaban},
  year    = {2022},
  journal = {IEEE Transactions on Control of Network Systems},
  volume  = {9(2)},
  pages   = {524--536},
  doi     = {10.1109/TCNS.2022.3161201},
}