  This paper studies the complexity of distributed construction of purely
additive spanners in the CONGEST model. We describe algorithms for building
such spanners in several cases. Because of the need to simultaneously make
decisions at far apart locations, the algorithms use additional mechanisms
compared to their sequential counterparts.
  We complement our algorithms with a lower bound on the number of rounds
required for computing pairwise spanners. The standard reductions from
set-disjointness and equality seem unsuitable for this task because no specific
edge needs to be removed from the graph. Instead, to obtain our lower bound, we
define a new communication complexity problem that reduces to computing a
sparse spanner, and prove a lower bound on its communication complexity using
information theory. This technique significantly extends the current toolbox
used for obtaining lower bounds for the CONGEST model, and we believe it may
find additional applications.
