Bandwidth-Optimal AllReduce Under Network Failures
报告人：陈沛庆(University of Maryland, College Park)
时间：2026-9-11 15:00-17:00
地点：王选厅
We investigate the optimal completion time of distributed element-wise summation (AllReduce) under asymmetric communication bandwidth, a fundamental problem arising from partial network failures in large computing clusters. The classical ring algorithm, though provably bandwidth-optimal on homogeneous links, suffers severe performance degradation in heterogeneous settings, and the underlying theoretical limits have remained open.Using information-theoretic flow counting and minimax analysis, we derive tight lower bounds on the minimum achievable completion time. A key mathematical result is that, when the number of nodes suffering bandwidth loss is sufficiently small relative to the total number of nodes p, and the slowest node retains at least half its baseline bandwidth, the unavoidable overhead relative to a fully healthy network is only \(O(1/p)\) — meaning the performance penalty becomes negligible in large clusters. The bounds exhibit a natural two-regime structure: mild bandwidth degradation is limited by the aggregate capacity of healthy links, while severe degradation is bottlenecked by the slow link itself.We then design OPTCC, an algorithm that provably attains these lower bounds. Its core idea is to carefully schedule communications so that transmissions over fast links and slow links proceed in parallel, effectively hiding the performance penalty caused by slow nodes. Simulations on a production-grade network simulator confirm our theoretical findings: under realistic network failures with up to 50% bandwidth loss, OPTCC runs within 2–6% of the fault-free optimum, substantially outperforming existing fault-tolerant schemes.
