The forgiving graph: a distributed data structure for low stretch under adversarial attack

DOI10.1007/S00446-012-0160-1MaRDI QIDQ1938375zbMATH OpenOpenAlexFDO

Authors Thomas P. Hayes, Jared Saia, Amitabh Trehan

Publication date 4 February 2013

Published in Distributed Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0902.2501

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Distributed systems (68M14) Data structures (68P05) Graph theory (including graph drawing) in computer science (68R10)

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, 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 $ell$ in the graph formed by considering only the adversarial insertions (not the adversarial deletions), will be at distance at most $elllogn$ in the actual graph, where $n$ is the total number of vertices seen so far. Similarly, at any point, a node $v$ whose degree would have been $d$ in the graph with adversarial insertions only, will have degree at most 3d in the actual graph. Our algorithm is completely distributed and has low latency and bandwidth requirements.

Recommendations

• The forgiving graph, a distributed data structure for low stretch under adversarial attack
• The forgiving tree, a self-healing distributed data structure
• Xheal, localized self-healing using expanders
• Xheal: a localized self-healing algorithm using expanders
• DEX: self-healing expanders

Cites work

• Building Optimal Binary Search Trees from Sorted Values in O(N) Time
• Introduction to algorithms
• Know thy neighbor's neighbor: the power of lookahead in randomized P2P networks
• Set reconciliation with nearly optimal communication complexity
• The forgiving graph, a distributed data structure for low stretch under adversarial attack
• The forgiving tree, a self-healing distributed data structure

Cited in

(8)

• Compact routing messages in self-healing trees
• Towards a universal approach for the finite departure problem in overlay networks
• Xheal: a localized self-healing algorithm using expanders
• DEX: self-healing expanders
• The forgiving tree, a self-healing distributed data structure
• Xheal, localized self-healing using expanders
• The forgiving graph, a distributed data structure for low stretch under adversarial attack
• Towards a universal approach for the finite departure problem in overlay networks

This page was built for publication: The forgiving graph: a distributed data structure for low stretch under adversarial attack

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1938375)