The forgiving tree

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The forgiving tree: a self-healing distributed data structure

Full text

Pdf (339 KB)

Source

Annual ACM Symposium on Principles of Distributed Computing archive
Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing table of contents

Toronto, Canada

SESSION: R5 table of contents

Pages 203-212

Year of Publication: 2008

ISBN:978-1-59593-989-0

Authors

Tom Hayes	Toyota Technological Institute, Chicago, IL, USA
Navin Rustagi	University of New Mexico, Albuquerque, NM, USA
Jared Saia	University of New Mexico, Albuquerque, NM, USA
Amitabh Trehan	University of New Mexico, Albuquerque, NM, USA

Sponsors

SIGOPS: ACM Special Interest Group on Operating Systems
ACM: Association for Computing Machinery
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 9, Downloads (12 Months): 131, Citation Count: 1

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1400751.1400779 What is a DOI?

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.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked 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	Villu Arak. What happened on August 16, August 2007. http://heartbeat.skype.com/2007/08/whathappened-on-august-16.html.
	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	Edith Cohen. Size--estimation framework with applications to transitive closure and reachability. In Proceedings of the Foundations of Computer Science (FOCS), 1994.
	5	Robert D. Doverspike and Brian Wilson. Comparison of capacity efficiency of dcs network restoration routing techniques. J. Network Syst. Manage., 2(2), 1994.
	6	Ken Fisher. Skype talks of "perfect storm" that caused outage, clarifies blame, August 2007. http://arstechnica.com/news.ars/post/20070821skype--talks--of--perfect--storm.html.
	7	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.
	8	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
	9	Yukio Hayashi and Toshiyuki Miyazaki. Emergent rewirings for cascades on correlated networks. cond-mat/0503615, 2005.
	10	Petter Holme and Beom Jun Kim. Vertex overload breakdown in evolving networks. Physical Review E, 65:066109, 2002.
	11	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]
	12	Fabian Kuhn, Stefan Schmid, Joest Smit, and Roger Wattenhofer. A Blueprint for Constructing Peer--to--Peer Systems Robust to Dynamic Worst--Case Joins and Leaves. In 14th IEEE International Workshop on Quality of Service (IWQoS), Yale University, New Haven, Connectitut, USA, June 2006.
	13	Fabian Kuhn, Stefan Schmid, and Roger Wattenhofer. A Self-Repairing Peer-to-Peer System Resilient to Dynamic Adversarial Churn. In 4th International Workshop on Peer-To-Peer Systems (IPTPS), Cornell University, Ithaca, New York, USA, Springer LNCS 3640, February 2005.
	14	Om Malik. Does Skype Outage Expose P2POs Limitations?, August 2007. http://gigaom.com/2007/08/16/skype-outage.
	15	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]
	16	Matt Moore. Skype's outage not a hang--up for user base, August 2007. http://www.usatoday.com/tech/wireless/phones/200708-24-skype-outage-effects-N.htm.
	17	Adilson E Motter. Cascade control and defense in complex networks. Physical Review Letters, 93:098701, 2004.
	18	Adilson E Motter and Ying--Cheng Lai. Cascade--based attacks on complex networks. Physical Review E, 66:065102, 2002.
	19	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
	20	Bill Ray. Skype hangs up on users, August 2007. http://www.theregister.co.uk/2007/08/16/skype down/.
	21	Jared Saia and Amitabh Trehan. Picking up the pieces: Self--healing in reconfigurable networks. In IEEE International Parallel & Distributed Processing Symposium, 2008.
	22	Brad Stone. Skype: Microsoft Update Took Us Down, August 2007. http://bits.blogs.nytimes.com/2007/08/20/skypemicrosoft--update--took--us--down.
	23	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.
	24	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]