  Solving linear programs is often a challenging task in distributed settings.
While there are good algorithms for solving packing and covering linear
programs in a distributed manner (Kuhn et al.~2006), this is essentially the
only class of linear programs for which such an algorithm is known. In this
work we provide a distributed algorithm for solving a different class of convex
programs which we call "distance-bounded network design convex programs". These
can be thought of as relaxations of network design problems in which the
connectivity requirement includes a distance constraint (most notably, graph
spanners). Our algorithm runs in $O( (D/\epsilon) \log n)$ rounds in the
$\mathcal{LOCAL}$ model and finds a $(1+\epsilon)$-approximation to the optimal
LP solution for any $0 < \epsilon \leq 1$, where $D$ is the largest distance
constraint. While solving linear programs in a distributed setting is
interesting in its own right, this class of convex programs is particularly
important because solving them is often a crucial step when designing
approximation algorithms. Hence we almost immediately obtain new and improved
distributed approximation algorithms for a variety of network design problems,
including Basic $3$- and $4$-Spanner, Directed $k$-Spanner, Lowest Degree
$k$-Spanner, and Shallow-Light Steiner Network Design with a spanning demand
graph. Our algorithms do not require any "heavy" computation and essentially
match the best-known centralized approximation algorithms, while previous
approaches which do not use heavy computation give approximations which are
worse than the best-known centralized bounds.
