Hypercomplete: A pancyclic recursive topology for large-scale distributed multicomputer systems
This paper introduces a pancyclic recursive topology, named the hypercomplete, for building large-scale distributed multicomputer systems. The hypercomplete is maximally fault-tolerant and has a logarithmic diameter. In addition to being pancyclic, the hypercomplete is Hamiltonian-connected. Consequently, the hypercomplete can embed rings of all possible lengths and a longest linear array between arbitrary two nodes. Besides, the hypercomplete can embed tori and trees with constant dilation and constant congestion. Some algorithms are developed for the hypercomplete. An algorithm is proposed to determine a shortest path between arbitrary two nodes. A broadcasting algorithm without redundant messages is proposed, whose resulting spanning tree has its height bounded above by the diameter. The class of ascend/descend algorithms can be executed efficiently. (C) 2000 John Wiley & Sons, Inc.
pancyclic diameter shortest path broadcasting ascend/descend algorithms embedding hamiltonian-connected interconnection topology