@Article{BarGol91, author = "R. Bar-Yehuda and O. Goldreich and A. Itai", title = "Efficient Emulation of Single-Hop Radio Network with Collision Detection on Multi-Hop Radio Network with no Collision Detection", journal = "Distributed Computing", volume = "5", number = "2", pages = "67--72", publisher = "Springer-Verlag , Berlin, Heidelberg, New York, Tokyo , D", year = "1991", abstract = "This paper presents an efficient randomized emulation of {\em single-hop} radio network {\em with} collision detection on {\em multi-hop} radio network {\em without} collision detection. Each step of the single-hop network is emulated by $O \left (\left ( D+\log \frac{n}{\epsilon} \right ) \log \Delta \right)$ rounds of the multi-hop network and succeeds with probability $\geq 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 $\leq \epsilon$. A consequence of the emulation is an efficient randomized algorithm for choosing a leader in a multi-hop network.", }