ICDCN2020_paper_62.pdf (870.21 kB)
Fully compact routing in low memory self-healing trees
conference contribution
posted on 2019-11-07, 11:48 authored by Armando Castañeda, Jonas Lefévre, Amitabh TrehanThe paper (Compact Routing Messages in Self-Healing Trees, TCS 2017) introduced CompactFTZ, the first self-healing compact routing algorithm that works in a distributed network with each node using only O(logn) words (i.e. O(log2 n) bits) memory and thus O(logn) sized messages. The routing uses only O(1) and O(logn) words routing table and packet labels respectively on a self-healing tree that also works using onlyO(1) words repairing the network in face of a strong adversary deleting nodes. This deterministic algorithm sets up its data structures in a preprocessing phase and then updates the required data structures in only O(1) parallel time per healing round during execution of the algorithm. However, CompactFTZ has no constraints in its preprocessing phase which could be done in distributed large memory or even centrally. In this paper, we correct that by developing the algorithms for preprocessing of CompactFTZ in a fully distributed manner using only O(logn) words memory in optimal time. In fact, the preprocessing for the self-healing tree (ForgivingTree) component takes only O(1) memory. We develop a local function which each node invokes to instantly compute and then relay its repair instructions (known as its Will) in only O(1) time. We formalise the low memory CONGEST model setting used in previous low memory algorithms (e.g.[24]); nodes’ working memory is restricted to be much smaller (in our case, O(logn)) than the numbers of their neighbours to whom they communicate through their I/O ports. We expand the model to allow for non-contiguous ports (e.g. empty ports or neighbours unmarked or lost in dynamic settings) and adversarial order of inputs from neighbours. Besides the Wills, we set up the tree structures and traversals for the routing scheme using only O(logn) memory and O(D) parallel time, where D is the diameter. Thus, we devise the first self-healing compact routing algorithm that can be fully set up and executed in low memory.
Funding
PAPIIT project IA102417
Engineering and Physical Sciences Research Council (EPSRC) grant EP/P021247/1 (COSHER)
History
School
- Science
Department
- Computer Science
Published in
ICDCN 2020: Proceedings of the 21st International Conference on Distributed Computing and NetworkingPages
1 - 10Source
21st International Conference on Distributed Computing and Networking (ICDCN 2020)Publisher
ACMVersion
- AM (Accepted Manuscript)
Rights holder
© Association for Computing MachineryPublisher statement
© ACM 2020. This is the author's version of the work. It is posted here for your personal use. Not for redistribution. The definitive Version of Record was published in ICDCN 2020: Proceedings of the 21st International Conference on Distributed Computing and Networking, https://doi.org/10.1145/3369740.3369786.Acceptance date
2019-10-09Publication date
2020-01-31Copyright date
2020ISBN
9781450377515Publisher version
Language
- en
Location
Kolkata, IndiaEvent dates
4th January 2020 - 7th January 2020Depositor
Dr Amitabh Trehan. Deposit date: 6 November 2019Article number
21Usage metrics
Categories
No categories selectedKeywords
Licence
Exports
RefWorks
BibTeX
Ref. manager
Endnote
DataCite
NLM
DC