|
|
||
|
IMADA -Department of Mathematics and Computer Science |
|
Broadcast is a fundamental network communication primitive, in which a source node has a message that has to be received by all other nodes. In synchronous radio networks, this problem is non-trivial, since if two or more neighbours of a node transmit at the same time, it hears nothing. In fact, if nodes do not store any information, broadcast is impossible deterministically, even in a four-cycle. If the nodes have distinct identifiers from a small name space, then a round-robin strategy suffices, but it takes a long time. This talk will show that every radio network can be labelled using a small constant number of bits so that broadcast can be accomplished by a fixed deterministic algorithm that does not know the network topology nor any bound on its size. Specifically, there is a labelling scheme that stores 2 (carefully chosen) bits per nodes that allows broadcast to be performed in $O(n)$ rounds, where $n$ is the size of the network. There is a variant of this algorithm using 4 bits per node that completes broadcast in $O(\sqrt{Dn})$ rounds, where $D$ is the source eccentricity of the network. This number of rounds is shown to be optimal for a class of algorithms that includes both. Then, using some ideas from some old algorithms, which assume nodes have distinct identifiers and a bound on the network size, a deterministic algorithm is constructed that uses 3 bits per node and completes in $O(D log^2 n)$ rounds. A randomized construction of a labelling scheme with 3 bits per node for a broadcast algorithm that completes in $O(D log n log^2 n)$ rounds is also presented. This is joint work with Seth Gilbert and Barun Gorain, Avery Miller, and Andrzej Pelc. Host: Joan Boyar SDU HOME | IMADA HOME Daniel Merkle |