Fully Compact Routing in Low Memory Self-Healing Trees
Armando Castañeda, Jonas Lefèvre, Amitabh Trehan · 2020
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(log n) words (i.e. O(log2 n) bits) memory and thus O(log n) sized messages. The routing uses only O(1) and O(log n) words routing table and packet labels respectively on a self-healing tree that also works using only O(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.