@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. }, }