On the radius of nonsplit graphs and information dissemination in dynamic networks

DOI10.1016/J.DAM.2020.02.013zbMATH Open1441.05090OpenAlexW3006692216MaRDI QIDQ2185751FDOQ2185751

Authors Matthias Függer, Thomas Nowak, Kyrill Winkler 

Publication date 5 June 2020

Published in Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

dynamic networksgraph radiusinformation dissemination

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Distance in graphs (05C12) Network design and communication in computer systems (68M10)

Abstract: A nonsplit graph is a directed graph where each pair of nodes has a common incoming neighbor. We show that the radius of such graphs is in $O(loglogn)$, where $n$ is the number of nodes. We then generalize the result to products of nonsplit graphs. The analysis of nonsplit graph products has direct implications in the context of distributed systems, where processes operate in rounds and communicate via message passing in each round: communication graphs in several distributed systems naturally relate to nonsplit graphs and the graph product concisely represents relaying messages in such networks. Applying our results, we obtain improved bounds on the dynamic radius of such networks, i.e., the maximum number of rounds until all processes have received a message from a common process, if all processes relay messages in each round. We finally connect the dynamic radius to lower bounds for achieving consensus in dynamic networks.

Recommendations

• A lower bound for radio broadcast
• Lower bounds on information dissemination in dynamic networks
• Radio communication in random graphs
• STACS 2004
• Coordinated consensus in dynamic networks

Cites work

• scientific article; zbMATH DE number 996442 (Why is no real title available?)
• scientific article; zbMATH DE number 857072 (Why is no real title available?)
• scientific article; zbMATH DE number 3232670 (Why is no real title available?)
• A survey of gossiping and broadcasting in communication networks
• Approximate consensus in highly dynamic networks: the role of averaging algorithms
• Consensus in rooted dynamic networks with short-lived stability
• Distributed computation in dynamic networks
• Methods and problems of communication in usual networks
• On linear-time data dissemination in dynamic rooted trees
• Rumor spreading in random evolving graphs
• The Heard-Of model: computing in distributed systems with benign faults
• Time is not a healer (preliminary version)

Cited in

(2)

• The time complexity of consensus under oblivious message adversaries
• On Dissemination Thresholds in Regular and Irregular Graph Classes

This page was built for publication: On the radius of nonsplit graphs and information dissemination in dynamic networks

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