  Network decomposition is a central concept in the study of distributed graph
algorithms. We present the first polylogarithmic-round deterministic
distributed algorithm with small messages that constructs a strong-diameter
network decomposition with polylogarithmic parameters.
  Concretely, a ($C$, $D$) strong-diameter network decomposition is a
partitioning of the nodes of the graph into disjoint clusters, colored with $C$
colors, such that neighboring clusters have different colors and the subgraph
induced by each cluster has a diameter at most $D$. In the weak-diameter
variant, the requirement is relaxed by measuring the diameter of each cluster
in the original graph, instead of the subgraph induced by the cluster.
  A recent breakthrough of Rozho\v{n} and Ghaffari [STOC 2020] presented the
first $\text{poly}(\log n)$-round deterministic algorithm for constructing a
weak-diameter network decomposition where $C$ and $D$ are both in
$\text{poly}(\log n)$. Their algorithm uses small $O(\log n)$-bit messages. One
can transform their algorithm to a strong-diameter network decomposition
algorithm with similar parameters. However, that comes at the expense of
requiring unbounded messages. The key remaining qualitative question in the
study of network decompositions was whether one can achieve a similar result
for strong-diameter network decompositions using small messages. We resolve
this question by presenting a novel technique that can transform any black-box
weak-diameter network decomposition algorithm to a strong-diameter one, using
small messages and with only moderate loss in the parameters.
