Title: Constant-Length Labelling Schemes for Deterministic Radio Broadcast

Speaker: Professor Faith Ellen

Abstract: 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, Barun Gorain, Avery Miller, and Andrzej Pelc.