Completely Independent Spanning Trees in Eisenstein-Jacobi Networks

Abstract In this work, we propose construction algorithms to build Completely Independent Spanning Trees (CIST) in EJ networks with time complexity of $O(n)$, where $n$ is the total number of nodes in the network. We present a sequential and a parallel CISTs construction algorithms. Their communication complexities are $O(d)$ and $O(1)$, respectively, $d$ is the tree depth. Based on the constructed CISTs, we developed a novel fault-tolerant communication algorithm that can be used for routing, broadcasting, and secure message distribution with $O(n)$ time complexity. Simulation results of our work illustrate the average of maximum number of steps required to deliver a message from the root node of any CIST to any destination in all trees. CISTs shows that it is more reliable than ISTs in terms of root node failure and node loads.