Premium
Bounds for algebraic gossip on graphs
Author(s) -
Borokhovich Michael,
Avin Chen,
Lotker Zvi
Publication year - 2014
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20480
Subject(s) - gossip , upper and lower bounds , algebraic number , bounded function , discrete mathematics , random graph , linear network coding , combinatorics , mathematical proof , mathematics , computer science , graph , stopping time , psychology , mathematical analysis , social psychology , computer network , statistics , geometry , network packet
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 Θ ( n ) for bounded degree graphs and an upper bound of O ( n 2 ) for general graphs. We show that the latter bound is tight by providing an example of a graph with a stopping time of Ω ( n 2 ) . 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