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

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 ℓ 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 degree would 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 [8] 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 does not require an initialization phase, while the Forgiving Tree initially requires construction of a spanning tree of the network.

REFERENCES

• 1: David Andersen , Hari Balakrishnan , Frans Kaashoek , Robert Morris, Resilient overlay networks, ACM SIGOPS Operating Systems Review, v.35 n.5, Dec. 2001
• 2: Baruch Awerbuch , Boaz Patt-Shamir , David Peleg , Michael Saks, Adapting to asynchronous dynamic networks (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.557-570, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129767]
• 3: Iching Boman, Jared Saia, Chaouki T. Abdallah, and Edl Schamiloglu. Brief announcement: Self-healing algorithms for reconfigurable networks. In Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), 2006.
• 4: Robert D. Doverspike and Brian Wilson. Comparison of capacity efficiency of dcs network restoration routing techniques. J. Network Syst. Manage., 2(2), 1994.
• 5: T. Frisanco. Optimal spare capacity design for various protection switching methods in ATM networks. In Communications, 1997. ICC 97 Montreal, 'Towards the Knowledge Millennium'. 1997 IEEE International Conference on, volume 1, pages 293--298, 1997.
• 6: Sanjay Goel , Salvatore Belardo , Laura Iwan, A Resilient Network that Can Operate Under Duress: To Support Communication between Government Agencies during Crisis Situations, Proceedings of the Proceedings of the 37th Annual Hawaii International Conference on System Sciences (HICSS'04) - Track 5, p.50123.1, January 05-08, 2004
• 7: Yukio Hayashi and Toshiyuki Miyazaki. Emergent rewirings for cascades on correlated networks. cond-mat/0503615, 2005.
• 8: Tom Hayes , Navin Rustagi , Jared Saia , Amitabh Trehan, The forgiving tree: a self-healing distributed data structure, Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, August 18-21, 2008, Toronto, Canada [doi>10.1145/1400751.1400779]
• 9: Petter Holme and Beom Jun Kim. Vertex overload breakdown in evolving networks. Physical Review E, 65:066109, 2002.
• 10: Rainer R. Iraschko , M. H. MacGregor , Wayne D. Grover, Optimal capacity placement for path restoration in STM or ATM mesh-survivable networks, IEEE/ACM Transactions on Networking (TON), v.6 n.3, p.325-336, June 1998 [doi>10.1109/90.700896]
• 11: Gurmeet Singh Manku , Moni Naor , Udi Wieder, Know thy neighbor's neighbor: the power of lookahead in randomized P2P networks, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007368]
• 12: Muriel Médard , Steven G. Finn , Richard A. Barry, Redundant trees for preplanned recovery in arbitrary vertex-redundant or edge-redundant graphs, IEEE/ACM Transactions on Networking (TON), v.7 n.5, p.641-652, Oct. 1999 [doi>10.1109/90.803380]
• 13: Adilson E Motter. Cascade control and defense in complex networks. Physical Review Letters, 93:098701, 2004.
• 14: Adilson E Motter and Ying-Cheng Lai. Cascade-based attacks on complex networks. Physical Review E, 66:065102, 2002.
• 15: Kazutaka Murakami , Hyong S. Kim, Comparative Study on Restoration Schemes of Survivable ATM Networks, Proceedings of the INFOCOM '97. Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Driving the Information Revolution, p.345, April 09-11, 1997
• 16: Moni Naor and Udi Wieder. Know thy neighbor's neighbor: Better routing for skip-graphs and small worlds. In in Proc. of IPTPS, 2004, pages 269--277, 2004.
• 17: Jared Saia and Amitabh Trehan. Picking up the pieces: Self-healing in reconfigurable networks. In IEEE International Parallel & Distributed Processing Symposium, 2008.
• 18: B. van Caenegem, N. Wauters, and P. Demeester. Spare capacity assignment for different restoration strategies in mesh survivable networks. In Communications, 1997. ICC 97 Montreal, 'Towards the Knowledge Millennium'. 1997 IEEE International Conference on, volume 1, pages 288--292, 1997.
• 19: Jean G. Vaucher. Building optimal binary search trees from sorted values in o(n) time. In Essays in Memory of Ole-Johan Dahl, pages 376--388, 2004.
• 20: Yijun Xiong , Lorne G. Mason, Restoration strategies and spare capacity requirements in self-healing ATM networks, IEEE/ACM Transactions on Networking (TON), v.7 n.1, p.98-110, Feb. 1999 [doi>10.1109/90.759330]

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Trees

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Reliability, availability, and serviceability

  E. Data
  E.1 DATA STRUCTURES
      Subjects: Graphs and networks; Distributed data structures

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software
          Subjects: Information networks; Distributed systems

General Terms:
Algorithms, Design, Reliability, Security, Theory

Keywords:
data structure, degree, distributed, half-full tree, network, peer-to-peer, reconfigurable, responsive, self-healing, stretch