14/07/2020

Constant-length labelling schemes for faster deterministic radio broadcast

Faith Ellen, Seth Gilbert

Keywords: labelling schemes, radio networks, broadcast

Abstract: In this paper, we consider the problem of broadcast from a specified source node in a known synchronous radio network. In 2019, Ellen, Gorain, Miller and Plc showed that this is possible if each node in the network only stores 2 (carefully chosen) bits of information. They proved that in an n-node network, their algorithm ensures that the broadcast completes within 2n-3 rounds. We show that storing only a small constant number of additional bits, it is possible to broadcast significantly faster when the source eccentricity, D, of the network is o(n).We begin by presenting a modification of Ellen, Gorain, Miller and Pelc’s algorithm that stores 4 bits per node and completes within O(√Dn) rounds. Then we define a class of broadcast algorithms that includes both these algorithms and prove that any algorithm in this class requires Ω(√nD) rounds.Next, we show (non-constructively) that there exists a broadcast algorithm which stores only 3 bits of information per node, but completes within O(D log n+log2 n) rounds. Finally, using ideas from Chlamtac and Weinstein (1991), we show how to construct the relevant information and do almost as well, giving an algorithm using 3 bits per node that runs in O(D log^2 n) rounds.

 0
 0
 0
 0
This is an embedded video. Talk and the respective paper are published at SPAA 2020 virtual conference. If you are one of the authors of the paper and want to manage your upload, see the question "My papertalk has been externally embedded..." in the FAQ section.

Comments

Post Comment
no comments yet
code of conduct: tbd

Similar Papers