next up previous
Next: Definitions and Properties of Up: The Technion Period (1986-94) Previous: On Completeness and Soundness

A Trade-off between Information and Communication in Broadcast Protocols

The main result is a linear (in the number of edges) lower bound on the (message) complexity of broadcast in the standard point-to-point network model.


Comments: Authored by B. Awerbuch, O. Goldreich, D. Peleg and R. Vainish. Appeared in



Oded Goldreich
2003-07-30