BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-88-1195
       ENTRY:: April 24, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: A Lower Bound for Radio Broadcast
        TYPE:: Technical Report
      AUTHOR:: Bar-Noy, A.
      AUTHOR:: Linial, N.
      AUTHOR:: Peleg, D.
        DATE:: February 1988
       PAGES:: 16
    ABSTRACT:: A radio network is a synchronous network of processors that
               communicate by transmitting messages to their neighbors,
               where a processor receives a message in a given step if and
               only if it is silent in this step and precisely one of its
               neighbors transmits. In this paper we prove the existence of
               a family of radius-2 networks on n vertices for which any
               broadcast schedule requires at least Omega((log n/ log log
               n)2) rounds of transmissions. This almost matches an upper
               bound of O(log2 n) rounds for networks of radius 2 proved
               earlier by Bar-Yehuda, Goldreich, and Itai.
       NOTES:: [Adminitrivia V1/Prg/19950424]
         END:: STAN//CS-TR-88-1195