This theoretical computer science paper resolves the main open problem of Dwork, Peleg, Pippenger, and Upfal (DPPU86) on almost-everywhere reliable message transmission: constructing a sparse communication network on which honest parties can still communicate even when an adversary corrupts a constant fraction of the network. The authors give the first construction of constant-degree networks that admit efficient (polylogarithmic work and round complexity) fault-tolerant routing protocols while tolerating a constant fraction of adversarial edge-faults, simultaneously achieving sparsity, efficiency, and constant fault-tolerance that prior work could only obtain separately. The central contribution is a composition technique (Lemma 3.1) for fault-tolerant communication networks, built on the balanced replacement graph product of Reingold-Vadhan-Wigderson, that combines two edge-fault-tolerant networks into a new network of smaller degree while preserving efficiency and tolerance. Applying this composition repeatedly to the high-dimensional-expander-based polylog-degree networks of BMV24 and then to the constant-degree networks of Upfal yields the final result, which in turn gives sparse networks supporting almost-everywhere Byzantine agreement and secure multi-party computation with only polylogarithmic overhead.
This theoretical computer science paper resolves the main open problem of Dwork, Peleg, Pippenger, and Upfal (DPPU86) on almost-everywhere reliable message transmission: constructing a sparse communi…