We present a randomized protocol that achieves broadcast in time which is optimal up to a logarithmic factor. Namely, with probability 1-epsilon, the protocol achieves broadcast in time O((D + log (n/epsilon)) cdot log n), where n is the number of processors in the network and D is the network's diameter. On the other hand, we prove a linear lower bound on the deterministic time-complexity of broadcast in this model. Namely, we show that deterministic broadcast protocols, requires THETA(n) rounds to guarantee delivery to all n processors in the network, even if the network has diameter 5, and n is known to all processors. These results put together demonstrate an exponential gap in complexity between randomization and determinism.
The paper appeared in the Journal of Computer and system Sciences, Vol. 45, (1992), pages 104-126.
The issue is what happens when several meighbors transmit at the same time. By our intuition (and original model) the outcome in this case is unexpected, whereas the stronger model defined in the paper postulates that the outcome is as in case there is no transmissions. That is, there are three possible events (w.r.t transmission by the neighbour set) (1) no transmission, (2) single transmission, and (3) multiple transmission (i.e., "conflict"). In all models, events (1) and (2) are distinguishable, and the issue is event (3). In the conflict detection model, the three events are distinguishable. The so-called ``no conflict detection'' alternative studied in BGI (and other works) is more pessimistic: it asserts that the bad event (3) may be indistinguishable from event (1). In fact, the model presented in [BGI] (and adopted by subsequent work) states that (3) is always indistinguishable from event (1), whereas both are distinguishable from (2). But by the same logic that underlies the `no conflict detection'' alternative, one may postulate that (3) may be indistinguishable also from (2); that is, (3) may be indistinguishable from either (1) or (2), with the choice left to the worst-case (or an adversary). (It is especially odd when one can (like with procedure ECHO of [KP02]) capitalize on the distinguishability of (2) and (3); that is, benefit from having somebody create noise on purpose.)
That is, the issue is whether (3) is always indistinguishable from (1), which is the model formulated in [BGI], or whether (3) may sometimes look like (1) and sometimes look like (2), with the choice being left to worst-case. We refer to the latter model as the most pessimistic model, and claim that it is at least as natural than the model in [BGI]. Still, the ``model as in [BGI]'' is simpler to state and has been the focus of all subsequent work.
The facts are that the results in [BGI] do not hold for the model presented in [BGI] but do hold for the most pessimistic model. The flaw in [BGI] is due to a single point; that is, the proof of Lemma 7. The way the function g is defined in that proof, makes the explorer answer the protocol in a way that is consistent with the most pessimistic model (but not with the model of [BGI]). (Unfortunately, the proof in [BGI] is too terse to make this point clear.) Consequently, although Lemma 7 is wrong (as stated w.r.t the [BGI] model) it is correct w.r.t the most pessimistic model. The rest of the proof remains unchanged and correct.
An after-thought: All abstract models may carry reality to an unreasonable extreme, but it seems better to be overly pessimstic than overly optimistic. Thus, it is better to have unrealistic events justify negative results than have them justify poisitive ones. Still, for sure, the flaw pointed by [KP02] and the discovery of the distiction between the two models are good news, and may even lead to further good news (i.e., further study of these issues).
For further details, see our errata notice (2002), and its revision (2003).