Fault-tolerance and reconfiguration of circulant graphs and hypercubes

ABSTRACT

Several interconnection networks (such as rings, meshes and hypercubes) can be modeled as circulant graphs. As a result, methods previously developed for constructing fault-tolerant solutions of circulant graphs can also be applied to these networks. Among these methods, the one based on the idea of "offsets partitioning" is the most efficient (for circulant graphs). We review this method in this paper, and extend its applications to hypercubes. Moreover, we develop new algorithms to reconfigure circulant graphs and hypercubes. Our results show that the fault-tolerant solutions obtained, and the reconfiguration algorithms developed are efficient.

REFERENCES

• 1: P. A. Lee , T. Anderson , J. C. Laprie , A. Avizienis , H. Kopetz, Fault Tolerance: Principles and Practice, Springer-Verlag New York, Inc., Secaucus, NJ, 1990
• 2: J. Bruck , R. Cypher , C. Ho, Fault-Tolerant Meshes and Hypercubes with Minimal Numbers of Spares, IEEE Transactions on Computers, v.42 n.9, p.1089-1104, September 1993 [doi>10.1109/12.241598]
• 3: Jehoshua Bruck , Robert Cypher , Ching-Tien Ho, Fault-Tolerant Meshes with Small Degree, SIAM Journal on Computing, v.26 n.6, p.1764-1784, Dec. 1997 [doi>10.1137/S0097539794274994]
• 4: Yen-Chu Chuang , Lih-Hsing Hsu , Chung-Haw Chang, Optimal 1-edge fault-tolerant designs for ladders, Information Processing Letters, v.84 n.2, p.87-92, 31 October 2002 [doi>10.1016/S0020-0190(02)00225-9]
• 5: Chung, F., F. Leighton, and A. Rosenberg, 1983, "Diogenes: a Methodology for Designing Fault-Tolerant VLSI Processor Arrays", in Proc. IEEE 13th Conf on Fault Tolerant Computing Symp, (June), Chicago, IL, 26--32.
• 6: Shantanu Dutt , John P. Hayes, Designing fault-tolerant systems using automorphisms, Journal of Parallel and Distributed Computing, v.12 n.3, p.249-268, July 1991 [doi>10.1016/0743-7315(91)90129-W]
• 7: Abdel Aziz Farrag, Tolerating faulty edges in a multi-dimensional mesh, Parallel Computing, v.20 n.9, p.1289-1301, Sept. 1994 [doi>10.1016/0167-8191(94)90038-8]
• 8: A. A. Farrag, Algorithm for constructing fault-tolerant solutions of the circulant graph configuration, Proceedings of the Fifth Symposium on the Frontiers of Massively Parallel Computation (Frontiers'95), p.514, February 06-09, 1995
• 9: A. Aziz Farrag , R. J. Dawson, The Fault-Tolerant Extension Problem for Complete Multipartite Networks, IEEE Transactions on Parallel and Distributed Systems, v.5 n.2, p.205-210, February 1994 [doi>10.1109/71.265947]
• 10: Abdel Aziz Farrag , Shituo Lou, Designing and Reconfiguring Fault-Tolerant Hypercubes, Proceedings of the 20th International Symposium on High-Performance Computing in an Advanced Collaborative Environment, p.11, May 14-17, 2006 [doi>10.1109/HPCS.2006.19]
• 11: Farrag, A., and S. Lou, 2005, "Applying Fault-Tolerant Solutions of Circulant Graphs to Multi-Dimensional Meshes" in Computers & Mathematics Journal, 50, no. 8--9, (November): 1383--1394.
• 12: Harary, F., and J. Hayes, 1993, "Edge Fault Tolerance of Graphs", in Networks, 23, no. 2 (March): 135--142.
• 13: Li, Y., S. Peng and W. Chu, 2003, "Fault-Tolerant Cycle Embedding in Dual-Cube with Node Faulty", in Proc. Int Conf on Parallel and Dist. Computing, (August 27--29), Chengdu, China, 71--75.
• 14: Lipson, J., 1981, Elements of Algebra and Algebraic Computing, Benjamin/Cummings Publisher, Melno Park, California.
• 15: Rennels, D., 1986, "On Implementing Fault-Tolerance in Binary Hypercubes", Digest of papers of IEEE Symp on Fault-Tolerant Comp, (July), Vienna, Austria, 344--349.
• 16: Youcef Saad , Martin H. Schultz, Topological Properties of Hypercubes, IEEE Transactions on Computers, v.37 n.7, p.867-872, July 1988 [doi>10.1109/12.2234]
• 17: Ernst Schmitter , Peter Baues, The Basic Fault-tolerant System, IEEE Micro, v.4 n.1, p.66-74, January 1984 [doi>10.1109/MM.1984.291309]
• 18: L. Snyder, Introduction to the Configurable, Highly Parallel Computer, Computer, v.15 n.1, p.47-56, January 1982 [doi>10.1109/MC.1982.1653826]
• 19: Ting-Yi Sung , Tung-Yang Ho , Men-Yang Lin, Multiple-Edge-Fault Tolerance with Respect to Hypercubes, IEEE Transactions on Parallel and Distributed Systems, v.8 n.2, p.187-192, February 1997 [doi>10.1109/71.577263]
• 20: Chu-Sing Yang , Shun-Yue Wu, Modular Fault-Tolerant Boolean N-Cubes, IEEE Micro, v.14 n.4, p.68-73, 75-77, August 1994 [doi>10.1109/40.296168]
• 21: Li Zhang, Fault-Tolerant Meshes with Small Degree, IEEE Transactions on Computers, v.51 n.5, p.553-560, May 2002 [doi>10.1109/TC.2002.1004594]

INDEX TERMS

Keywords:
circulant graphs, fault-tolerance, hypercubes, networks, reconfiguration