The Forgiving Graph: A distributed data structure for low stretch under adversarial attack

T.P. Hayes, J. Saia, A. Trehan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

22 Citations (Scopus)


We consider the problem of self-healing in peer-to-peer networks that are under repeated attack by an omniscient adversary. We assume that, over a sequence of rounds, an adversary either inserts a node with arbitrary connections or deletes an arbitrary node from the network. The network responds to each such change by quick "repairs," which consist of adding or deleting a small number of edges. These repairs essentially preserve closeness of nodes after adversarial deletions,without increasing node degrees by too much, in the following sense. At any point in the algorithm, nodes v and w whose distance would have been - in the graph formed by considering only the adversarial insertions (not the adversarial deletions), will be at distance at most - log n in the actual graph, where n is the total number of vertices seen so far. Similarly, at any point, a node v whose degreewould have been d in the graph with adversarial insertions only, will have degree at most 3d in the actual graph. Our distributed data structure, which we call the Forgiving Graph, has low latency and bandwidth requirements. The Forgiving Graph improves on the Forgiving Tree distributed data structure from Hayes et al. (2008) in the following ways: 1) it ensures low stretch over all pairs of nodes, while the Forgiving Tree only ensures low diameter increase; 2) it handles both node insertions and deletions, while the Forgiving Tree only handles deletions; 3) it requires only a very simple and minimal initialization phase, while the Forgiving Tree initially requires construction of a spanning tree of the network.
Original languageEnglish
Title of host publicationProc. of 28th Symp. on Principles of Distributed Computing (PODC)
PublisherAssociation for Computing Machinery
Number of pages10
Publication statusPublished - 01 Sept 2009
EventACM Principles of Distributed Computing 2009 - Calgary, Canada
Duration: 09 Aug 200911 Aug 2009


ConferenceACM Principles of Distributed Computing 2009


Dive into the research topics of 'The Forgiving Graph: A distributed data structure for low stretch under adversarial attack'. Together they form a unique fingerprint.

Cite this