On the fault-tolerant embedding of complete binary trees in the pancake graph interconnection network

This paper studies the problem of embedding complete binary trees (CBTs) in to an n-dimensional pancake graph (P-n) with fault-tolerant capability. Fir st, a new embedding scheme is developed for mapping a source CBT with heigh t Sigma(m=2)(n) [log m] and dilation 2 onto the P-n. This scheme not only e mbeds a CBT whose height is very close to the largest possible one, but als o saves a lot of unused generators and generator products. Furthermore, the se unused generators and generator products are used to recover faulty node s and embed multiple CBTs. Maximally, near 2/3 nodes of the source CBT are allowed to be faulty at the same time and can be recovered by our scheme wi th dilation 4. Alternatively, a scheme which can embed a CBT with height Si gma(m=2)(n) [log m] - 1 is also given. In this case, if all nodes in the CB T are faulty, they can be recovered in the smallest number of recovery step s and only with dilation 4. (C) 2000 Published by Elsevier Science Inc. All rights reserved.