Lenzen's Distributed Routing Generalized: A Full Characterization of Constant-Time Routability

A celebrated and widely used result of Lenzen and Wattenhofer [STOC’11, PODC’13] shows a constant-round (deterministic) distributed routing algorithm for the complete-graph network: if each node is the source or destination of at most Θ(n) packets, there is a constant-round deterministic distributed algorithm that routes all packets to their destinations in a constant number of rounds, on the complete-graph network. We study generalizations of this result to arbitrary network graphs and show a necessary and sufficient condition for the network so that it can route any such demand in constant rounds distributedly. One can easily see that just for the existence of a constant-round routing for all such demands, it is necessary that any cut’s size, when normalized by the number of possible edges in that cut, should be lower bounded by a positive constant. That is, for any partition of nodes with exactly k∈ [1, n/2] nodes on one side, the cut should have at least Θ(kn) edges. We call this a graph with a positive minimum normalized cut, or a positive graph for short. We show that this necessary condition is also sufficient. In particular, by tightening the Leighton-Rao multicommodity max-flow min-cut theorem for positive graphs, we show the existence of a constant-round routing in positive graphs (assuming the network graph is known globally). Then, as the main technical contribution of this paper, we also show that there is a (deterministic) distributed algorithm that computes such a constant-round routing in constant rounds in these graphs. This result allows us to vastly relax the conditions of the well-studied congested clique model of distributed computing: Any distributed algorithm for the congested clique model can be run in any positive graph network, without any asymptotic slow-down. Our results are in fact more general and they give a distributed routing bound for any network, as a function of its minimum normalized cut size (and without assuming it is a constant), within a polynomial of the relevant lower bound.