Compact Routing Messages in Self-Healing Trees
Data(s) |
2016
|
---|---|
Resumo |
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.<br/>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).<br/>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. |
Formato |
application/pdf |
Identificador | |
Idioma(s) |
eng |
Direitos |
info:eu-repo/semantics/openAccess |
Fonte |
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 , 4-7 January . DOI: 10.1145/2833312.2833328 |
Palavras-Chave | #cs.DC #cs.DS #cs.NI #E.1; H.3.4; C.2.1; C.2.4; G.2.2 |
Tipo |
contributionToPeriodical |