@Article{Riv87a,
  author = 	 { Ronald L. Rivest },
  title = 	 { Network control by {B}ayesian broadcast },
  journal = 	 { IEEE Trans. on Information Theory },
  issn =         { 0018-9448 },                  
  OPTyear = 	 { 1987 },
  OPTmonth = 	 { May },
  date =         { 1987-05 },                  
  volume = 	 { IT-33 },
  number = 	 { 3 },
  pages = 	 { 323--328 },
  publisher =    { IEEE },                  
  doi =          { 10.1109/TIT.1987.1057315 },                  
  abstract =     {
         A transmission control strategy is described for slotted-ALOHA-type
         broadcast channels with ternary feedback.  At each time slot, each
         station estimates the probability that $n$ stations are ready to
         transmit a packet for each $n$, using Bayes' rule and the observed
         history of collisions, successful transmissions, and holes (empty 
         slots).  A station transmits a packet in a probabilistic manner
         based on these estimates.  This strategy is called Bayesian broadcast.
         An elegant and very practical strategy---pseudo-Bayesian broadcast---is
         then derived by approximating the probability estimates with a Poisson
         distribution with mean $\nu$ and further simplifying.  Each station
         keeps a copy of $\nu$, transmits a packet with probability $1/\nu$,
         and then updates $\nu$ in two steps:
         \begin{itemize}
             \item For collisions, increment $\nu$ by $(e-2)^{-1} = 1.39221\cdots$.
                   For successes and holes, decrement $\nu$ by $1$.
             \item Set $\nu$ to $\max(\nu+\hat{\lambda},1)$, where $\hat{\lambda}$
                   is an estimate of the arrival rate $\lambda$ of new packets 
                   into the system.
         \end{itemize}                  
         Simulation results are presented showing that pseudo-Bayesian broadcast
         performs well in practice, and methods that can be used to prove that
         certain versions of pseudo-Bayesian broadcast are stable for $\lambda < e^{-1}$
         are discussed.                          
                 },
}