Fast Routing Table Construction Using Small Messages. ArXiv e-prints

We describe a distributed randomized algorithm to con-struct routing tables. Given 0 < ε ≤ 1/2, the algorithm runs in time Õ(n1/2+ε + HD), where n is the number of nodes and HD denotes the diameter of the network in hops (i.e., as if the network is unweighted). The weighted length of the produced routes is at most O(ε−1 log ε−1) times the optimal weighted length. This is the first algorithm to break the Ω(n) complexity barrier for computing weighted short-est paths even for a single source. Moreover, the algorithm nearly meets the Ω̃(n1/2 + HD) lower bound for distributed computation of routing tables and approximate distances (with optimality, up to polylog factors, for ε = 1 / logn). The presented techniques have many applications, including improved distributed approximation algorithms for Gener-alized Steiner Forest, all-pairs distance estimation, and esti-mation of the weighted diameter