@Article{BarIsr93,
  author =       "R. Bar-Yehuda and A. Israeli and A. Itai",
  title =        "Multiple Communication in Multi-hop Radio Networks",
  journal =      "SIAM Journal on Computing",
  volume =       "22",
  number =       "4",
  month =        aug,
  year =         "1993",
  pages =        "875--887",
  abstract =     "Two tasks of communication in a multi-hop
    synchronous radio network are considered: Point-to-point
    communication and broadcast (sending a message to
    all nodes of a network). Efficient protocols for both
    problems are presented. Even though the protocols are
    probabilistic, it is shown how to acknowledge messages
    deterministically.
    Let $n, D,$ and $\Delta$ be the number of nodes, the
    diameter and the maximum degree of our network,
    respectively. Both protocols require a setup phase
    in which a BFS tree is constructed. This phase takes
    $O((n+D \log n) \log \Delta)$ time.
    After the setup, $k$ point-to-point transmissions
    require $O((k+D) \log \Delta)$ time on the average.
    Therefore the network allows a new transmission every
    $O(\log \Delta)$ time slots. Also, $k$ broadcasts
    require an average of $O((k+D) \log \Delta \log n)$
    time. Hence the average throughput of the network is
    a broadcast every $O(\log \Delta \log n)$ time slots.
    Both protocols pipeline the messages along the BFS tree.
    They are always successful on the graph spanned by the
    BFS tree.  Their probabilistic behavior refers only to
    the running time.
    Using the above protocols the ranking problem is solved
    in $O(n \log n \log \Delta)$ time. The performance
    analysis of both protocols constitutes a new application
    of queuing theory.",
}