  We consider the Backup Placement problem in networks in the
$\mathcal{CONGEST}$ distributed setting. Given a network graph $G = (V,E)$, the
goal of each vertex $v \in V$ is selecting a neighbor, such that the maximum
number of vertices in $V$ that select the same vertex is minimized. The backup
placement problem was introduced by Halldorsson, Kohler, Patt-Shamir, and
Rawitz, who obtained an $O(\log n/ \log \log n)$ approximation with randomized
polylogarithmic time. Their algorithm remained the state-of-the-art for general
graphs, as well as specific graph topologies. In this paper we obtain
significantly improved algorithms for various graph topologies. Specifically,
we show that $O(1)$-approximation to optimal backup placement can be computed
deterministically in $O(1)$ rounds in graphs that model wireless networks,
certain social networks, claw-free graphs, and more generally, in any graph
with neighborhood independence bounded by a constant. At the other end, we
consider sparse graphs, such as trees, forests, planar graphs and graphs of
constant arboricity, and obtain a constant approximation to optimal backup
placement in $O(\log n)$ deterministic rounds.
  Clearly, our constant-time algorithms for graphs with constant neighborhood
independence are asymptotically optimal. Moreover, we show that our algorithms
for sparse graphs are not far from optimal as well, by proving several lower
bounds. Specifically, optimal backup placement of unoriented trees requires
$\Omega(\log n)$ time, and approximate backup placement with a polylogarithmic
approximation factor requires $\Omega(\sqrt {\log n / \log \log n})$ time. Our
results extend the knowledge regarding the question of "what can be computed
locally?", and reveal surprising gaps between complexities of distributed
symmetry breaking problems.
