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.