A Tradeoff Between Information and Communication in Broadcast Protocols.pdf

A Tradeo Between Information andCommunication in Broadcast Protocols(Revised version)Baruch Awerbuch 1 Oded Goldreich 2 David Peleg 3 Ronen Vainish 2AbstractThis paper concerns the message complexity of broadcast in arbitrary point-to-point communication networks. Broadcast is a task initiated by a single processorthat wishes to convey a message to all processors in the network. We assume thewidely accepted model of communication networks, in which each processor initiallyknows the identity of its neighbors, but does not know the entire network topology.Although it seems obvious that the number of messages required for broadcast in thismodel equals the number of links, no proof of this basic fact has been given before.We show that the message complexity of broadcast depends on the exact com-plexity measure. If messages of unbounded length are counted at unit cost, thenbroadcast requires (jV j) messages, where V is the set of processors in the network.We prove that if one counts messages of bounded length then broadcast requires (jEj)messages, where E is the set of edges in the network.Assuming an intermediate model in which each vertex knows the topology of thenetwork in radius   1 from itself, we prove matching upper and lower bounds of(minfjEj; jV j1+(1) g) on the number of messages of bounded length required forbroadcast. Both the upper and the lower bounds hold for both synchronous andasynchronous network models.The same results hold for the construction of spanning trees, and various otherglobal tasks.1Dept. of Math., MIT, Cambridge, MA 02139, baruch@theory.lcs.mit.edu Partially supportedby Air Force contract TNDGAFOSR-86-0078, ARO contract DAAL03-86-K-0171 and NSF contractCCR8611442.2Dept. of Computer Science, Technion, Haifa, 32000, Israel. Partially supported by the NewYork Metropolitan Research Fund.3Dept. of Computer Science, Stanford University, Stanford CA 94305. Partially supported byONR contract N00014-85-C-0731. 1 1 IntroductionBroadcast [DM]