Fast Routing Table Construction Using Small Messages

abstract: A fundamental task in distributed systems is to determine efficient routing paths between all pairs of nodes. The optimal trade-off between routing tables size and approximation ratio is fairly well-understood in this setting. However, little attention has been paid to quick distributed construction of such tables if the size of messages must be small. I will present a novel technique for distributed routing table construction and related tasks running in roughly n^(1/2)+D rounds of communication, where n is the number of nodes in the system and D the diameter of the communication graph. The table construction algorithm uses messages of size O(log n) and guarantees approximation ratio O(log n log log n). Under these constraints, our solutions are near-optimal: Every algorithm using messages of size O(log n) and achieving a polylogarithmic approximation must run for at least n^(1/2)+D rounds (up to polylogarithmic factors). In contrast, previous algorithms incur running times of Omega(n) even in unweighted graphs or graphs of constant diameter.