New application scenarios, such as Internet-scale computations, nomadic networks and mobile systems, require decentralized, scalable and open infrastructures. The peer-to-peer (P2P) paradigm has been recently proposed to address the construction of completely decentralized systems for the above mentioned environments, but P2P systems frequently lack of dependability. In this paper, we propose an algorithm for increasing fault-tolerance by dynamically adding redundant links to P2P systems with unstructured topology. The algorithm requires only local interactions, is executed asynchronously by each peer and guarantees that the disappearance of any single peer does not affect the overall performance and routing capabilities of the system.