@inproceedings{33fdbbe60a07426eb858be9794e0da93,
title = "A new perspective on randomized gossip algorithms",
abstract = "In this short note we propose a new approach for the design and analysis of randomized gossip algorithms which can be used to solve the average consensus problem. We show how that Randomized Block Kaczmarz (RBK) method - a method for solving linear systems - works as gossip algorithm when applied to a special system encoding the underlying network. The famous pairwise gossip algorithm arises as a special case. Subsequently, we reveal a hidden duality of randomized gossip algorithms, with the dual iterative process maintaining a set of numbers attached to the edges as opposed to nodes of the network. We prove that RBK obtains a superlinear speedup in the size of the block, and demonstrate this effect through experiments.",
keywords = "Average Consensus Problem, Linear Systems, Networks, Randomized Block Kaczmarz, Randomized Gossip Algorithms",
author = "Nicolas Loizou and Peter Richt{\'a}rik",
note = "Publisher Copyright: {\textcopyright} 2016 IEEE.; 2016 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2016 ; Conference date: 07-12-2016 Through 09-12-2016",
year = "2017",
month = apr,
day = "19",
doi = "10.1109/GlobalSIP.2016.7905880",
language = "English (US)",
series = "2016 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2016 - Proceedings",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "440--444",
booktitle = "2016 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2016 - Proceedings",
address = "United States",
}