Prof. Michael Elkin

Given a distributed network represented by a weighted undirected graph G= (V, E) on n vertices, and a parameter k, we devise a randomized distributed algorithm that whp computes a routing scheme in O(n^1/2+1/k+ D) · n^o(1) rounds, where D is the hop-diameter of the network. Moreover, for odd k, the running time of our algorithm is O(n^1/2+1/(2k)+ D) · n^o(1). Our running time nearly matches the lower bound of Ω ~ (n^{1 / 2}+ D) rounds (which holds for any scheme with polynomial stretch). The routing tables are of size O~ (n^1/k) , the labels are of size O(klog ²n) , and every packet is routed on a path suffering stretch at most 4 k- 5 + o(1). Our construction nearly matches the state-of-the-art for routing schemes built in a centralized sequential manner. The previous best algorithms for building routing tables in a distributed small messages model were by Lenzen and Patt-Shamir (In: Symposium on theory of computing conference, STOC’13, Palo Alto, CA, USA, 2013) and Lenzen and Patt-Shamir (In: Proceedings of the 2015 ACM symposium on principles of distributed computing, PODC 2015, Donostia-San Sebastián, Spain, 2015). The former has similar properties but suffers from substantially larger routing tables of size O(n^1/2+1/k) , while the latter has sub-optimal running time of O~ (min { (nD) ^{1 / 2}· n^1/k, n^2/3+2/(3k)+ D}).