论文标题
针对对抗边缘的广播拥塞算法
Broadcast CONGEST Algorithms against Adversarial Edges
论文作者
论文摘要
我们考虑使用自适应对手的角石广播任务，该任务控制输入通信图中固定数量的$ t $边缘。在此模型中，对手看到网络中的整个通信和节点的随机硬币，同时恶意操纵通过一组$ t $边缘发送的消息（节点未知）。由于[Pease，Shostak和Lamport，JACM'80]的有影响力的工作，已经研究了针对大量对抗模型的广播算法，在理论和实践中都研究了超过四十年。尽管进行了广泛的研究，但在分布式计算的交通拥堵模型中，尚无圆形有效的广播算法。我们提供针对自适应边缘对手的第一个圆形广播算法。我们的两个关键结果，用于直径$ d $的$ n $ node图如下： 1。对于$ t = 1 $，有一个确定性算法可以在$ \ widetilde {o}（d^2）$ rounds中解决该问题，但前提是该图是3 edge连接的。这种圆形复杂性超过了$ o（d^3）$ rounds的自然障碍，这是在$ g $中给定的一对节点之间的最大长度上的生存下限。该算法可以将其扩展到$ \ widetilde {o}（d^{o（t）}）$ - 圆形算法与$（2T+1）$ edge-edence-ednectements的图形相对于$ t $ verversial边缘。 2。对于$ω（t ^2 \ log n）$的扩展器图，有一种改进的广播算法，带有$ O（t \ log ^2 n）$ roughs，而$ t $ tums $。该算法利用了通过采用Karger的边缘采样技术获得的G-子图的连通性和电导性能。 我们的算法标志着耐故障网络设计和可靠的分布式通信之间的新联系。
We consider the corner-stone broadcast task with an adaptive adversary that controls a fixed number of $t$ edges in the input communication graph. In this model, the adversary sees the entire communication in the network and the random coins of the nodes, while maliciously manipulating the messages sent through a set of $t$ edges (unknown to the nodes). Since the influential work of [Pease, Shostak and Lamport, JACM'80], broadcast algorithms against plentiful adversarial models have been studied in both theory and practice for over more than four decades. Despite this extensive research, there is no round efficient broadcast algorithm for general graphs in the CONGEST model of distributed computing. We provide the first round-efficient broadcast algorithms against adaptive edge adversaries. Our two key results for $n$-node graphs of diameter $D$ are as follows: 1. For $t=1$, there is a deterministic algorithm that solves the problem within $\widetilde{O}(D^2)$ rounds, provided that the graph is 3 edge-connected. This round complexity beats the natural barrier of $O(D^3)$ rounds, the existential lower bound on the maximal length of $3$ edge-disjoint paths between a given pair of nodes in $G$. This algorithm can be extended to a $\widetilde{O}(D^{O(t)})$-round algorithm against $t$ adversarial edges in $(2t+1)$ edge-connected graphs. 2. For expander graphs with minimum degree of $Ω(t^2\log n)$, there is an improved broadcast algorithm with $O(t \log ^2 n)$ rounds against $t$ adversarial edges. This algorithm exploits the connectivity and conductance properties of G-subgraphs obtained by employing the Karger's edge sampling technique. Our algorithms mark a new connection between the areas of fault-tolerant network design and reliable distributed communication.
