标题： 常度网络用于几乎处处可靠传输 显示英文标题

标题： Constant Degree Networks for Almost-Everywhere Reliable Transmission

摘要： 在几乎处处可靠的报文传输问题中，由[Dwork, Pippenger, Peleg, Upfal'86]提出，目标是设计一个稀疏通信网络$G$，该网络支持所有节点对之间的高效、容错协议。 所谓容错，意味着即使对手破坏了$G$中的少量顶点，几乎所有顶点仍可以通过构建的协议完美通信。 成功做到这一点允许在稀疏图上模拟任何容错分布式计算任务和为完整网络构建的安全多方计算协议，仅需最小的效率开销。 此前的研究要么实现了容忍$o(1)$故障的常数度网络，要么通过低效协议（指数工作复杂度）实现了容忍常数比例故障的常数度网络，或者实现了容忍常数比例故障的多对数度网络。 我们展示了一个具有高效协议（即，具有多对数工作复杂度）的常数度网络，可以容忍常数比例的对抗故障，从而解决了Dwork等人提出的主要开放问题。我们的主要贡献是一种基于图乘积的通信网络组合技术。 我们的技术结合了两个容忍对抗边故障的网络，以构建一个度更小的网络，同时保持效率和容错性。 我们多次应用这一组合结果，将最近[Bafna, Minzer, Vyas'24]工作中构建的多对数度边故障容错网络（基于高维扩展器）与自身结合，然后再与[Upfal'92]中的常数度网络（尽管协议效率较低）结合。 显示英文摘要

摘要： In the almost-everywhere reliable message transmission problem, introduced by [Dwork, Pippenger, Peleg, Upfal'86], the goal is to design a sparse communication network $G$ that supports efficient, fault-tolerant protocols for interactions between all node pairs. By fault-tolerant, we mean that that even if an adversary corrupts a small fraction of vertices in $G$, then all but a small fraction of vertices can still communicate perfectly via the constructed protocols. Being successful to do so allows one to simulate, on a sparse graph, any fault-tolerant distributed computing task and secure multi-party computation protocols built for a complete network, with only minimal overhead in efficiency. Previous works on this problem achieved either constant-degree networks tolerating $o(1)$ faults, constant-degree networks tolerating a constant fraction of faults via inefficient protocols (exponential work complexity), or poly-logarithmic degree networks tolerating a constant fraction of faults. We show a construction of constant-degree networks with efficient protocols (i.e., with polylogarithmic work complexity) that can tolerate a constant fraction of adversarial faults, thus solving the main open problem of Dwork et al.. Our main contribution is a composition technique for communication networks, based on graph products. Our technique combines two networks tolerant to adversarial edge-faults to construct a network with a smaller degree while maintaining efficiency and fault-tolerance. We apply this composition result multiple times, using the polylogarithmic-degree edge-fault tolerant networks constructed in a recent work of [Bafna, Minzer, Vyas'24] (that are based on high-dimensional expanders) with itself, and then with the constant-degree networks (albeit with inefficient protocols) of [Upfal'92].