论文标题
拥挤集团中的容忍故障图实现
Fault-Tolerant Graph Realizations in the Congested Clique
论文作者
论文摘要
在本文中，我们研究了在崩溃故障下的分布式计算集团模型中的图形实现问题。我们考虑{\ em Leger-sequence实现}，其中每个节点$ v $与学位值$ d（v）$相关联，并且如果可以使用给定学位构建覆盖网络，则结果序列是可以实现的。 我们的主要结果是$ O（f）$ - 圆形确定性算法，用于$ n $ node拥挤集团中的学位序列实现问题，其中$ f $ nodes可能是错误的（$ f <n $）。该算法使用$ O（n^2）$消息。我们将结果与下限进行补充，以表明该算法同时散布了W.R.T的数量和消息。 我们还将结果扩展到节点电容集团（NCC）模型，在该模型中，每个节点仅限于每回合发送和接收最高的$ O（\ log n）$消息。在NCC模型中，我们的算法解决了$ O（nf/\ log n）$ grounds和$ o（n^2）$消息中的学位序列实现。 对于这两种设置，我们的算法都在不了解$ f $的情况下工作，这是故障的数量。据我们所知，这些是崩溃错误分布式网络中图形实现问题的第一个结果。
In this paper, we study the graph realization problem in the Congested Clique model of distributed computing under crash faults. We consider {\em degree-sequence realization}, in which each node $v$ is associated with a degree value $d(v)$, and the resulting degree sequence is realizable if it is possible to construct an overlay network with the given degrees. Our main result is a $O(f)$-round deterministic algorithm for the degree-sequence realization problem in a $n$-node Congested Clique, of which $f$ nodes could be faulty ($f<n$). The algorithm uses $O(n^2)$ messages. We complement the result with lower bounds to show that the algorithm is tight w.r.t the number of rounds and the messages simultaneously. We also extend our result to the Node Capacitated Clique (NCC) model, where each node is restricted to sending and receiving at-most $O(\log n)$ messages per round. In the NCC model, our algorithm solves degree-sequence realization in $O(nf/\log n)$ rounds and $O(n^2)$ messages. For both settings, our algorithms work without the knowledge of $f$, the number of faults. To the best of our knowledge, these are the first results for the graph realization problem in the crash-fault distributed network.
