Compact Routing Messages in Self-Healing Trees

Armando Castaneda, Danny Dolev, Amitabh Trehan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

178 Downloads (Pure)

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(log2 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(log n) 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 treebased 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 ∆ messages, with only +3 degree increase and O(log∆) graph diameter increase, over any sequence of deletions (∆ is the initial maximum degree).
Additionally, CompactFTZ guarantees delivery of a packet sent from sender s as long as the receiver has not been deleted, with only an additional O(y log ∆) 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.
Original languageEnglish
Title of host publicationProceedings of the 17th International Conference on Distributed Computing and Networking
Pages1-10
Number of pages10
DOIs
Publication statusPublished - 2016
Event17th International Conference on Distributed Computing and Networking - Singapore, Singapore
Duration: 04 Jan 201607 Jan 2016

Conference

Conference17th International Conference on Distributed Computing and Networking
CountrySingapore
CitySingapore
Period04/01/201607/01/2016

Fingerprint

Data storage equipment

Keywords

  • cs.DC
  • cs.DS
  • cs.NI
  • E.1; H.3.4; C.2.1; C.2.4; G.2.2

Cite this

Castaneda, A., Dolev, D., & Trehan, A. (2016). Compact Routing Messages in Self-Healing Trees. In Proceedings of the 17th International Conference on Distributed Computing and Networking (pp. 1-10). [23] https://doi.org/10.1145/2833312.2833328
Castaneda, Armando ; Dolev, Danny ; Trehan, Amitabh. / Compact Routing Messages in Self-Healing Trees. Proceedings of the 17th International Conference on Distributed Computing and Networking. 2016. pp. 1-10
@inproceedings{bf44b442102044b6a30871abc267dcd6,
title = "Compact Routing Messages in Self-Healing Trees",
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(log2 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(log n) 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 treebased 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 ∆ messages, with only +3 degree increase and O(log∆) graph diameter increase, over any sequence of deletions (∆ is the initial maximum degree).Additionally, CompactFTZ guarantees delivery of a packet sent from sender s as long as the receiver has not been deleted, with only an additional O(y log ∆) 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.",
keywords = "cs.DC, cs.DS, cs.NI, E.1; H.3.4; C.2.1; C.2.4; G.2.2",
author = "Armando Castaneda and Danny Dolev and Amitabh Trehan",
year = "2016",
doi = "10.1145/2833312.2833328",
language = "English",
isbn = "978-1-4503-4032-8",
pages = "1--10",
booktitle = "Proceedings of the 17th International Conference on Distributed Computing and Networking",

}

Castaneda, A, Dolev, D & Trehan, A 2016, Compact Routing Messages in Self-Healing Trees. in Proceedings of the 17th International Conference on Distributed Computing and Networking., 23, pp. 1-10, 17th International Conference on Distributed Computing and Networking, Singapore, Singapore, 04/01/2016. https://doi.org/10.1145/2833312.2833328

Compact Routing Messages in Self-Healing Trees. / Castaneda, Armando; Dolev, Danny; Trehan, Amitabh.

Proceedings of the 17th International Conference on Distributed Computing and Networking. 2016. p. 1-10 23.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - Compact Routing Messages in Self-Healing Trees

AU - Castaneda, Armando

AU - Dolev, Danny

AU - Trehan, Amitabh

PY - 2016

Y1 - 2016

N2 - 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(log2 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(log n) 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 treebased 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 ∆ messages, with only +3 degree increase and O(log∆) graph diameter increase, over any sequence of deletions (∆ is the initial maximum degree).Additionally, CompactFTZ guarantees delivery of a packet sent from sender s as long as the receiver has not been deleted, with only an additional O(y log ∆) 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.

AB - 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(log2 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(log n) 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 treebased 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 ∆ messages, with only +3 degree increase and O(log∆) graph diameter increase, over any sequence of deletions (∆ is the initial maximum degree).Additionally, CompactFTZ guarantees delivery of a packet sent from sender s as long as the receiver has not been deleted, with only an additional O(y log ∆) 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.

KW - cs.DC

KW - cs.DS

KW - cs.NI

KW - E.1; H.3.4; C.2.1; C.2.4; G.2.2

U2 - 10.1145/2833312.2833328

DO - 10.1145/2833312.2833328

M3 - Conference contribution

SN - 978-1-4503-4032-8

SP - 1

EP - 10

BT - Proceedings of the 17th International Conference on Distributed Computing and Networking

ER -

Castaneda A, Dolev D, Trehan A. Compact Routing Messages in Self-Healing Trees. In Proceedings of the 17th International Conference on Distributed Computing and Networking. 2016. p. 1-10. 23 https://doi.org/10.1145/2833312.2833328