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.
|Publication status||Published - 24 Apr 2017|
|Event||2016 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2016 - Washington, United States|
Duration: 7 Dec 2016 → 9 Dec 2016
|Conference||2016 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2016|
|Period||7/12/16 → 9/12/16|