Communication-time trade-offs in network synchronization
Communication-time trade-offs in network synchronization
复制标题
网络同步中的通信时间权衡
DOI：
10.1145/323596.323621
复制
发表时间：
1985
影响因子：
0.5
通讯作者：
B. Awerbuch
中科院分区：
文献类型：
--
作者：
B. Awerbuch
在本文中，我们在文献中首次证明，通信 - 时间的权衡是异步网络本质所固有的。我们通过证明网络同步这一非常基本问题的复杂度下界来说明这一现象。即，我们表明这个问题的任何解决方案在其最坏情况的通信复杂度和时间复杂度之间都呈现出某种权衡。这个下界在一个常数因子内与已知的上界（由作者给出）相匹配。我们的证明涉及极值图论中的一些重要定理。
1. 模型
在本文中，我们在两种网络模型中处理分布式算法。异步网络是一个点对点（存储 - 转发）通信网络，由一个无向通信图$(V, E)$描述，其中节点集$V$代表网络的处理器，链路集$E$代表它们之间双向无干扰的通信信道。节点的处理器不共享公共内存，并且每个节点都有一个不同的标识。每个节点处理从其邻居接收到的消息，执行本地计算，并向其邻居发送消息。假设所有这些操作都在零时间内完成。消息具有任意长度，并且可能携带无限量的信息。一个节点发送给其邻居的每个消息都会在某个有限但不可预测的时间内到达。这个模型也出现在[A - 84]、[Cr82]等文献中。
在同步网络中，只允许在全局时钟的整数时刻，即脉冲时刻发送消息。每个节点都可以访问这个时钟。在某个脉冲时刻，一条给定的链路上最多只能发送一个消息。每条链路的延迟最多为全局时钟的一个时间单位。
以下复杂度度量用于评估在上述两种网络模型中运行的算法的性能。通信复杂度$C$是算法期间发送的消息总数。同步算法的时间复杂度$T$是从其……以来经过的脉冲数。
In this paper we prove, for the first time in the literature, that the communication-time trade-off is intrinsic to the nature of asynchronous networks. We exemplify this phenomena by proving a lower bound on the complexity of a very fundamental problem of network Synchronization. Namely, we show that any solution of this problem e×hibits a certain trade-off between its worst-case communication and time complexities. 'l'l~is lower bound matches the known upper bounds (due to the author) within a constant factor. Our proof involves some heavy theorems in extremal graph theory. 1. "llae Model In this paper, we are dealing with distributed algorithms in two network models. The asynchro-nous network is a point-to-point (store-and-forward) communication network, described by an undirected communicalion graph (V,E) where the set of nodes V represents processors of the network and the set of links E represents bidirec-Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Association for Computing Machinery. To copy otherwise, or to republish, requires a fee and/or specific permission. tional non-interfering communication channels operating between them. No common memory is shared by the node's processors and each node has a distinct identity. Each node processe:~ messages received from its neighbors, performs local computations , and sends messages to its neighbors. All these actions are assumed to be performed in zero time. "lhe messages have an arbitrary length, and may carry unbounded an~ount of information. Each message sent by a node to its neighbor arrives to it within some finite but unpredictable time. This model appears also in [A-841,[Cr821, etc. In the synchronous network, messages are allowed to be sent only at integer times, or pulses, of a global clock. Each node has an access to this clock. At most one message can be sent over a given link at a certain pulse. The delay of each link is at most one time unit of the global clock. qhe following complexity measures are used to evaluate performances of algorithms operating in the two network models above. 'lhe Communication Complexity, Cis the total number of messages sent during the algorithm. 'lhe Time Complexity, Tofa synchronous algorithm is the number of pulses, passed since its …