Broadcasting in Unreliable Radio Networks

Abstract

Practitioners agree that unreliable links, which fluctuate between working and not working, are an important characteristic of wireless networks. In contrast, most theoretical models of radio networks fix a static set of links and assume that these links work reliably throughout an execution. This gap between theory and practice motivates us to investigate how unreliable links affect theoretical bounds on broadcast in radio networks. To that end we consider a model that includes two types of links: reliable links, which always deliver messages, and unreliable links, which sometimes deliver messages and sometimes do not. It is assumed that the graph induced by the reliable links is connected, and unreliable links are controlled by a worst-case adversary. In the new model we show an(n log n) lower bound on deterministic broadcast in undirected graphs, even when all processes are initially awake and have collision detection, and an (n) lower bound on randomized broadcast in undirected networks of constant diameter. This clearly separates the new model from the classical, reliable model. On the positive side, we give two algorithms that tolerate the inherent unreliability: an O(n3=2plog n)-time deterministic algorithm and a randomized algorithm which terminates in O(n log2 n) rounds with high probability.