Hypercomplete: A pancyclic recursive topology for large-scale distributed multicomputer systems

This paper introduces a pancyclic recursive topology, named the hypercomple te, for building large-scale distributed multicomputer systems. The hyperco mplete is maximally fault-tolerant and has a logarithmic diameter. In addit ion to being pancyclic, the hypercomplete is Hamiltonian-connected. Consequ ently, the hypercomplete can embed rings of all possible lengths and a long est linear array between arbitrary two nodes. Besides, the hypercomplete ca n embed tori and trees with constant dilation and constant congestion. Some algorithms are developed for the hypercomplete. An algorithm is proposed t o determine a shortest path between arbitrary two nodes. A broadcasting alg orithm without redundant messages is proposed, whose resulting spanning tre e has its height bounded above by the diameter. The class of ascend/descend algorithms can be executed efficiently. (C) 2000 John Wiley & Sons, Inc.