On Efficient Distributed Construction of Near Optimal Routing Schemes
Michael Elkin, Ofer Neiman · 2016
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(n1/2+1/k+D)⋅ no(1) rounds, where D is the hop-diameter of the network. The running time nearly matches the lower bound of Ω(n1/2+D) rounds (which holds for any scheme with polynomial stretch). The routing tables are of size Õ(n1/k), the labels are of size O(k log2n), and every packet is routed on a path suffering stretch at most 4k-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 [LP13a, STOC 2013] and [LP15, PODC 2015]. The former has similar properties but suffers 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 ⋅ n1/k,n2/3+2/(3k)+D}).