Locality Dilution Law

Abstract

From the Bandwidth Collapse Theorem to Locality Dilution and Bandwidth Collapse This work represents the rigorous evolution of the original Bandwidth Collapse Theorem. The earlier formulation identified a fundamental phenomenon in hierarchical interconnects: as a system grows, an increasing fraction of communication crosses slower architectural boundaries, causing the effective bandwidth perceived by applications to deteriorate toward the capacity of the weakest tier. Further analysis showed, however, that this intuition contained two distinct effects that must not be conflated. The first is locality dilution: the fraction of communicating pairs that remain within a fast local domain decreases as the system expands. The second is bandwidth collapse under concurrent demand: the aggregate traffic generated by many simultaneous communications eventually exceeds the capacity of the physical cuts separating the domains. The present paper replaces the original single conservation-law interpretation with a more precise framework based on demand matrices, physical topology and cut capacity. It proves when locality-weighted bandwidth converges toward slower hierarchy levels, establishes the conditions required for that convergence in arbitrary multi-level systems, and derives unconditional max-flow/min-cut lower bounds for collective communication. This refinement also clarifies the role of software. Routing and scheduling cannot overcome a physical cut for a fixed demand matrix. Algorithms can nevertheless reorganise communication, aggregate data and reshape the demand presented to the network. Consequently, part of an observed slowdown may be architectural, part algorithmic, and part an unresolved gap between a constructive algorithm and the available lower bound. For AllReduce, the paper provides both a topology-oblivious ring analysis and a constructive hierarchical algorithm. Under an explicit non-blocking reference model, the inter-domain phase approaches the cut floor within a factor smaller than two, while the complete three-phase algorithm is proved to be a less-than-four approximation to the optimum. On the reference configuration, the analysis separates a demonstrated 4.63×4.63\times algorithmic improvement, a 1.125×1.125\times architectural cut-floor ratio, and a remaining 3.43×3.43\times optimality gap whose recoverable fraction is not yet known. The evolution was necessary because attributing every performance loss to hierarchy would overstate the architectural result and understate what software can recover. The revised theory therefore makes a stronger and more falsifiable claim: hierarchy imposes unavoidable limits determined by physical cuts, but the magnitude observed in practice depends equally on topology, traffic structure and collective algorithm design. Rather than presenting bandwidth collapse as an unconditional universal conservation law, this work establishes precisely what collapses, under which demand patterns, at what asymptotic rate, and which part of the loss is genuinely irreducible. The result is a more rigorous design framework for AI clusters, HPC systems, PCIe fabrics, networks-on-chip and hyperscale datacenters.