Computer Science – Distributed – Parallel – and Cluster Computing
Scientific paper
2008-02-22
PODC '08: Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing. 2008, pages 203--212
Computer Science
Distributed, Parallel, and Cluster Computing
Submitted to Principles of Distributed Computing (PODC) 2008
Scientific paper
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 deletes an 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(log log 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.
Hayes Tom
Rustagi Navin
Saia Jared
Trehan Amitabh
No associations
LandOfFree
The Forgiving Tree: A Self-Healing Distributed Data Structure does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The Forgiving Tree: A Self-Healing Distributed Data Structure, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Forgiving Tree: A Self-Healing Distributed Data Structure will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-303153