Lower bounds on information dissemination in dynamic networks

DOI10.1007/978-3-642-33651-5_12zbMATH Open1377.68021arXiv1208.6051OpenAlexW1570690262MaRDI QIDQ4909409FDOQ4909409

Authors: Bernhard Haeupler, Fabian Kuhn 

Publication date: 13 March 2013

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: We study lower bounds on information dissemination in adversarial dynamic networks. Initially, k pieces of information (henceforth called tokens) are distributed among n nodes. The tokens need to be broadcast to all nodes through a synchronous network in which the topology can change arbitrarily from round to round provided that some connectivity requirements are satisfied. If the network is guaranteed to be connected in every round and each node can broadcast a single token per round to its neighbors, there is a simple token dissemination algorithm that manages to deliver all k tokens to all the nodes in O(nk) rounds. Interestingly, in a recent paper, Dutta et al. proved an almost matching Omega(n + nk/log n) lower bound for deterministic token-forwarding algorithms that are not allowed to combine, split, or change tokens in any way. In the present paper, we extend this bound in different ways. If nodes are allowed to forward b < k tokens instead of only one token in every round, a straight-forward extension of the O(nk) algorithm disseminates all k tokens in time O(nk/b). We show that for any randomized token-forwarding algorithm, Omega(n + nk/(b^2 log n log log n)) rounds are necessary. If nodes can only send a single token per round, but we are guaranteed that the network graph is c-vertex connected in every round, we show a lower bound of Omega(nk/(c log^{3/2} n)), which almost matches the currently best O(nk/c) upper bound. Further, if the network is T-interval connected, a notion that captures connection stability over time, we prove that Omega(n + nk/(T^2 log n)) rounds are needed. The best known upper bound in this case manages to solve the problem in O(n + nk/T) rounds. Finally, we show that even if each node only needs to obtain a delta-fraction of all the tokens for some delta in [0,1], Omega(nk delta^3 log n) are still required.

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

Recommendations

• On the complexity of information spreading in dynamic networks
• The cost of global broadcast in dynamic radio networks
• Token dissemination in geometric dynamic networks
• Information spreading in dynamic networks under oblivious adversaries
• Distributed computation in dynamic networks

Mathematics Subject Classification ID

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

Cited In (10)

• A randomized algorithm for the joining protocol in dynamic distributed networks
• Gathering in dynamic rings
• An Introduction to Temporal Graphs: An Algorithmic Perspective^*
• On information aggregation and interim efficiency in networks
• Message and time efficient multi-broadcast schemes
• Brief Announcement: Efficient Computation in Congested Anonymous Dynamic Networks
• Exploration of dynamic networks: tight bounds on the number of agents
• Some lower bounds in dynamic networks with oblivious adversaries
• Minimum Weight Dynamo and Fast Opinion Spreading
• An Introduction to Temporal Graphs: An Algorithmic Perspective

This page was built for publication: Lower bounds on information dissemination in dynamic networks

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