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

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

Authors: Matthias Függer, Thomas Nowak, Kyrill Winkler 

Publication date: 5 June 2020

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• A survey of gossiping and broadcasting in communication networks
• Distributed computation in dynamic networks
• Title not available (Why is that?)
• Methods and problems of communication in usual networks
• Title not available (Why is that?)
• The Heard-Of model: computing in distributed systems with benign faults
• Time is not a healer
• Approximate Consensus in Highly Dynamic Networks: The Role of Averaging Algorithms
• On linear-time data dissemination in dynamic rooted trees
• Consensus in rooted dynamic networks with short-lived stability
• Rumor Spreading in Random Evolving Graphs

Cited In (2)

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

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)