Tight bounds on information dissemination in sparse mobile networks

DOI10.1145/1993806.1993882zbMath1321.68391arXiv1101.4609OpenAlexW2014705821MaRDI QIDQ2943410

Geppino Pucci, Andrea Pietracaprina, Eli Upfal, Alberto Pettarin

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://arxiv.org/abs/1101.4609

zbMATH Keywords

mobile networksbroadcastinformation disseminationmultiple random walks

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Distributed systems (68M14) Random walks on graphs (05C81)

Related Items (10)

Fast flooding over Manhattan ⋮ Multiple random walks on graphs: mixing few to cover many ⋮ Unnamed Item ⋮ Information spreading in dynamic graphs ⋮ Unnamed Item ⋮ Theory and Practice of Discrete Interacting Agents Models ⋮ Space-time percolation and detection by mobile nodes ⋮ Viral Processes by Random Walks on Random Regular Graphs ⋮ Information Dissemination via Random Walks in d-Dimensional Space ⋮ Viral processes by random walks on random regular graphs

Cites Work

• Gradient clock synchronization in dynamic networks
• Consensus algorithms with one-bit messages
• Knowledge and common knowledge in a Byzantine environment: Crash failures
• Broadcasting in dynamic radio networks
• Programming simultaneous actions using common knowledge
• Continuous consensus via common knowledge
• Distributed computation in dynamic networks
• Flooding time in edge-Markovian dynamic graphs
• Knowledge and common knowledge in a distributed environment
• How to Explore a Fast-Changing World (Cover Time of a Simple Random Walk on Evolving Graphs)
• Opportunistic Information Dissemination in Mobile Ad-hoc Networks: The Profit of Global Synchrony
• Fault Tolerance in Networks of Bounded Degree
• Reaching Agreement in the Presence of Faults
• Perfectly secure message transmission
• Parsimonious flooding in dynamic graphs
• Optimal gradient clock synchronization in dynamic networks
• Almost-Everywhere Secure Computation
• Unnamed Item

This page was built for publication: Tight bounds on information dissemination in sparse mobile networks