A trade-off between information and communication in broadcast protocols
A trade-off between information and communication in broadcast protocols
复制标题
广播协议中信息和通信之间的权衡
DOI：
10.1145/77600.77618
复制
发表时间：
1990
期刊：
影响因子：
--
通讯作者：
Ronen Vainish
中科院分区：
文献类型：
--
作者：
B. Awerbuch;Oded Goldreich;D. Peleg;Ronen Vainish
本文研究任意点到点通信网络中广播的消息复杂度。<italic>广播</italic>是由<italic>单个</italic>处理器发起的任务，该任务希望将消息传送到网络中的所有处理器。被广泛接受的通信网络模型，其中每个处理器最初知道它的邻居的身份，但不知道整个网络拓扑结构，假设。虽然在这个模型中广播所需的消息数等于链接数似乎是显而易见的，但以前没有给出这个基本事实的证明。
结果表明，广播的消息复杂度依赖于精确的复杂度度量。如果无限长的消息以单位成本计算，则广播需要（N V）条消息，其中<italic>V</italic>是网络中的处理器集合。<italic></italic>证明了，如果计算<italic>有界长度</italic>的消息，则广播需要（<italic>E</italic>）消息，其中<italic>E</italic>是网络中的边的集合。
假设一个中间模型，其中每个顶点都知道半径≥ 1的网络拓扑，证明了（min{n<italic>E_</italic> n，n<italic>V</italic>_n<supscrpt>1+（l）/&rgr;</supscrpt>}）在广播所需的有界长度消息数上的匹配上、下界.上界和下界对于同步和异步网络模型都成立。
同样的结果也适用于生成树的构造和其他各种全局任务。
This paper concerns the message complexity of broadcast in arbitrary point-to-point communication networks. <italic>Broadcast</italic> is a task initiated by a <italic>single</italic> processor that wishes to convey a message to all processors in the network. The widely accepted model of communication networks, in which each processor initially knows the identity of its neighbors but does not know the entire network topology, is assumed. Although it seems obvious that the number of messages required for broadcast in this model equals the number of links, no proof of this basic fact has been given before.
It is shown that the message complexity of broadcast depends on the exact complexity measure. If messages of unbounded length are counted at unit cost, then broadcast requires &THgr;(↿<italic>V</italic>↾) messages, where <italic>V</italic> is the set of processors in the network. It is proved that, if one counts messages of <italic>bounded length</italic>, then broadcast requires &THgr;(↿<italic>E</italic>↾) messages, where <italic>E</italic> is the set of edges in the network.
Assuming an intermediate model in which each vertex knows the topology of the network in radius <italic>&rgr;</italic> ≥ 1 from itself, matching upper and lower bounds of &THgr;(min{↿<italic>E</italic>↾, ↿<italic>V</italic>↾<supscrpt>1+&THgr;(l)/&rgr;</supscrpt>}) is proved on the number of messages of bounded length required for broadcast. Both the upper and lower bounds hold for both synchronous and asynchronous network models.
The same results hold for the construction of spanning trees, and various other global tasks.