Embedding of Fault-Tolerant Trees in the Josephus Cube

Loh, P.K.K., Hsu, W.J. and Omondi, A.

The tree interconnection network lends itself to several suitably structured applications. However, the low connectivity at each node, traffic congestion and single point of failure at the root node reduce reliability and availability. Both the hypertree and X-tree are faulttolerant variants of the basic tree network and have been the focus of more recent implementation and research interest. In this paper, we introduce a recently proposed family of interconnection networks known as the Josephus Cubes and show how hypertrees, X-trees and ringed X-trees of arbitrary height can be near-optimally embedded in this novel interconnection network. Embedding techniques used for both hypertree and Xtrees are simple and may be recursively applied.

Cite as: Loh, P.K.K., Hsu, W.J. and Omondi, A. (2002). Embedding of Fault-Tolerant Trees in the Josephus Cube. In Proc. Seventh Asia-Pacific Computer Systems Architectures Conference (ACSAC2002), Melbourne, Australia. CRPIT, 6. Lai, F. and Morris, J., Eds. ACS. 17-27.

(from crpit.com) (local if available)