Bounds for algebraic gossip on graphs

DOI10.1002/RSA.20480zbMATH Open1301.05164arXiv1001.3265OpenAlexW2963370966MaRDI QIDQ2925522FDOQ2925522

Authors: Michael Borokhovich, Chen Avin, Zvi Lotker 

Publication date: 16 October 2014

Published in: Random Structures \& Algorithms (Search for Journal in Brave)

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(D*n) where D is the maximum degree of the graph. This leads to a tight bound of Theta(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 Omega(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.

Full work available at URL: https://arxiv.org/abs/1001.3265

Recommendations

• Order optimal information spreading using algebraic gossip
• Order optimal information spreading using algebraic gossip
• Analyzing network coding gossip made easy
• Analyzing network coding (gossip) made easy
• On the optimality of general lower bounds for broadcasting and gossiping

zbMATH Keywords

network codingnetwork capacitygossipgossip algorithmsalgebraic gossip

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Applications of queueing theory (congestion, allocation, storage, traffic, etc.) (60K30) Approximation algorithms (68W25) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25)

Cites Work

• Probability and random processes.
• Title not available (Why is that?)
• Linear network coding
• Probability and Computing
• Title not available (Why is that?)
• Analyzing network coding gossip made easy
• Queueing Modelling Fundamentals
• Order optimal information spreading using algebraic gossip

Cited In (5)

• Analyzing network coding (gossip) made easy
• A Generalized Gossip Algorithm on Convex Metric Spaces
• Order optimal information spreading using algebraic gossip
• Order optimal information spreading using algebraic gossip
• Distributed computation in dynamic networks via random walks

This page was built for publication: Bounds for algebraic gossip on graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2925522)