  In the distributed backup-placement problem each node of a network has to
select one neighbor, such that the maximum number of nodes that make the same
selection is minimized. This is a natural relaxation of the perfect matching
problem, in which each node is selected just by one neighbor. Previous
(approximate) solutions for backup placement are non-trivial, even for simple
graph topologies, such as dense graphs. In this paper we devise an algorithm
for dense graph topologies, including unit disk graphs, unit ball graphs, line
graphs, graphs with bounded diversity, and many more. Our algorithm requires
just one round, and is as simple as the following operation. Consider a
circular list of neighborhood IDs, sorted in an ascending order, and select the
ID that is next to the selecting vertex ID. Surprisingly, such a simple
one-round strategy turns out to be very efficient for backup placement
computation in dense networks. Not only that it improves the number of rounds
of the solution, but also the approximation ratio is improved by a
multiplicative factor of at least $2$.
  Our new algorithm has several interesting implications. In particular, it
gives rise to a $(2 + \epsilon)$-approximation to maximum matching within
$O(\log^* n)$ rounds in dense networks. The resulting algorithm is very simple
as well, in sharp contrast to previous algorithms that compute such a solution
within this running time. Moreover, these algorithms are applicable to a
narrower graph family than our algorithm. For the same graph family, the best
previously-known result has $O(\log {\Delta} + \log^* n)$ running time. Another
interesting implication is the possibility to execute our backup placement
algorithm as-is in the self-stabilizing setting. This makes it possible to
simplify and improve other algorithms for the self-stabilizing setting, by
employing helpful properties of backup placement.
