NDLI: The forgiving tree: a self-healing distributed data structure

Please wait, while we are loading the content...

Distributed computation of the mode

Anti-Ω: the weakest failure detector for set agreement

Collaborative enforcement of firewall policies in virtual private networks

On the complexity of asynchronous gossip

On a capacitated multivehicle routing problem

Flooding time in edge-Markovian dynamic graphs

Distributed algorithms for ultrasparse spanners and linear size skeletons

New combinatorial topology upper and lower bounds for renaming

Packet mode and QoS algorithms for buffered crossbar switches with FIFO queuing

Asynchronous exclusive selection

Forget him and keep on moving

BMobi_Causal: a causal broadcast protocol in mobile dynamic groups

A fast distributed slicing algorithm

A tradeoff analysis on message complexity and lifetime optimality for a distributed multicast algorithm in WSNs

Greedy distributed optimization of unsplittable multicommodity flows

Quantum distributed consensus

Optimizing consistency checking for memory-intensive transactions

The lotus-eater attack

Evolution of distributed computing theory: from concurrency to networks and beyond

Beyond nash equilibrium: solution concepts for the 21st century

Sublogarithmic distributed MIS algorithm for sparse graphs using nash-williams decomposition

Failure detectors in loosely named systems

Secure communication over radio channels

Brahms: byzantine resilient random membership sampling

Improved compact routing schemes for dynamic trees

On the effect of the deployment setting on broadcasting in Euclidean radio networks

Efficient distributed approximation algorithms via probabilistic tree embeddings

Timeliness-based wait-freedom: a gracefully degrading progress condition

The impact of randomization in smoothing networks

Fast self-stabilizing byzantine tolerant digital clock synchronization

Online and dynamic embeddings of approximate ultrametrics

Correctness criteria for replicated database systems with snapshot isolation replicas

A dynamic exchange game

Nearest-neighbor graphs on random point sets and their applications to sensor networks

Stateless distributed algorithms for near optimal maximum multicommodity flows

Looking for the optimal conditions for solving set agreement

Wait-free programming for general purpose computations on graphics processors

Extracting models from design documents with mapster

A world of (Im) possibilities

The internet is flat: a brief history of networking in the next ten years

A log-star distributed maximal independent set algorithm for growth-bounded graphs

Every problem has a weakest failure detector

On tradeoff between network connectivity, phase complexity and communication complexity of reliable communication tolerating mixed adversary

Efficient randomised broadcasting in random regular networks with applications in peer-to-peer systems

Tight bounds for delay-sensitive aggregation

Virtual infrastructure for collision-prone wireless networks

On the locality of distributed sparse spanner construction

Lower bounds for randomized consensus under a weak adversary

Optimizing data popularity conscious bloom filters

OCD: obsessive consensus disorder (or repetitive consensus)

Dynamic routing and location services in metrics of low doubling dimension

The asynchronous bounded-cycle model

Anonymous and censorship resistant content sharing in unstructured overlays

From anarchy to geometric structuring: the power of virtual coordinates

Distributed averaging in the presence of a sparse cut

Tight RMR lower bounds for mutual exclusion and other problems

Transactional memory retry mechanisms

Efficient single phase unconditionally secure message transmission with optimum communication complexity

The power of simulation relations

Accountability for distributed systems

A jamming-resistant MAC protocol for single-hop wireless networks

Sharing is harder than agreeing

CAR-STM: scheduling-based collision avoidance and resolution for software transactional memory

Bounded budget connection (BBC) games or how to make friends and influence people, on a budget

The forgiving tree: a self-healing distributed data structure

Sleeping on the job: energy-efficient and robust broadcast for radio networks

The stretched exponential distribution of internet media access patterns

Randomized consensus in expected O(n log n) individual work

Distributed order scheduling and its application to multi-core dram controllers

An almost-surely terminating polynomial protocol for asynchronous byzantine agreement with optimal resilience

On ad hoc routing with guaranteed delivery

Model checking transactional memory with spin

Our brothers' keepers

Balancing energy consumption for uniform data gathering wireless sensor networks

Gossip-based aggregate computation: computing faster with non address-oblivious schemes

Closing the complexity gap between mutual exclusion and FCFS mutual exclusion

Scheduling tasks with dependencies on asymmetric multiprocessors

Mobile proactive secret sharing

On fault tolerance and wireless networks

On the internet delay space dimensionality

On the robustness of (semi) fast quorum-based implementations of atomic shared memory

Distributed churn measurement in arbitrary networks

Scheduling sensors by tilinglattices

Snap-stabilization in message-passing systems

Fault-tolerant implementations of atomic registers by safe registers in networks

The future of distributed computing: renaissance or reformation?

Maximizing quorum availability in multi-clustered systems

Principles of untrusted storage: a new look at consistency conditions

Efficient pipeline configuration in distributed heterogeneous computing environments

Power management of devices: when should i switch off?

Dynamic service assignment in mobile networks: the magma approach

Optimal failure detection with low sporadic overhead and communication locality

The forgiving tree: a self-healing distributed data structure

Content Provider	ACM Digital Library
Author	Rustagi, Navin Saia, Jared Trehan, Amitabh Hayes, Tom
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.
Starting Page	203
Ending Page	212
Page Count	10
File Format	PDF
ISBN	9781595939890
DOI	10.1145/1400751.1400779
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2008-08-18
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Networks Responsive Distributed Peer-to-peer Self-healing Data structure Reconfigurable
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in