Tight lower and upper bounds for some distributed algorithms for a complete network of processors
Tight lower and upper bounds for some distributed algorithms for a complete network of processors
复制标题
完整处理器网络的某些分布式算法的严格下限和上限
DOI：
10.1145/800222.806747
复制
发表时间：
1984
期刊：
影响因子：
--
通讯作者：
S. Zaks
中科院分区：
文献类型：
--
作者：
E. Korach;S. Moran;S. Zaks
讨论了处理器的完全异步网络(即，其中每对处理器通过通信线路连接的网络)的分布式算法。主要结果是此类网络的给定分布式算法中的任何算法所需消息数量的<；italic>；O<；/italic>；(<；italic>；nlogn<；/italic>；)下界和上限。这一类包括寻找领导者或构建生成树等问题的算法(据我们所知，这些问题的所有已知算法在应用于完整网络时可能需要<；italic>；O<；/italic>；(<；italic>；n<；/italic>；<；supscrpt>；2<；/supscrpt>；)消息)。还给出了构造极大匹配或哈密顿回路等问题的<；italic>；O<；/italic>；(<；italic>；n<；/italic>；<；supscrpt>；2<；/supscrpt>；)界。在证明下界时，我们计算的是在算法执行期间携带消息的边(忽略每条边实际携带的消息数量)。有趣的是，这个数字与这些算法所需的消息总数具有相同的数量级。在上限中，任何消息的长度最多为log<；subscrpt>；2<；/subscrpt>；[4<；italic>；mlog<；/italic>；<；subscrpt>；2<；/subscrpt>；<；italic>；n<；/italic>；]比特，其中<；italic；m<；/italic&>是网络中节点的最大标识。我们的结果的一个含义是，在完全网络中寻找生成树比在这样的网络中寻找最小权重的生成树更容易，后者可能需要<；italic>；O<；/italic>；(<；italic>；n<；/italic>；<；supscrpt>；2<；/supscrpt>；)消息。
Distributed algorithms for complete asynchronous networks of processors (i.e., networks where each pair of processors is connected by a communication line) are discussed. The main result is <italic>O</italic>(<italic>nlogn</italic>) lower and upper bounds on 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 (as far as we know, all known algorithms for those problems may require <italic>O</italic>(<italic>n</italic><supscrpt>2</supscrpt>) messages when applied to complete networks). <italic>O</italic>(<italic>n</italic><supscrpt>2</supscrpt>) bounds for other problems, like constructing a maximal matching or a Hamiltonian circuit are also given. In proving the lower bound we are counting the edges which carry messages during the executions of the algorithms (ignoring the actually number of messages carried by each edge). Interestingly, this number is shown to be of the same order of magnitude of the total number of messages needed by these algorithms. In the upper bounds, the length of any message is at most log<subscrpt>2</subscrpt>[4<italic>mlog</italic><subscrpt>2</subscrpt><italic>n</italic>] bits, where <italic>m</italic> is the maximum identity of a node in the network. One implication of our results is that finding a spanning tree in a complete network is easier than finding a minimum weight spanning tree in such a network, which may require <italic>O</italic>(<italic>n</italic><supscrpt>2</supscrpt>) messages.