Loughborough University
Browse
ICDCN2020_paper_62.pdf (870.21 kB)

Fully compact routing in low memory self-healing trees

Download (870.21 kB)
conference contribution
posted on 2019-11-07, 11:48 authored by Armando Castañeda, Jonas Lefévre, Amitabh Trehan
The 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 Networking

Pages

1 - 10

Source

21st International Conference on Distributed Computing and Networking (ICDCN 2020)

Publisher

ACM

Version

  • AM (Accepted Manuscript)

Rights holder

© Association for Computing Machinery

Publisher 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-09

Publication date

2020-01-31

Copyright date

2020

ISBN

9781450377515

Language

  • en

Location

Kolkata, India

Event dates

4th January 2020 - 7th January 2020

Depositor

Dr Amitabh Trehan. Deposit date: 6 November 2019

Article number

21

Usage metrics

    Loughborough Publications

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC