论文标题
完全缺陷的网络中的分布式计算
Distributed Computations in Fully-Defective Networks
论文作者
论文摘要
我们解决了完全缺陷的异步网络，其中所有链接均遭受无限数量的更改错误，这意味着网络中的所有消息都可能完全损坏。尽管可能直觉在于任何可靠的通信对于任何可靠的通信都过于苛刻，但我们展示了如何在任何完全缺陷的设置上模拟任何噪声设置的任何算法，鉴于网络已连接2-EDGE。我们证明，如果网络未连接2边缘，则在完全缺陷的设置中不可能进行非平凡的计算。 我们利用的2边缘连接图的关键结构特性是存在所有节点的定向（非简单）周期的存在[Robbins，1939年]。我们技术贡献的核心是在完全缺陷的网络中介绍了这样一个罗宾斯周期的构建，并展示了尽管消息腐败的彻底腐败，但如何进行沟通。这些是以内容为主的方式获得的，因为节点必须忽略接收到的消息的内容。
We address fully-defective asynchronous networks, in which all links are subject to an unlimited number of alteration errors, implying that all messages in the network may be completely corrupted. Despite the possible intuition that such a setting is too harsh for any reliable communication, we show how to simulate any algorithm for a noiseless setting over any fully-defective setting, given that the network is 2-edge connected. We prove that if the network is not 2-edge connected, no non-trivial computation in the fully-defective setting is possible. The key structural property of 2-edge-connected graphs that we leverage is the existence of an oriented (non-simple) cycle that goes through all nodes [Robbins, 1939]. The core of our technical contribution is presenting a construction of such a Robbins cycle in fully-defective networks, and showing how to communicate over it despite total message corruption. These are obtained in a content-oblivious manner, since nodes must ignore the content of received messages.
