Analyzing network coding gossip made easy

DOI10.1145/1993636.1993676MaRDI QIDQ5419099zbMATH OpenOpenAlexFDO

Authors Bernhard Haeupler

Publication date 5 June 2014

Published in Proceedings of the forty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)

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

zbMATH Keywords

dynamic networksgossipmulticastnetwork coding

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Network protocols (68M12) Analysis of algorithms and problem complexity (68Q25)

Abstract: We give a new technique to analyze the stopping time of gossip protocols that are based on random linear network coding (RLNC). Our analysis drastically simplifies, extends and strengthens previous results. We analyze RLNC gossip in a general framework for network and communication models that encompasses and unifies the models used previously in this context. We show, in most settings for the first time, that it converges with high probability in the information-theoretically optimal time. Most stopping times are of the form O(k + T) where k is the number of messages to be distributed and T is the time it takes to disseminate one message. This means RLNC gossip achieves "perfect pipelining". Our analysis directly extends to highly dynamic networks in which the topology can change completely at any time. This remains true even if the network dynamics are controlled by a fully adaptive adversary that knows the complete network state. Virtually nothing besides simple O(kT) sequential flooding protocols was previously known for such a setting. While RLNC gossip works in this wide variety of networks its analysis remains the same and extremely simple. This contrasts with more complex proofs that were put forward to give less strong results for various special cases.

Recommendations

• Analyzing network coding (gossip) made easy
• Broadcasting and Gossiping in de Bruijn Networks
• Faster information dissemination in dynamic networks via network coding
• Network Coding
• Source Coding for a Simple Network
• Network coding
• Broadcasting and gossiping on de Bruijn, shuffle-exchange and similar networks
• Analysis of accelerated gossip algorithms
• A survey of gossiping and broadcasting in communication networks

Cited in

(12)

• Breathe before speaking: efficient information dissemination despite noisy, limited and anonymous communication
• Simple multi-party set reconciliation
• The cost of global broadcast in dynamic radio networks
• Distributed computation in dynamic networks via random walks
• Bounds for algebraic gossip on graphs
• Analyzing network coding (gossip) made easy
• Towards robust and efficient computation in dynamic peer-to-peer networks
• Ultra-fast rumor spreading in social networks
• Order optimal information spreading using algebraic gossip
• Bounded-contention coding for the additive network model
• Causality, influence, and computation in possibly disconnected synchronous dynamic networks
• Randomized broadcast in radio networks with collision detection

This page was built for publication: Analyzing network coding gossip made easy

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