Title: Fault-tolerant cycle embedding in dual-cube with node faults

Authors: Yamin Li, Shietung Peng, Wanming Chu

Addresses: Department of Computer Science, Hosei University, Tokyo 184 8584, Japan. ' Department of Computer Science, Hosei University, Tokyo 184 8584, Japan. ' Department of Computer Hardware, University of Aizu, Aizu-Wakamatsu 965 8580, Japan

Abstract: A low-degree dual-cube was proposed as an alternative to the hypercubes. A dual-cube DC(m) has m + 1 links per node, where m is the degree of a cluster (m-cube) and one more link is used for connecting to a node in another cluster. There are 2^m+1 clusters and hence the total number of nodes in a DC(m) is 2^2m+1. In this paper, by using Gray code, we show that there exists a fault-free cycle containing at least 2^2m+1–2f nodes in DC(m), m≥3, with f≤m faulty nodes.

Keywords: interconnection networks; hypercubes; Gray code; Hamiltonian cycle; fault-tolerant embedding; cycle embedding; dual-cube; node faults; high performance computing; networking.

DOI: 10.1504/IJHPCN.2005.007866

International Journal of High Performance Computing and Networking, 2005 Vol.3 No.1, pp.45 - 53

Published online: 28 Sep 2005 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article