  This paper presents new deterministic and distributed low-diameter
decomposition algorithms for weighted graphs. In particular, we show that if
one can efficiently compute approximate distances in a parallel or a
distributed setting, one can also efficiently compute low-diameter
decompositions. This consequently implies solutions to many fundamental
distance based problems using a polylogarithmic number of approximate distance
computations.
  Our low-diameter decomposition generalizes and extends the line of work
starting from [Rozho\v{n}, Ghaffari STOC 2020] to weighted graphs in a very
model-independent manner. Moreover, our clustering results have additional
useful properties, including strong-diameter guarantees, separation properties,
restricting cluster centers to specified terminals, and more. Applications
include:
  -- The first near-linear work and polylogarithmic depth randomized and
deterministic parallel algorithm for low-stretch spanning trees (LSST) with
polylogarithmic stretch. Previously, the best parallel LSST algorithm required
$m \cdot n^{o(1)}$ work and $n^{o(1)}$ depth and was inherently randomized. No
deterministic LSST algorithm with truly sub-quadratic work and sub-linear depth
was known.
  -- The first near-linear work and polylogarithmic depth deterministic
algorithm for computing an $\ell_1$-embedding into polylogarithmic dimensional
space with polylogarithmic distortion. The best prior deterministic algorithms
for $\ell_1$-embeddings either require large polynomial work or are inherently
sequential.
  Even when we apply our techniques to the classical problem of computing a
ball-carving with strong-diameter $O(\log^2 n)$ in an unweighted graph, our new
clustering algorithm still leads to an improvement in round complexity from
$O(\log^{10} n)$ rounds [Chang, Ghaffari PODC 21] to $O(\log^{4} n)$.
