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) into an n-dimensional pancake graph (P-n) with fault-tolerant capability. First, a new embedding scheme is developed for mapping a source CBT with height Sigma(m=2)(n) [log m] and dilation 2 onto the P-n. This scheme not only embeds a CBT whose height is very close to the largest possible one, but also saves a lot of unused generators and generator products. Furthermore, these unused generators and generator products are used to recover faulty nodes 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 with dilation 4. Alternatively, a scheme which can embed a CBT with height Sigma(m=2)(n) [log m] - 1 is also given. In this case, if all nodes in the CBT are faulty, they can be recovered in the smallest number of recovery steps and only with dilation 4. (C) 2000 Published by Elsevier Science Inc. All rights reserved. [References: 18]