Order optimal information spreading using algebraic gossip

DOI10.1145/1993806.1993883MaRDI QIDQ5892124zbMATH OpenOpenAlexFDO

Authors Chen Avin, Michael Borokhovich, Keren Censor-Hillel, Zvi Lotker

Publication date 11 September 2015

Published in Proceedings of the 30th annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1993806.1993883

zbMATH Keywords

algebraic gossipgossipnetwork codingtight bounds

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Network protocols (68M12) Distributed systems (68M14) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Order optimal information spreading using algebraic gossip
• Bounds for algebraic gossip on graphs
• Fast gossiping by short messages
• Fast Gossiping by Short Messages
• Almost-optimal gossip-based aggregate computation

Cites work

• Almost-Everywhere Secure Computation
• Broadcasting in dynamic radio networks
• Consensus algorithms with one-bit messages
• Continuous consensus via common knowledge
• Distributed computation in dynamic networks
• Fault Tolerance in Networks of Bounded Degree
• Flooding time in edge-Markovian dynamic graphs
• Gradient clock synchronization in dynamic networks
• How to Explore a Fast-Changing World (Cover Time of a Simple Random Walk on Evolving Graphs)
• scientific article; zbMATH DE number 795590 (Why is no real title available?)
• Knowledge and common knowledge in a Byzantine environment: Crash failures
• Knowledge and common knowledge in a distributed environment
• Opportunistic information dissemination in mobile ad-hoc networks: the profit of global synchrony
• Optimal gradient clock synchronization in dynamic networks
• Parsimonious flooding in dynamic graphs
• Perfectly secure message transmission
• Programming simultaneous actions using common knowledge
• Reaching Agreement in the Presence of Faults

Cited in

(2)

• Bounds for algebraic gossip on graphs
• Order optimal information spreading using algebraic gossip

This page was built for publication: Order optimal information spreading using algebraic gossip

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