NDLI: DEX: self-healing expanders

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

DEX: self-healing expanders

Content Provider	Springer Nature Link
Author	Pandurangan, Gopal Robinson, Peter Trehan, Amitabh
Copyright Year	2015
Abstract	We present a fully-distributed self-healing algorithm dex that maintains a constant degree expander network in a dynamic setting. To the best of our knowledge, our algorithm provides the first efficient distributed construction of expanders—whose expansion properties hold deterministically—that works even under an all-powerful adaptive adversary that controls the dynamic changes to the network (the adversary has unlimited computational power and knowledge of the entire network state, can decide which nodes join and leave and at what time, and knows the past random choices made by the algorithm). Previous distributed expander constructions typically provide only probabilistic guarantees on the network expansion which rapidly degrade in a dynamic setting; in particular, the expansion properties can degrade even more rapidly under adversarial insertions and deletions. Our algorithm provides efficient maintenance and incurs a low overhead per insertion/deletion by an adaptive adversary: only $$O(\log n)$$ rounds and $$O(\log n)$$ messages are needed with high probability (n is the number of nodes currently in the network). The algorithm requires only a constant number of topology changes. Moreover, our algorithm allows for an efficient implementation and maintenance of a distributed hash table on top of dex with only a constant additional overhead. Our results are a step towards implementing efficient self-healing networks that have guaranteed properties (constant bounded degree and expansion) despite dynamic changes.
Starting Page	163
Ending Page	185
Page Count	23
File Format	PDF
ISSN	01782770
Journal	Distributed Computing
Volume Number	29
Issue Number	3
e-ISSN	14320452
Language	English
Publisher	Springer Berlin Heidelberg
Publisher Date	2015-11-27
Publisher Place	Berlin/Heidelberg
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Computer Communication Networks Computer Hardware Computer Systems Organization and Communication Networks Software Engineering/Programming and Operating Systems Theory of Computation
Content Type	Text
Resource Type	Article
Subject	Theoretical Computer Science Computer Networks and Communications Computational Theory and Mathematics Hardware and Architecture

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

Xheal: a localized self-healing algorithm using expanders

Randomized leader election

The mailbox problem

Self-stabilizing smoothing and balancing networks

Coloring unstructured radio networks

Oblivious signature-based envelope

The computational power of population protocols

Fast and scalable rendezvousing

Stable and scalable universal swarms

DEX: self-healing expanders

Similar Documents

Xheal: a localized self-healing algorithm using expanders

Randomized leader election

The mailbox problem

Self-stabilizing smoothing and balancing networks

Coloring unstructured radio networks

Oblivious signature-based envelope

The computational power of population protocols

Fast and scalable rendezvousing

Stable and scalable universal swarms

DEX: self-healing expanders