  Healing algorithms play a crucial part in distributed P2P networks where
failures occur continuously and frequently. Several self-healing algorithms
have been suggested recently [IPDPS'08, PODC'08, PODC'09, PODC'11] in a line of
work that has yielded gradual improvements in the properties ensured on the
graph. This work motivates a strong general phenomenon of edge-preserving
healing that aims at obtaining self-healing algorithms with the constraint that
all original edges in the graph (not deleted by the adversary), be retained in
every intermediate graph.
  The previous algorithms, in their nascent form, are not explicitly edge
preserving. In this paper, we show they can be suitably modified (We introduce
Xheal+, an edge-preserving version of Xheal[PODC'11]). Towards this end, we
present a general self-healing model that unifies the previous models. The main
contribution of this paper is not in the technical complexity, rather in the
simplicity with which the edge-preserving property can be ensured and the
message that this is a crucial property with several benefits. In particular,
we highlight this by showing that, almost as an immediate corollary, subgraph
densities are preserved or increased. Maintaining density is a notion motivated
by the fact that in certain distributed networks, certain nodes may require and
initially have a larger number of inter-connections. It is vital that a healing
algorithm, even amidst failures, respect these requirements. Our suggested
modifications yield such subgraph density preservation as a by product. In
addition, edge preservation helps maintain any subgraph induced property that
is monotonic. Also, algorithms that are edge-preserving require minimal
alteration of edges which can be an expensive cost in healing - something that
has not been modeled in any of the past work.
