Fast Routing Table Construction Using Small Messages

Abstract: A fundamental task in distributed systems (like the Internet) is to determine efficient routing paths between all pairs of nodes. For efficiency reasons, one frequently resorts to constructing approximate shortest path based on new node labels that encapsulate some hints on a node's location in its name. While the optimal trade-off between routing tables size and approximation ratio is fairly well-understood in this setting, little attention has been paid to quick construction of such tables in a distributed manner. This is crucial, since usually it is impractical – or even infeasible – to aggregate the topology of large systems in a single location, and in a dynamic environment the solution might be already outdated before it can be put to use.

In this talk, we present a novel technique for distributed routing table construction running in O(n^1/2+ε + D) rounds of communication (up to polylogarithmic factors in n), where n is the number of nodes in the system and D the diameter of the communication graph. Our algorithm uses messages of size O(log n) and guarantees approximation ratio O(ε⁻¹ log ε⁻¹). Under these constraints, our solution is near-optimal: Every algorithm using messages of size O(log n) and achieving a polylogarithmic approximation must run for Θ(n^1/2 + D) rounds. In contrast, previous algorithms incur running times of Θ(n) even in graphs of constant diameter. Our approach yields improved distributed algorithms for a number of related problems, including distance approximation and Generalized Steiner Forest approximation.

Biography: Christoph Lenzen received a diploma degree in Mathematics from the University of Bonn, Germany, and subsequently performed his graduate studies in Distributed Computing in the group of Professor Roger Wattenhofer at ETH Zurich. In 2011, he was a postdoctoral Fellow at the Hebrew University of Jerusalem, with Danny Dolev. Currently, he is a postdoctoral fellow at the Weizmann Institute of Science, with Professor David Peleg. In 2012 and 2013 he will be a postdoctoral fellow at MIT, with Professor Nancy Lynch. His research interests cover distributed computing in a wider sense, including topics such as randomized load balancing, graph algorithms, and clock synchronization. He published e.g. at PODC, SPAA, FOCS, and STOC, and in JACM. In 2009, he and his coauthors received the PODC best paper award for their work on gradient clock synchronization.