Compact routing messages in self-healing trees

DOI10.1016/J.TCS.2016.11.022MaRDI QIDQ1686108zbMATH OpenOpenAlexWikidataFDO

Authors Armando Castañeda, Danny Dolev, Amitabh Trehan

Publication date 20 December 2017

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1508.04234, https://pureadmin.qub.ac.uk/ws/files/39009986/1508.04234v1

zbMATH Keywords

internet of thingscompact forgiving treecompact Thorup-Zwick routingdistributed message passing algorithmlow memory compact algorithmself-healing fault-tolerant P2P algorithm

Mathematics Subject Classification ID

Reliability, testing and fault tolerance of networks and computer systems (68M15) Distributed systems (68M14)

Abstract: Existing compact routing schemes, e.g., Thorup and Zwick [SPAA 2001] and Chechik [PODC 2013], often have no means to tolerate failures, once the system has been setup and started. This paper presents, to our knowledge, the first self-healing compact routing scheme. Besides, our schemes are developed for low memory nodes, i.e., nodes need only $O(lo{g}^{2}n)$ memory, and are thus, compact schemes. We introduce two algorithms of independent interest: The first is CompactFT, a novel compact version (using only $O(logn)$ local memory) of the self-healing algorithm Forgiving Tree of Hayes et al. [PODC 2008]. The second algorithm (CompactFTZ) combines CompactFT with Thorup-Zwick's tree-based compact routing scheme [SPAA 2001] to produce a fully compact self-healing routing scheme. In the self-healing model, the adversary deletes nodes one at a time with the affected nodes self-healing locally by adding few edges. CompactFT recovers from each attack in only $O(1)$ time and $Delta$ messages, with only +3 degree increase and $O(logDelta)$ graph diameter increase, over any sequence of deletions ($Delta$ is the initial maximum degree). Additionally, CompactFTZ guarantees delivery of a packet sent from sender s as long as the receiver t has not been deleted, with only an additional $O(ylogDelta)$ latency, where $y$ is the number of nodes that have been deleted on the path between $s$ and $t$. If $t$ has been deleted, $s$ gets informed and the packet removed from the network.

Recommendations

• Improved compact routing schemes for dynamic trees
• Optimal Routing Designs in Self‐healing Communications Networks
• Publication:4733694
• Space-Efficient Message Routing inc-Decomposable Networks
• Efficient Message Routing in Planar Networks
• scientific article; zbMATH DE number 2006653
• An optimal algorithm for broadcasting multiple messages in trees
• A polynomial-time algorithm for message routing in hierarchical communication networks

Cites work

• scientific article; zbMATH DE number 996442 (Why is no real title available?)
• scientific article; zbMATH DE number 2038725 (Why is no real title available?)
• scientific article; zbMATH DE number 1756017 (Why is no real title available?)
• scientific article; zbMATH DE number 2086374 (Why is no real title available?)
• A fault-tolerant routing scheme in dynamic networks
• A near-optimal distributed fully dynamic algorithm for maintaining sparse spanners
• A self-stabilizing transformer for population protocols with covering
• A trade-off between information and communication in broadcast protocols
• Compact Forbidden-Set Routing
• Compact routing schemes with improved stretch
• Compact routing with minimum stretch
• Distributed computation in dynamic networks
• Fault-tolerant compact routing schemes for general graphs
• General compact labeling schemes for dynamic trees
• Improved routing strategies with succinct tables
• Labeling schemes for dynamic tree networks
• Labeling schemes for weighted dynamic trees
• Labelling and Implicit Routing in Networks
• Routing with guaranteed delivery in ad hoc wireless networks
• Self-stabilization
• Self-stabilizing depth-first search
• Self-stabilizing systems in spite of distributed control
• Stabilization, safety, and security of distributed systems. 16th international symposium, SSS 2014, Paderborn, Germany, September 28 -- October 1, 2014. Proceedings
• The forgiving graph: a distributed data structure for low stretch under adversarial attack
• The forgiving tree, a self-healing distributed data structure
• Xheal: a localized self-healing algorithm using expanders
• \(f\)-sensitivity distance oracles and routing schemes

Describes a project that uses

Uses Software

• Xheal

This page was built for publication: Compact routing messages in self-healing trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1686108)