Title: On Efficient Distributed Construction of Near Optimal Routing Schemes.

Authors: Michael Elkin and Ofer Neiman.

Abstract:

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 $(n^{1/2+3/(2k)}+D)\cdot n^{o(1)}$ rounds, where $D$ is the hop-diameter of the network. The running 
time nearly matches the lower bound of $\tilde{\Omega}(n^{1/2}+D)$ rounds (which holds for any scheme with polynomial stretch). The routing tables 
are of size $\tilde{O}(n^{1/k})$, the labels are of size $O(k\log^2n)$, 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(n^{1/2+1/k})$, while the latter has sub-optimal running time of 
$\tilde{O}(\min\{(nD)^{1/2}\cdot n^{1/k},n^{2/3+2/(3k)}+D\})$.