  In the minimum $k$-edge-connected spanning subgraph ($k$-ECSS) problem the
goal is to find the minimum weight subgraph resistant to up to $k-1$ edge
failures. This is a central problem in network design, and a natural
generalization of the minimum spanning tree (MST) problem. While the MST
problem has been studied extensively by the distributed computing community,
for $k \geq 2$ less is known in the distributed setting.
  In this paper, we present fast randomized distributed approximation
algorithms for $k$-ECSS in the CONGEST model. Our first contribution is an
$\widetilde{O}(D + \sqrt{n})$-round $O(\log{n})$-approximation for 2-ECSS, for
a graph with $n$ vertices and diameter $D$. The time complexity of our
algorithm is almost tight and almost matches the time complexity of the MST
problem. For larger constant values of $k$ we give an $\widetilde{O}(n)$-round
$O(\log{n})$-approximation. Additionally, in the special case of unweighted
3-ECSS we show how to improve the time complexity to $O(D \log^3{n})$ rounds.
All our results significantly improve the time complexity of previous
algorithms.
