A trade-off between information and communication in broadcast protocols

摘要: This paper concerns the message complexity of broadcast in arbitrary point-to-point communication networks. Broadcast is a task initiated by single processor that wishes to convey all processors network. The widely accepted model networks, which each initially knows identity its neighbors but does not know entire network topology, assumed. Although it seems obvious number messages required for this equals links, no proof basic fact has been given before.It shown depends on exact measure. If unbounded length are counted at unit cost, then requires T(uVu) messages, where V set It proved that, if one counts bounded length, T(uEu) E edges network.Assuming an intermediate vertex topology radius r ≥ 1 from itself, matching upper and lower bounds T(min{uEu, uVu1+T(l)/r}) broadcast. Both hold both synchronous asynchronous models.The same results construction spanning trees, various other global tasks.