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 distributed algorithm that computes a routing scheme in O(n^1/2+1/k+D)·n^o(1) rounds, where D is the hopdiameter of the network. The 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 ω(n^1/k), the labels are of size O(k log² n), and every packet is routed on a path suering stretch at most 4k..5+o(1). Our construction nearly matches the state-ofthe- 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 [LP13a, STOC 2013] and [LP15, PODC 2015]. The former has similar properties but suers from substantially larger routing tables of size O(^n1/2+1/k), while the latter has sub-optimal running time of ω(min{(nD)^1/2 · n^1/k, n^2/3+2/(3k) + Dg).