The forgiving tree: a self-healing distributed data structure

Tom Hayes, Navin Rustagi, Jared Saia, Amitabh Trehan

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

21 Citations (Scopus)

Abstract



We consider the problem of self-healing in peer-to-peer networks that are under repeated attack by an omniscient adversary. We assume that the following process continues for up to n rounds where n is the total number of nodes initially in the network: the adversary deletesan arbitrary node from the network, then the network responds by quickly adding a small number of new edges.

We present a distributed data structure that ensures two key properties. First, the diameter of the network is never more than O(log Delta) times its original diameter, where Delta is the maximum degree of the network initially. We note that for many peer-to-peer systems, Delta is polylogarithmic, so the diameter increase would be a O(loglog n) multiplicative factor. Second, the degree of any node never increases by more than 3 over its original degree. Our data structure is fully distributed, has O(1) latency per round and requires each node to send and receive O(1) messages per round. The data structure requires an initial setup phase that has latency equal to the diameter of the original network, and requires, with high probability, each node v to send O(log n) messages along every edge incident to v. Our approach is orthogonal and complementary to traditional topology-based approaches to defending against attack.
Original languageEnglish
Title of host publicationProceedings of the twenty-seventh ACM symposium on Principles of distributed computing.
Place of PublicationNew York, NY, USA
PublisherAssociation for Computing Machinery
Pages203-212
Number of pages10
ISBN (Print)978-1-59593-989-0
DOIs
Publication statusPublished - 2008
EventPODC 2008: twenty-seventh ACM symposium on Principles of distributed computing - Toronto, Canada
Duration: 18 Aug 200821 Aug 2008

Publication series

NamePODC '08
PublisherACM

Conference

ConferencePODC 2008: twenty-seventh ACM symposium on Principles of distributed computing
Country/TerritoryCanada
CityToronto
Period18/08/200821/08/2008

Keywords

  • data structure
  • distributed
  • networks
  • peer-to-peer
  • reconfigurable
  • responsive
  • self-healing

ASJC Scopus subject areas

  • General Computer Science

Fingerprint

Dive into the research topics of 'The forgiving tree: a self-healing distributed data structure'. Together they form a unique fingerprint.

Cite this