EFFICIENT EMULATION OF SINGLE-HOP RADIO NETWORK WITH COLLISION DETECTION ON MULTIHOP RADIO NETWORK WITH NO COLLISION DETECTION

This paper presents an efficient randomized emulation of single-hop radio network with collision detection on multi-hop radio network without collision detection. Each step of the single-hop network is emulated by O((D+log n/epsilon)log-DELTA) rounds of the multi-hop network and succeeds with probability greater-than-or-equal-to 1 -epsilon. (n is the number of processors, D the diameter and DELTA-the maximum degree). It is shown how to emulate any polynomial algorithm such that the probability of failure remains less-than-or-equal-to-epsilon. A consequence of the emulation is an efficient randomized algorithm for choosing a leader in a multi-hop network.