2016/02/06 by Michael Elkin, Ofer Neiman, Elkin, Michael +1 · 1 citation
Computer Science · #Complexity and Algorithms in Graphs #Optimization and Search Problems #Advanced Graph Theory Research
paper · pdf · doi:10.48550/arxiv.1602.02293
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 (n1/2+1/k+D)⋅ no(1) rounds, where D is the hop-diameter of the network. The running time matches the lower bound of Ω(n1/2+D) rounds (which holds for any scheme with polynomial stretch), up to lower order terms. The routing tables are of size O(n1/k), the labels are of size O(klog2n), 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 \cite[STOC 2013]LP13 and \cite[PODC 2015]LP15. 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 O(min\(nD)1/2⋅ n1/k,n2/3+2/(3k)+D\).