Campus Event Calendar

Event Entry

What and Who

Fast Routing Table Construction Using Small Messages

Christoph Lenzen
AG 1, AG 2, AG 3, AG 4, AG 5, RG1, SWS, MMCI  
AG Audience

Date, Time and Location

Thursday, 31 October 2013
60 Minutes
E1 4


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.


Kurt Mehlhorn
--email hidden
passcode not visible
logged in users only

Kurt Mehlhorn, 10/22/2013 16:02
Kurt Mehlhorn, 10/22/2013 11:30 -- Created document.