Publisher DOI: 10.1016/j.tcs.2019.07.013
Title: The cost of global broadcast in dynamic radio networks
Language: English
Authors: Ahmadi, Mohamad 
Ghodselahi, Abdolhamid 
Kuhn, Fabian 
Molla, Anisur Rahaman 
Keywords: Dynamic network;Global broadcast;Hitting game;Information dissemination;Interval connectivity;Radio network
Issue Date: 2-Feb-2020
Source: Theoretical Computer Science (806): 363-387 (2020-02-02)
Journal or Series Name: Theoretical computer science 
Abstract (english): We study the time complexity of single and multi token broadcast in adversarial dynamic radio networks. Initially, k tokens (which are k pieces of information) are distributed among the n nodes of a network and all the tokens need to be disseminated to all the nodes in the network. We first consider the single-token broadcast problem (i.e., the case k=1). By presenting upper and lower bounds, we show that the time complexity of single-token broadcast depends on the amount of stability and connectivity of the dynamic network topology and on the adaptiveness of the adversary providing the dynamic topology. Then, we give two generic algorithms which allow to transform generalized forms of single-token broadcast algorithms into multi-token broadcast (k-token broadcast) algorithms. Based on these generic algorithms, we obtain k-token broadcast algorithms for a number of different dynamic network settings. For one of the modeling assumptions, our algorithm is complemented by a lower bound which shows that the upper bound is close to optimal.
ISSN: 0304-3975
Institute: Telematik E-17 
Type: (wissenschaftlicher) Artikel
Appears in Collections:Publications without fulltext

Show full item record

Page view(s)

Last Week
Last month
checked on Oct 1, 2020

Google ScholarTM


Add Files to Item

Note about this record


Items in TORE are protected by copyright, with all rights reserved, unless otherwise indicated.