Optimal Lower Bounds for Some Distributed Algorithms for a Complete Network of Processors
Optimal Lower Bounds for Some Distributed Algorithms for a Complete Network of Processors
复制标题
完整处理器网络的某些分布式算法的最佳下界
DOI：
10.1016/0304-3975(89)90103-5
复制
发表时间：
1989
期刊：
影响因子：
--
通讯作者：
S. Zaks
中科院分区：
文献类型：
--
作者：
E. Korach;S. Moran;S. Zaks
讨论了完整处理器网络（即每对处理器通过通信线路连接的网络）的分布式算法的下界。我们首先展示了此类网络的给定类分布式算法中任何算法所需消息数量的 Ω (n log n) 下限。此类包括针对寻找领导者或构建生成树等问题的算法。然后，我们显示其他问题的 Ω (n 2) 下界，例如构造最大匹配或哈密顿电路。在证明下界时，我们对算法执行期间携带消息的边进行计数（忽略每个边携带的实际消息数）。有趣的是，这个数字与这些算法所需的消息总数具有相同的数量级。下界的证明适用于同步网络和任意长的消息。
Lower bounds for distributed algorithms for complete networks of processors (ie, networks where each pair of processors is connected by a communication line) are discussed. We first show an Ω (n log n) lower bound for the number of messages required by any algorithm in a given class of distributed algorithms for such networks. This class includes algorithms for problems like finding a leader or constructing a spanning tree. We then show an Ω (n 2) lower bound for other problems, like constructing a maximal matching or a Hamiltonian circuit. In proving the lower bounds we are counting the edges which carry messages during the executions of the algorithms (ignoring the actual number of messages carried by each edge). Interestingly, this number is shown to be of the same order of magnitude as the total number of messages needed by these algorithms. The proofs of the lower bounds apply for synchronous networks and for arbitrarily long messages.