Distributed Algorithms for Building Hamiltonian Cycles in k-ary n-cubes and Hypercubes with Faulty Links

摘要

In parallel computers which have a large number of processors, it is not uncommon for nodes or links between nodes to fail. This experience has motivated investigations into how able different interconnection networks are to cope with a limited number of node and/or link faults. Most investigations have focussed on the resulting communication capabilities or embeddability of faulty interconnection networks, e.g., whether a certain network is still connected or whether certain guest networks can still be embedded in certain host networks, given a limited number of faults. Also, most research has centered around hypercubes and the k-ary n-cube has not been considered to such a great extent.