Bounds for algebraic gossip on graphs1. Issue 2 (27th December 2012) - Borokhovich, Michael; Avin, Chen; Lotker, Zvi
ABSTRACT We study the stopping times of gossip algorithms for network coding. We analyze algebraic gossip (i.e., random linear coding) and consider three gossip algorithms for information spreading: Pull, Push, and Exchange. The stopping time of algebraic gossip is known to be linear for the complete graph, but the question of determining a tight upper bound or lower bounds for general graphs is still open. We take a major step in solving this question, and prove that algebraic gossip on any graph of size n is O(Δn) where Δ is the maximum degree of the graph. This leads to a tight bound of <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pghv4nzqtd" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />Θ(n)</alternatives> for bounded degree graphs and an upper bound of O(n2) for general graphs. We show that the latter bound is tight by providing an example of a graph with a stopping time of <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pghv4nzqj8" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />Ω(n2)</alternatives>. Our proofs use a novel method that relies on Jackson's queuing theorem to analyze the stopping time of network coding; this technique is likely to become useful for future research. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 45, 185–217, 2014