.po 1.6i .ll 5.5i .pl 11.5i .nr ps .5v .nr ss 0v .nr sp 13 .nr pp 12 .nr $r 18 .nr $R 11 .ps 12 .vs 13 .ls 1 .EQ gsize 12 delim $$ .EN .ds st "\v'.08'*\v'-.08' .ds sq "\f(ZDr\fP .fo ''- % -'' .sh 1 "Introduction" .pp The hypercube is a multiprocessor computer architecture that has received much attention recently. It is practical compared with the PRAM (Parallel Random Access Machine) model [KR] and is powerful enough to execute many algorithms efficiently. It can also simulate other parallel computer architectures [LS] such as rings [CL2], grids [C, CC1, CC2, HJ] and trees [BCLR, BI, CL1, HL, LNRS, MS, WCM, Wa, Wu] with little or no slowdown. As a result, algorithms designed for these architectures can also be executed on a hypercube efficiently. It is robust and remains operative in the presence of faults, though at a slower pace [A, BS, BCS, HLN, L, LSGH]. Due to these and many other nice properties, a number of real hypercube computers have been built [DD, Sc, Se] and effort will be devoted to research on this architecture. .sh 2 "Running Algorithms on Hypercubes" .pp A parallel algorithm usually consists of a number of tasks that can be run in parallel. In order to fully exploit the power of a hypercube, the tasks that constitute the whole algorithm should be distributed evenly among the processors. Moreover, related tasks in which coordination is required should be assigned to nearby processors so that communication is easy. To achieve such a task assignment, the algorithm can be abstracted as a \fItask graph\fR in which a node represents a task and an edge between two nodes represents the need for communication between the two tasks. Similarly, the hypercube can be represented as a \fIprocessor graph\fR in which nodes and edges correspond to processors and communication links respectively. Then the problem of assigning the tasks to the processors can be formulated as the problem of \fIembedding\fR the task graph into the processor graph. (For convenience, we shall refer to the processor graph of a hypercube computer as \fIhypercube\fR.) .pp Formally, an embedding of a graph $G$ into a graph $H$ is a mapping from the nodes of $G$ to nodes of $H$ and from the edges in $G$ to paths in $H$. There are four important attributes of an embedding: \fIexpansion\fR, \fIload\fR, \fIdilation\fR and (\fInode\fR/\fIedge\fR) \fIcongestion\fR. \fBExpansion\fR is the ratio of the number of nodes in $H$ to that in $G$. \fBLoad\fR is the maximum number of nodes in $G$ mapped to the same node in $H$. \fBDilation\fR is the worst case shortest distance between the images of two adjacent nodes in $G$. \fBNode/edge congestion\fR is the maximum number of edges in $G$ with their images sharing the same intermediate nodes/edges in $H$. .pp Obviously, a satisfactory embedding of a task graph into a processor graph should have small values in all these parameters. Small expansion and load means that both efficiency and processor utilization are high. Small dilation and congestion implies that communication between related tasks can be carried out efficiently. Note that congestion is somewhat related to dilation. For instance, when dilation is 1, there will be no congestion (i.e., congestion is 1). However, a slight increase in dilation (to 2 or 3, say) may bring about a large increase in congestion. .sh 2 "Embedding Binary Trees into Hypercubes .pp The class of parallel algorithms that have \fIfull binary trees\fR as their task graphs is of special interests. This covers many algorithms such as those broadcasting, parallel prefix and other divide-and-conquer algorithms. Thus it is worthwhile to study the embedding of full binary trees into hypercubes. .pp A full binary tree with $n$ levels (or equivalently, $2 sup n -1$ nodes) is called an \fZn\fB-tree\fR. A hypercube of $n$ dimensions (called an \fZn\fB-cube\fR) is an undirected graph of $2 sup n$ nodes each having a unique $n$-bit label. Two nodes are connected by a link if and only if their labels differ in exactly one bit position. .pp Figure 1.1 shows an embedding of a 3-tree into a 3-cube. The embedding has load 1 because every hypercube node receives at most 1 tree node. It has dilation 2 since the shortest distance between the images of $B$ and $E$ is 2 and this is the worst (longest) among all pairs of adjacent tree nodes. The edge congestion is 2 because the most congested edge is that between hypercube nodes 001 and 011, used by the paths for $BD$ and $BE$ assuming $BE$ is mapped to the path $001 -> 011 -> 010$. .(z .PS T:[ box invis wid 1i ht .5i line from last box.sw to last box.n line from last box.se to last box.n ] TL:[ box invis wid .6i ht .5i line from last box.sw to last box.n line from last box.se to last box.n ] with .n at T.sw TR:[ box invis wid .6i ht .5i line from last box.sw to last box.n line from last box.se to last box.n ] with .n at T.se "\(bu" at T.n "\(bu" at TR.n "\(bu" at TR.sw "\(bu" at TR.se "\(bu" at TL.n "\(bu" at TL.sw "\(bu" at TL.se "$A$" at T.n + (0,.1i) "$B$" at TL.n + (-.1i,0) "$C$" at TR.n + (-.1i,0) "$D$" at TL.sw + (-.1i,0) "$E$" at TL.se + (-.1i,0) "$F$" at TR.sw + (-.1i,0) "$G$" at TR.se + (-.1i,0) "(a) a 3-tree" at T.s + (0,-.8i) H0:[ box wid .6i ht .6i ] at T + (3i,0) H1:[ box wid 1.5i ht 1.5i ] at H0 line from H1.sw to H0.sw line from H1.se to H0.se line from H1.nw to H0.nw line from H1.ne to H0.ne "\(bu" at H1.nw "\(bu" at H1.ne "\(bu" at H1.sw "\(bu" at H1.se "\(bu" at H0.nw "\(bu" at H0.ne "\(bu" at H0.sw "\(bu" at H0.se "000" at H0.nw + (-.2i,0) "001" at H0.ne + (.2i,0) "010" at H0.sw + (-.2i,0) "011" at H0.se + (.2i,0) "100" at H1.nw + (-.2i,0) "101" at H1.ne + (.2i,0) "110" at H1.sw + (-.2i,0) "111" at H1.se + (.2i,0) "(b) a 3-cube" at H1.s + (0,-.3i) .PE .PS H0:[ box dashed wid .6i ht .6i ] H1:[ box dashed wid 1.5i ht 1.5i ] at H0 line dashed from H1.sw to H0.sw line dashed from H1.se to H0.se line from H1.nw to H0.nw line dashed from H1.ne to H0.ne line from H0.nw to H0.ne line from H0.ne to H0.se line from H0.se to H0.sw line from H1.sw to H1.nw line from H1.nw to H1.ne "\(bu" at H1.nw "\(bu" at H1.ne "\(bu" at H1.sw "\(bu" at H1.se "\(bu" at H0.nw "\(bu" at H0.ne "\(bu" at H0.sw "\(bu" at H0.se "A" at H0.nw + (-.2i,0) "B" at H0.ne + (.2i,0) "D" at H0.se + (.2i,0) "E" at H0.sw + (-.2i,0) "C" at H1.nw + (-.2i,0) "F" at H1.ne + (.2i,0) "G" at H1.sw + (-.2i,0) "(c) an embedding of a 3-tree into a 3-cube" at H1.s + (0,-.3i) .PE .fi Fig. 1.1. Embedding a 3-tree into a 3-cube. \fIPaths between images of adjacent tree nodes are shown as continuous lines. Note that tree edge $BE$ is mapped to the path (001,011,010) .ft R .)z .pp It was shown in [HL, Wa] and later in [BI] that an $n$-tree cannot be embedded into an $n$-cube with unit dilation and load for all $n~>=~3$. To see this, observe that there are $2 sup n-1$ leaf nodes in an $n$-tree. They are mapped to hypercube nodes of the same parity because the embedding has unit dilation and load. Furthermore, either the root or a son of the root has the same parity as the leaf nodes. Hence the embedding requires strictly more than $2 sup n-1$ hypercube nodes of the same parity when $n~>=~3$ and this is impossible for an $n$-cube. .pp On the other hand, [BI, Wu] showed that the embedding of an $(n-1)$-tree can be done. .sh 2 "Handling Faults" .pp As a hypercube computer consists of many processors and communication links, each having a nonzero probability of failure, it is not rare for the computer to contain some faulty components. Thus, fault tolerant computing on hypercube computers is an important issue for investigation. .pp Here we consider a strong fault model wherein a faulty processor can neither compute nor communicate with its neighbors. To keep on running in the presence of faults, we need to find an embedding that never maps a task to a faulty processor. Also, it cannot use any faulty link or a link which is nonfaulty but adjacent to a faulty processor. Such an embedding is called a \fIfault-tolerant embedding\fR. In a real hypercube computer, both the processors and communication links can go faulty. However, we only consider faulty processors. A faulty link can be handled by treating either of the two processors connected by the link as faulty. Also, we assume the faults are static and known before we perform the embedding. .pp There is a fundamental difference between the embeddings in hypercubes with and without faults. When there are no faults, every node is identical (by symmetry of the hypercube). That means where we place the root does not affect the embedding. However, when faults are present, the embedding may not be possible if we place the root carelessly. As an example (see Figure 1.2), consider a 3-cube having 2 faulty nodes, 010 and 001. To embed a 2-tree with unit dilation and load, the root can be placed at 100 but not at 000. .(z .PS H0:[ box wid .6i ht .6i ] H1:[ box wid 1.5i ht 1.5i ] at H0 line from H1.sw to H0.sw line from H1.se to H0.se line from H1.nw to H0.nw line from H1.ne to H0.ne .ps +3 "\(bu" at H0.ne "\(bu" at H0.sw .ps -3 "000" at H0.nw + (-.2i,0) "001" at H0.ne + (.2i,0) "010" at H0.sw + (-.2i,0) "011" at H0.se + (.2i,0) "100" at H1.nw + (-.2i,0) "101" at H1.ne + (.2i,0) "110" at H1.sw + (-.2i,0) "111" at H1.se + (.2i,0) .PE .ce Fig. 1.2. A 3-cube with 2 faults (depicted by large black dots) .)z .pp Hence we distinguish two variations of the fault-tolerant embedding problem. The \fBspecified root embedding problem\fR is the problem of embedding an $(n-1)$-tree into an $n$-cube with unit dilation and load. Furthermore, the root of the tree must be mapped to a \fIspecified\fR hypercube node. The \fBvariable root embedding problem\fR is similar but the root can be mapped to \fIany\fR nonfaulty hypercube node. It was shown in [CL1] that $n-1-\(lc log n \(rc$ faults can be tolerated for the variable root embedding problem. Later, [WCM] improved this to $OMEGA (n sup 2 / log n )$ faults. For the specified root embedding problem, [WCM] showed that $\(lcn/4\(rc$ faults can be tolerated. The smaller number of tolerable faults is expected since there are more restrictions on the specified root embedding problem. .sh 2 "Our Results" .pp This thesis studies both the specified and variable root embedding problems. In particular, we present three new results in regards to these two problems: .ip (i) for the specified root embedding problem, up to $n-2$ faults (this is optimal) can be tolerated; .ip (ii) for the variable root embedding problem, up to $2n-3-\(lc log n\(rc$ faults can be tolerated. .ip (iii) for the variable root embedding problem, no more than $O(1/ sqrt n )\(mu2 sup n$ faults can be tolerated in the worst case. Furthermore, the result holds even if we allow unbounded dilation and $O(1)$ load. .lp It is interesting to note that our method for the variable root embedding is classified as a recursive embedding in [WCM]. It was proved in [WCM] that this type of embedding can tolerate no more than $2n-3$ faults. Hence we have achieved their bounds asymptotically. .sh 2 "Definitions and Notations" .pp The following definitions and notations will be used throughout the rest of this thesis. .pp We refer to the nodes of a hypercube by their labels. A node having a 0 (or 1) as the $k$th bit of its label is said to have a 0 (or 1) in dimension $k$, with the first bit or dimension taken to mean the leftmost bit. Two nodes are said to be neighbors of each other on dimension $i$ if and only if their labels agree in all but dimension $i$. .pp To specify subcubes of the $n$-cube, we use strings of length $n$ consisting of 0's, 1's and \*(st's only. A string of length $n$ with exactly $m$ \*(st's describes an $m$-cube within an $n$-cube. For example, \*(st01\*(st\*(st denotes the 3-cube comprised of the eight nodes 00100, 00101, 00110, 00111, 10100, 10101, 10110 and 10111 of a 5-cube. .pp The $n$ levels of an $n$-tree are numbered from 0 (highest) to $n-1$ (lowest), with the root at level 0. Nodes at level $i$ are denoted by strings of length $i$ consisting of $L$'s and $R$'s only. In particular, the empty string $epsilon$ specifies the root and if $T$ is a string denoting a tree node, $LT$ and $RT$ specify respectively the left and right son of that node. For example, a 3-tree is shown in Figure 1.3. .(b .PS B:[ box invis wid 2i ht .7i line from last box.sw to last box.n line from last box.se to last box.n ] BL:[ box invis wid 1.2i ht .5i line from last box.sw to last box.n line from last box.se to last box.n ] with .n at B.sw BR:[ box invis wid 1.2i ht .5i line from last box.sw to last box.n line from last box.se to last box.n ] with .n at B.se L:[ box invis wid .2i ht 1.2i ] with .n at B.n + (2i,0) "levels" at L.n + (0,.2i) "0" at L.n "1" at L.n + (0,-.7i) "2" at L.s "\(bu" at B.n "\(bu" at BL.n "\(bu" at BR.n "\(bu" at BL.sw "\(bu" at BL.se "\(bu" at BR.sw "\(bu" at BR.se "$epsilon$" at B.n + (0,.2i) "$L$" at BL.n + (-.2i,0) "$R$" at BR.n + (.2i,0) "$LL$" at BL.sw + (0,-.2i) "$RL$" at BL.se + (0,-.2i) "$LR$" at BR.sw + (0,-.2i) "$RR$" at BR.se + (0,-.2i) .PE .ce Fig. 1.3. A 3-tree. .)b .pp From now on, \fBembedding\fR refers to a fault-tolerant embedding with unit dilation and load unless otherwise stated. To specify the (unit dilation and load) embedding, we define $H[T]$ as the hypercube node to which tree node $T$ is mapped. The mapping of tree edges to paths in hypercubes need not be specified explicitly because of unit dilation. As our embedding methods are recursive, it will be convenient to have some notations for specifying the subproblems. Thus we define $C[T]$ as the subcube in which we want to embed the subtree rooted at $T$. Furthermore, \fZT\fB-embedding\fR refers to the embedding of the subtree rooted at $T$ within $C[T]$, with $T$ mapped to $H[T]$. .bp .sh 1 "Specified Root Tree Embedding" .pp In this section, we consider the problem of specified root tree embedding. Our main result is the following. .lp \fBTheorem 2.1: \fR For all $n~>=~2$ and $0~<=~f~<=~n-2$, there exists an embedding of an $(n-1)$-tree into an $n$-cube containing $f$ faulty nodes/links with the root of the tree mapped to a specified nonfaulty node $S$ in the hypercube. .pp Note that $n-2$ faults are the maximum that can be tolerated when the root is specified. For example, if there were $n-1$ faulty nodes neighboring the specified node $S$, embedding would be impossible. On the other hand, Theorem 2.2 shows that faults can be ignored if they are far away from the root. .lp \fBTheorem 2.2: \fR The embedding of any $m$-tree with root mapped to hypercube node $S$ can never be affected by faulty node $F$ if the Hamming distance between $S$ and $F$ is $>=~m$. .lp \fBProof: \fR A level $i$ tree node can only be mapped to a hypercube node at Hamming distance $<=~i$ from $S$. Thus, the whole $m$-tree can only be mapped to hypercube nodes at Hamming distance $<=~m-1$ from $S$. Hence, it is impossible to use $F$ in any embedding. \*(sq .pp To simplify the proof for Theorem 2.1, we assume, without loss of generality, that (i) exactly $n-2$ faults with Hamming distance $<=~n-2$ from $S$ are in the $n$-cube, (ii) all of the faults are node faults, as link faults can be handled by treating either of the two nodes connected by the link as faulty, and (iii) $S~=~0 sup n$. We prove the theorem by actually constructing an embedding, i.e., performing the $epsilon$-embedding with $H[ epsilon ]~=~0 sup n$ and $C[ epsilon ]~=~\*(st sup n$. The construction is based on two techniques: \fIcube splitting\fR and \fInode borrowing\fR. .sh 2 "Cube Splitting and Node Borrowing" .pp The idea of cube splitting is to map $L$ and $R$ to two nonfaulty neighbors of $H[ epsilon ]$ and then embed the subtrees rooted at $L$ and $R$ into two disjoint subcubes. With $H[ epsilon ]~=~0 sup n$ and $C[ epsilon ]~=~\*(st sup n$, we say that $C[ epsilon ]$ is \fIsplit\fR on dimension $i$ if we set $C[L] ~=~\*(st sup i-1 1 \*(st sup n-i$, $C[R] ~=~\*(st sup i-1 0 \*(st sup n-i$ and $H[L] ~=~0 sup i-1 1 0 sup n-i$. (In other words, $H[L]$ is the neighbor of $H[ epsilon ]$ on dimension $i$, $C[L]$ is the subcube not containing $H[ epsilon ]$, and $C[R]$ is the other subcube. See Figure 2.1.) .(z $gsize 10$ .PS .ps 10 EA:[ ellipse wid 1.5i ht 2.5i BA:[ box invis wid 1i ht 1i ] at last ellipse line from BA.sw to BA.se "$(n-2)$-tree" above line from BA.sw to BA.nw + (.5i,0) line from BA.se to BA.nw + (.5i,0) "\(bu" at BA.nw + (.5i,0) "$L$" at BA.nw + (.3i, 0) "$p$ faults" at BA.s + (0,-.3i) ] EB:[ ellipse wid 1.5i ht 2.5i BA:[ box invis wid 1i ht 1i ] at last ellipse line from BA.sw to BA.se "$(n-2)$-tree" above line from BA.sw to BA.nw + (.5i,0) line from BA.se to BA.nw + (.5i,0) "\(bu" at BA.nw + (.5i,0) "$R$" at BA.nw + (.7i, 0) "\(bu" at BA.nw + (.5i,.5i) "$epsilon$" at BA.nw + (.7i,.5i) line from BA.nw + (.5i,0) up .5i "$q$ faults" at BA.s + (0,-.3i) ] at EA + (2.5i,0) line from EA.BA.nw + (.5i,0) to EB.BA.nw + (.5i,.5i) "$C[L]=\*(st sup i-1 1 \*(st sup n-i$" at EA.BA.sw + (.5i,-1.1i) "$C[R]=\*(st sup i-1 0 \*(st sup n-i$" at EB.BA.sw + (.5i,-1.1i) "$i$" at EA.BA.n + (1.25i,.4i) .ps 12 .PE $gsize 12$ .ce Fig. 2.1. Splitting $C[ epsilon ]~=~\*(st sup n$ on dimension $i$. .)z .pp Thus by splitting $C[ epsilon ]$ on dimension $i$ and mapping $R$ to a nonfaulty neighbor of $H[ epsilon ]$ in $C[R]$, we reduce the original problem to two subproblems, i.e., finding the $L$- and the $R$-embeddings. (Note that $H[L]$ lies in $C[L]$ while $H[R]~=~0 sup j-1 1 0 sup n-j$ for some $j~!=~i$ must be in $C[R]$.) By recursively splitting the subcubes on suitable dimensions, we can derive an embedding in most circumstances. This type of embedding, in which the left and right subtrees of every internal node of the $(n-1)$-tree are mapped to disjoint subcubes, is called a \fIrecursive embedding\fR in [WCM]. .pp [WCM] also showed that there are certain fault patterns in which recursive embeddings are impossible. Fortunately, we find that only some leaves of the subtree rooted at $R$ cannot be mapped within $C[R]$. We overcome this problem by \fIborrowing\fR some nodes from $C[L]$, i.e., mapping these leaves to nonfaulty nodes in $C[L]$. While performing the $L$-embedding, the borrowed nodes are treated as faults. This avoids mapping the subtree of $L$ to these nodes. As only a few nodes in $C[L]$ are borrowed (will be shown later), the $L$-embedding is not much affected and hence the whole embedding can be done. .sh 2 "Constructing the Embedding" .pp We construct the $epsilon$-embedding recursively. The base cases, where $n~<=~5$, are considered in Section 2.4. .pp For $n~>=~6$, the first step is to find a suitable dimension to split $C[ epsilon ]$. Suppose we split on some dimension $i$ such that $C[L]$ contains $p$ faults and $C[R]$ contains $q$ faults (see Figure 2.1). Then the subtree in $C[L]$ has to avoid $p$ faults while that in $C[R]$ has to avoid $q$ faults and the assigned node $H[ epsilon ]$. Ideally, we want to split $C[ epsilon ]$ so that $p~<=~n-3$ and $q~<=~n-4$. Then we can perform the $L$- and $R$-embeddings recursively. However, this is not always achievable. Thus our strategy is to ensure $p~<=~n-3$ first. More precisely, we split $C[ epsilon ]$ on dimension $i$ provided .ip (A1) $H[L]$ is nonfaulty, .ip (A2) $C[L]$ has at most $n-3$ faults and .ip (A3) $C[L]$ has as many faults as possible while satisfying conditions (A1) and (A2). .lp Theorem 2.3 below shows that a dimension $i$ which satisfies conditions (A1) and (A2) can always be found. Among all the different possibilities for $i$, we choose the one which \fImaximizes\fR $p$. Hence, the splitting can always be done. .lp \fBTheorem 2.3: \fR There exists a dimension $i$ such that $\*(st sup i-1 1 \*(st sup n-i$ has at most $n-3$ faults (i.e., $\*(st sup i-1 0 \*(st sup n-i$ has at least one fault) and $0 sup i-1 1 0 sup n-i$ is a nonfaulty hypercube node. .lp \fBProof: \fR The faults must differ in some dimension $j$, i.e., both $\*(st sup j-1 0\*(st sup n-j$ and $\*(st sup j-1 1\*(st sup n-j$ have at least one fault. If $0 sup j-1 10 sup n-j$ is nonfaulty, let $i$ be $j$. Otherwise, let $i$ be a dimension other than $j$ where $0 sup i-1 10 sup n-i$ is nonfaulty. Note that this dimension always exists as faulty node $0 sup j-1 10 sup n-j$ belongs to $\*(st sup i-1 0\*(st sup n-i$ and there are at most $n-2$ faults. \*(sq .pp To illustrate the idea of conditions (A1)-(A3), let us consider the following examples. .lp \fBExample 2.1: \fR $n~=~6$ and there are 4 faults: .(b C $beta sub 1$=100000 $beta sub 2$=010010 $beta sub 3$=111000 $beta sub 4$=101100 .)b .lp By condition (A1), we cannot split on dimension 1 because of $beta sub 1$. Also, all the remaining dimensions satisfy condition (A2). Among them, we can choose dimensions 2 or 3 because both $\*(st1\*(st\*(st\*(st\*(st$ and $\*(st\*(st1\*(st\*(st\*(st$ contains 2 faults. Hence we have $p~=~2$ in this case. \*(sq .lp \fBExample 2.2: \fR $n~=~6$ and the 4 faults are: .(l C $beta sub 1$=100011 $beta sub 2$=010011 $beta sub 3$=001011 $beta sub 4$=000011 .)l .lp This time, no neighbor of $H[ epsilon ]$ is faulty, thus condition (A1) is always satisified. However, we cannot split on dimensions 5 and 6 for violation of condition (A2). Among the remaining dimensions, we can choose dimensions 1, 2 or 3 because each of the subcubes 1\*(st\*(st\*(st\*(st\*(st, \*(st1\*(st\*(st\*(st\*(st and \*(st\*(st1\*(st\*(st\*(st contains 1 fault. Hence for this example, we have $p~=~1$. \*(sq .lp \fBExample 2.3: \fR $n~=~6$ and the 4 faults are: .(l C $beta sub 1$=010000 $beta sub 2$=001000 $beta sub 3$=000100 $beta sub 4$=011000 .)l .lp In this case, we cannot split on dimensions 2, 3 and 4 because of condition (A1). We can, however, split on dimensions 1, 5 or 6. Thus $p~=~0$ in this case. \*(sq .pp Based on $p$, we have two cases in general: (1) $0~<=~p~<=~1$ and (2) $2~<=~p~<=~n-3$. For case (2) where $2~<=~p~<=~n-3$, we have $q~=~n-2-p~<=~n-4$. Hence both the $L$- and $R$-embeddings can be done recursively. For case (1) where $0~<=~p~<=~1$, the $L$-embedding is still easy but the $R$-embedding is more complicated. There are effectively $q+1~=~n-1-p~>~n-3$ faults in $C[R]$ (the extra fault is from $H[ epsilon ]$) and we cannot perform the $R$-embedding as simply as in case (2). The details for this case are described in next section. .sh 2 "Case (1) where" $n~>=~6$, $0~<=~p~<=~1$. .pp In this case, we have to choose the dimension on which $C[ epsilon ]$ is split more carefully. As will be shown later, that dimension has to satisfy more contraints besides conditions (A1)-(A3). After that, we split $C[R]$ again so as to separate the $n-2-p+1 ~>~ n-3$ faults/assigned nodes. In particular, we ensure that $C[LR]$ contains as many faults as possible while not exceeding its \fIfault-tolerance capacity\fR (dimensionality of subcube minus 2). Then the $LR$-embedding can be done recursively. For the $RR$-embedding, we split $C[RR]$ again if it still contains too many faults. In general, we keep on splitting $C[R sup i ]$ until the $R sup i$-embedding can be done recursively. .pp Before describing the embedding strategy in detail, we first study some useful properties of the faults. We shall also arrange the dimensions so that the faults are of a standard pattern (Section 2.3.1). An example and the exact algorithm are then given in Sections 2.3.2 and 2.3.3 respectively. .pp As shown in the previous examples, for all $1~<=~i~<=~n$, $\*(st sup i-1 1 \*(st sup n-i$ cannot contain more than $p$ but less than $n-2$ faults unless $0 sup i-1 1 0 sup n-i$ is faulty (like dimension 1 in Example 2.1). Otherwise, we would have split on dimension $i$ according to condition (A3). In fact, when $p~=~0$, there are even more restrictions on the number of faults in these subcubes. .lp \fBLemma 2.1: \fR Given that $0 sup k-1 10 sup n-k$ is nonfaulty, .ip (a) when $p~=~1$, the number of faults in $\*(st sup k-1 1 \*(st sup n-k$ can only be 0, 1 or $n-2$; .ip (b) when $p~=~0$, the number of faults in $\*(st sup k-1 1 \*(st sup n-k$ must be 0. .lp \fBProof: \fR .br (a) is obvious, for if $\*(st sup k-1 \*(st sup n-k$ contains more than 1 but less than $n-2$ faults, we would have split on dimension $k$ according to condition (A3) and have $p~>~1$. .br (b) Note that $\*(st sup k-1 1\*(st sup n-k$ cannot contain more than 0 and less than $n-2$ faults. Otherwise we could split on dimension $k$ and have $p~>~0$. Assume that $\*(st sup k-1 1 \*(st sup n-k$ contains $n-2$ faults (i.e., all faults have a 1 in dimension $k$). Then, for any dimension $j~!=~k$, $0 sup j-1 1 0 sup n-j$ must not be faulty. Hence $\*(st sup j-1 1 \*(st sup n-j$ contains 0 or $n-2$ faults (i.e., all faults agree in dimension $j$) because $p~=~0$. This implies that all faults would be identical which is a contradiction. Thus the number of faults in $\*(st sup k-1 1\*(st sup n-k$ must be 0. \*(sq .pp Referring to Example 2.2, $0 sup k-1 10 sup n-k$ is nonfaulty for every $k$. Hence the number of faults in $\*(st sup k-1 1\*(st sup n-k$ is 0 (for $k$ = 4), 1 (for $k$ = 1, 2 or 3) or $n-2$ (for $k$ = 5 or 6). In Example 2.3, the number of faults in $\*(st sup k-1 1\*(st sup n-k$ is 0 when $k$ = 1, 5 or 6. .pp Define $x$ as the number of faulty nodes neighboring $H[ epsilon ]$, i.e., faulty neighbors of $H[ epsilon ]$. For example, $x~=~3$ in Example 2.3. The following lemma shows some bounds on the value of $x$. .lp \fBLemma 2.2: \fR .ip (a) $x~<=~n-2$ and .ip (b) when $p~=~0$, $x ~>=~ \(lc log (n-1) \(rc$. .lp \fBProof: \fR .br (a) is obvious as the number of faults is no more than $n-2$. .br (b) For all dimensions $k$ where $0 sup k-1 1 0 sup n-k$, neighbor of $H[ epsilon ]$, is nonfaulty, the number of faults in $\*(st sup k-1 1 \*(st sup n-k$, neighbor of $H[ epsilon ]$, must be 0 (Lemma 2.1b). Therefore all faults have 0 in dimension $k$. Moreover, $H[ epsilon ]~=~0 sup n$ also has 0 in this dimension. Thus the number of such dimensions, $k$, i.e. $n-x$, cannot be too large in order for the $n-2$ faults and $H[ epsilon ]$ to be distinct. In fact, it can be shown easily that $x ~>=~ \(lc log (n-1) \(rc$. \*(sq .sh 3 "Arranging Dimensions" .pp We choose dimension 1 so that $1\*(st sup n-1$ contains $p$ faults and $1 0 sup n-1$ is nonfaulty. This allows us to split $C[ epsilon ]$ on dimension 1. .pp Consider a dimension $k$ such that $2 ~<=~ k ~<=~ n$ and $0\*(st sup k-2 1\*(st sup n-k$ contains all the $n-2-p$ faults in $0\*(st sup n-1$. Let there be $n-m$ such dimensions. If $n-m~>~0$, we let them be the rightmost $n-m$ dimensions (Figure 2.2a and Example 2.2) so that we can easily choose nonfaulty nodes from $0 \*(st sup m-1 0 sup n-m$ during the embedding. In the case where $n-m~=~0$, we would instead find a dimension $k$ such that $0 \*(st sup k-2 0 \*(st sup n-k$ contains all $n-2-p$ faults and swap it to the rightmost dimension (see Figure 2.2b and Example 2.3). Again, this allows us to find nonfaulty nodes from $0\*(st sup n-2 1$ for embedding. Note that this dimension $k$ may not exist if we have not chosen dimension 1 carefully. Let us consider the following example. .lp \fBExample 2.4: \fR $n~=~6$ and the 4 faults are: .(l C $beta sub 1$=111000 $beta sub 2$=010000 $beta sub 3$=001000 $beta sub 4$=010111 .)l \*(sq .lp However, it can be proved that such a dimension $k$ can always be found by properly choosing dimension 1. In Example 2.4, we can swap dimension 1 and 4 (and also exchange row 1 with row 4) so that the faults have the following pattern (like the pattern in Figure 2.2b). Then we can choose nonfaulty nodes from $0 \*(st sup n-2 1$. .(l C $beta sub 4$=110011 $beta sub 2$=010000 $beta sub 3$=001000 $beta sub 1$=011100 .)l .(z $gsize 10$ .PS .ps 10 B1:[ box wid 2i ht 2i line from last box.nw + (.3i,0) to last box.sw + (.3i,0) line from last box.ne - (.6i,0) to last box.se - (.6i,0) line from last box.nw - (0,.2i) to last box.ne - (0,.2i) ] B2:[ box wid 2i ht 2i line from last box.nw + (.3i,0) to last box.sw + (.3i,0) line from last box.ne - (.3i,0) to last box.se - (.3i,0) line from last box.nw - (0,.2i) to last box.ne - (0,.2i) ] with .nw at B1.ne + (1i,0) "(a) $n~>~m$" at B1.s + (0,-0.3i) "dimension" at B1.n + (0,0.3i) "fault" at B1.w + (-0.5i,0.1i) "number" at B1.w + (-0.5i,-0.1i) "$z$" at B1.nw + (.15i,-0.1i) "0" at B1.nw + (.15i,-0.4i) .ps 6 "\(bu" at B1.nw + (.15i,-0.8i) "\(bu" at B1.nw + (.15i,-1.0i) "\(bu" at B1.nw + (.15i,-1.2i) .ps 10 "0" at B1.nw + (.15i,-1.8i) "$y$" at B1.ne + (-0.5i,-0.1i) .ps 6 "\(bu \(bu \(bu" at B1.ne + (-0.3i,-0.1i) .ps 10 "$y$" at B1.ne + (-0.1i,-0.1i) "1" at B1.ne + (-0.5i,-0.4i) .ps 6 "\(bu \(bu \(bu" at B1.ne + (-0.3i,-0.4i) .ps 10 "1" at B1.ne + (-0.1i,-0.4i) .ps 6 "\(bu" at B1.ne + (-0.3i,-0.8i) "\(bu" at B1.ne + (-0.3i,-1.0i) "\(bu" at B1.ne + (-0.3i,-1.2i) .ps 10 "1" at B1.ne + (-0.5i,-1.8i) .ps 6 "\(bu \(bu \(bu" at B1.ne + (-0.3i,-1.8i) .ps 10 "1" at B1.ne + (-0.1i,-1.8i) "1" at B1.nw + (-.1i,-0.1i) "2" at B1.nw + (-.1i,-0.4i) .ps 6 "\(bu" at B1.nw + (-.1i,-0.8i) "\(bu" at B1.nw + (-.1i,-1.0i) "\(bu" at B1.nw + (-.1i,-1.2i) .ps 10 "$n-2$" at B1.nw + (-.15i,-1.8i) "1" at B1.nw + (.15i,.1i) "2" at B1.nw + (.4i,.1i) .ps 6 "\(bu \(bu \(bu" at B1.nw + (.8i,.1i) .ps 10 "$m$" at B1.nw + (1.3i,.1i) "$m+1$" at B1.ne + (-0.4i,.1i) .ps 6 "\(bu\(bu\(bu" at B1.ne + (-0.2i,.1i) .ps 10 "$n$" at B1.ne + (-0.1i,.1i) "(b) $n~=~m$" at B2.s + (0,-0.3i) "dimension" at B2.n + (0,0.3i) "$z$" at B2.nw + (.15i,-0.1i) "0" at B2.nw + (.15i,-0.4i) .ps 6 "\(bu" at B2.nw + (.15i,-0.8i) "\(bu" at B2.nw + (.15i,-1.0i) "\(bu" at B2.nw + (.15i,-1.2i) .ps 10 "0" at B2.nw + (.15i,-1.8i) "$x$" at B2.ne + (-0.15i,-0.1i) "0" at B2.ne + (-0.15i,-0.4i) .ps 6 "\(bu" at B2.ne + (-0.15i,-0.8i) "\(bu" at B2.ne + (-0.15i,-1.0i) "\(bu" at B2.ne + (-0.15i,-1.2i) .ps 10 "0" at B2.ne + (-0.15i,-1.8i) "1" at B2.nw + (-.1i,-0.1i) "2" at B2.nw + (-.1i,-0.4i) .ps 6 "\(bu" at B2.nw + (-.1i,-0.8i) "\(bu" at B2.nw + (-.1i,-1.0i) "\(bu" at B2.nw + (-.1i,-1.2i) .ps 10 "$n-2$" at B2.nw + (-.15i,-1.8i) "1" at B2.nw + (.15i,.1i) "2" at B2.nw + (.4i,.1i) .ps 6 "\(bu \(bu \(bu" at B2.nw + (.9i,.1i) .ps 10 "$n-1$" at B2.nw + (1.6i,.1i) "$n$" at B2.ne + (-.15i,.1i) .ps 12 .PE $gsize 12$ .fi Fig. 2.2. The bit pattern of faults after arranging dimension 1 and the last $max (n-m,1)$ dimensions. The faults are listed row by row. $z$ is 0 or 1 depending on $p$ is 0 or 1. The value of $x$ and each of the $y$'s can be 0 or 1 subject to other conditions. .)z .pp The next step is to arrange dimensions 2 through $m$ such that for all $i$, $2~<=~i~<=~m$, $0 sup i-1 1 \*(st sup n-i$ contains as many faults as that in $0 sup i-1 \*(st sup k-i 1 \*(st sup n-k$ for all $k$ where $i~<=~k~<=~m$. The arrangement allocates more faults to larger subcubes and guarantees that $0 sup i-1 1 \*(st sup n-i$ contains no more than $n-i-2$ faults. Hence we can recursively embed an $(n-i-1)$-tree within this $(n-i)$-cube. .pp Finally, we may need to swap dimensions $\(lcm/2\(rc$ and $\(lcm/2\(rc+1$ to guarantee that a particular node used in the embedding is nonfaulty. .pp More precisely, the dimensions are arranged such that .ip (B1) subcube $1 \*(st sup n-1$ contains $p$ faults and $1 0 sup n-1$ is nonfaulty; .ip (B2) subcube $left {~~~ lpile { 0 \*(st sup m-1 1 sup n-m above 0 \*(st sup m-2 0 }~~~ lpile { if~n~>~m above if~n~=~m }~~~$ contains $n-2-p$ faults; .ip (B3) for all $i$, $2~<=~i~<=~m$, subcube $0 sup i-1 1 \*(st sup n-i$ contains at least as many faults as in $0 sup i-1 \*(st sup k-i 1 \*(st sup n-k$ for all $k$ such that $i~<=~k~<=~m$; .ip (B4) hypercube node $left {~~~ lpile { 0 sup \(lcm/2\(rc 1 sup \(lfm/2\(rf 0 sup n-m-1 1 above 0 sup \(lcm/2\(rc 1 sup \(lfm/2\(rf-1 0 }~~~ lpile { if~n~>~m above if~n~=~m }~~~$ is nonfaulty. .lp Lemma A.1 (in Appendix A) shows that conditions (B1) and (B2) are achievable by carefully choosing dimension 1. Lemma A.2 (in Appendix A) shows that dimensions 2 through $m$ can be arranged according to the number of faults in the subcubes $0 sup i-1 1\*(st sup n-i$ so as to satisfy condition (B3) without violating conditions (B1) and (B2). Finally, Lemma A.3 (in Appendix A) shows that if we need to swap dimensions $\(lcm/2\(rc$ and $\(lcm/2\(rc+1$ to satisfy condition (B4), this can be achieved while preserving conditions (B1)-(B3). .sh 3 "An Example of the Embedding" .pp We assume that $n~=~7$ and the 5 faults are as below: .(b C 0100000 0010000 0001000 0000100 0101000 .)b .lp The dimensions have been arranged such that conditions (B1)-(B4) are satisfied. In this example, $p~=~0$, $n~=~m$. The embedding will be defined as follows (Figure 2.3): .(l .ta .5i .8i 2i 2.2i 2.5i $H[ epsilon ]$ = 0000000 $H[L]$ = 1000000 $H[R]$ = 0000001 $C[L]$ = 1\*(st\*(st\*(st\*(st\*(st\*(st $C[R]$ = 0\*(st\*(st\*(st\*(st\*(st\*(st $H[LR]$ = 0100001 $H[RR]$ = 0000011 $C[LR]$ = 01\*(st\*(st\*(st\*(st\*(st $C[RR]$ = 00\*(st\*(st\*(st\*(st\*(st $H[LR sup 2 ]$= 0010011 $H[RR sup 2 ]$ = 0000111 $C[LR sup 2 ]$ = 001\*(st\*(st\*(st\*(st $C[RR sup 2 ]$ = 000\*(st\*(st\*(st\*(st .)l .pp The main ideas of our embedding strategy are illustrated here. The embedding strategy for $p~=~1$ is similar. .pp Since each of the subcubes $C[L]~=~1\*(st\*(st\*(st\*(st\*(st\*(st$, $C[LR]~=~01\*(st\*(st\*(st\*(st\*(st$ and $C[LR sup 2 ]~=~001\*(st\*(st\*(st\*(st$ contains no more than two faults, the $L$-, $LR$-and $LR sup 2$-embeddings of a 5-tree, 4-tree and 3-tree in $C[L]~=~1\*(st\*(st\*(st\*(st\*(st\*(st$, $C[LR]~=~01\*(st\*(st\*(st\*(st\*(st$ and $C[LR sup 2 ]~=~001\*(st\*(st\*(st\*(st$ rooted at $H[L]~=~1000000$, $H[LR]~=~0100001$ and $H[LR sup 2 ]~=~0010011$ respectively, are always possible by recursion. .(z $gsize 10$ .PS .ps 10 B:[ box invis wid 2i ht 1i line from last box.sw to last box.n line from last box.se to last box.n ] BR:[ box invis wid 2i ht 1i line from last box.sw to last box.n line from last box.se to last box.n ] with .n at B.se BRR:[ box invis wid 2i ht 1i line from last box.sw to last box.n line from last box.se to last box.n ] with .n at BR.se BRRR:[ box invis wid 2i ht 1i line from last box.sw to last box.nw + (1i,0) line from last box.se to last box.ne - (1i,0) ] with .n at BRR.se "\(bu" at B.n "\(bu" at B.sw "\(bu" at BR.nw + (1i,0) "\(bu" at BR.sw "\(bu" at BRR.n "\(bu" at BRR.sw "\(bu" at BRRR.nw + (1i,0) "\(bu" at BRRR.sw "\(bu" at BRRR.se "1" at B.sw + (.4i,.5i) "7" at B.se + (-.4i,.5i) "2" at BR.sw + (.4i,.5i) "6" at BR.se + (-.4i,.5i) "3" at BRR.sw + (.4i,.5i) "5" at BRR.se + (-.4i,.5i) "7" at BRRR.sw + (.4i,.5i) "4" at BRRR.se + (-.4i,.5i) "$H[ epsilon ]~=~0000000$" at B.n + (0,.3i) "$C[ epsilon ]~=~\*(st\*(st\*(st\*(st\*(st\*(st\*(st$" at B.n + (0,.1i) "$H[L]~=~1000000$" at B.sw + (0,-.1i) "$C[L]~=~1\*(st\*(st\*(st\*(st\*(st\*(st$" at B.sw + (0,-.3i) "$H[R]~=~0000001$" at BR.nw + (1.8i,.1i) "$C[R]~=~0\*(st\*(st\*(st\*(st\*(st\*(st$" at BR.nw + (1.8i,-.1i) "$H[LR]~=~0100001$" at BR.sw + (0,-.1i) "$C[LR]~=~01\*(st\*(st\*(st\*(st\*(st$" at BR.sw + (0,-.3i) "$H[R sup 2 ]~=~0000011$" at BRR.nw + (1.8i,.1i) "$C[R sup 2 ]~=~00\*(st\*(st\*(st\*(st\*(st$" at BRR.nw + (1.8i,-.1i) "$H[LR sup 2 ]~=~0010011$" at BRR.sw + (0,-.1i) "$C[LR sup 2 ]~=~001\*(st\*(st\*(st\*(st$" at BRR.sw + (0,-.3i) "$H[R sup 3 ]~=~0000111$" at BRRR.nw + (1.8i,.1i) "$C[R sup 3 ]~=~000\*(st\*(st\*(st\*(st$" at BRRR.nw + (1.8i,-.1i) "$H[LR sup 3 ]~=~0000110$" at BRRR.sw + (0,-.1i) "$C[LR sup 3 ]~=~000\*(st\*(st\*(st0$" at BRRR.sw + (0,-.3i) "$H[R sup 4 ]~=~0001111$" at BRRR.se + (0,-.1i) "$C[R sup 4 ]~=~000\*(st\*(st\*(st1$" at BRRR.se + (0,-.3i) "faults = $left { pile {0100000 above 0101000} right }$" at BR.sw + (0,-.5i) "faults = {0010000}" at BRR.sw + (0,-.3i) "faults = $left { pile {0001000 above 0000100 above 0000000} right }$" at BRRR.sw + (0,-.4i) "faults = $left { pile {0000001 above 0000011 above 0000111} right }$" at BRRR.se + (0,.1i) .ps 12 .PE $gsize 12$ .ce Fig. 2.3. An example for a 7-cube .)z .pp On the other hand, the $R sup 3$-embedding of a 3-tree rooted at $H[R sup 3 ]~=~0000111$ into the $C[R sup 3 ] ~=~000\*(st\*(st\*(st\*(st$ has to avoid the faults 0001000, 0000100, and the assigned nodes 0000000, 0000001 and 0000011. Among these five nodes, only 0001000 and 0000000 are at Hamming distance $>=~3$ from 0000111 and can be ignored by the embedding (Theorem 2.2). Thus the $R sup 3$-embedding cannot be performed by straightforward recursion. Fortunately, the faults and the assigned hypercube nodes can be somewhat separated by splitting $C[R sup 3 ]$ on dimension $n~=~7$. That is, let $H[LR sup 3 ] ~=~ 0000110$, $C[LR sup 3 ]~=~000\*(st\*(st\*(st0$ and $H[RR sup 3 ] ~=~ 0001111$, $C[RR sup 3 ]~=~000\*(st\*(st\*(st1$. .pp $C[LR sup 3 ]$ will contain faults 0001000, 0000100 and the designated root 0000000. Since 0000000 and 0001000 are at Hamming distance $>=~2$ from 0000110, they can all be ignored by the embedding according to Theorem 2.2. Thus, the $LR sup 3$-embedding can be performed successfully. .pp On the other hand, $C[R sup 4 ]$ contains the assigned nodes 0000001, 0000011 and 0000111. As 0000001 and 0000011 are of Hamming distance $>=~2$ from 00001111 and can be ignored, the $R sup 4$-embedding can also be done recursively by considering 0000111 as the only fault in the $C[R sup 4 ]$. Thus, the embedding can be done. .pp Note that except $H[L]$ and $H[LR sup 3 ]$, all the assigned nodes are in \*(st\*(st\*(st\*(st\*(st\*(st1. By condition (B2), all faults are in \*(st\*(st\*(st\*(st\*(st\*(st0. Hence these assigned nodes cannot be faulty. Also, $H[L]$ and $H[LR sup 3 ]$ are nonfaulty due to conditions (B1) and (B4) respectively. Condition (B3) ensures that all the $L$-, $LR$-, $LR sup 2$- and $R sup 3$-embeddings are possible. .sh 3 "Description of the Embedding" .pp We first split $C[R sup i-1 ]$ on dimension $i$ for $i~=~1,^\(el,^\(lfm/2\(rf$ so that $C[LR sup i-1 ]$ equals the $(n-i)$-cube, $0 sup i-1 1 \*(st sup n-i$, and $C[RR sup i-1 ]$ equals $0 sup i-1 0 \*(st sup n-i$. That means the subtree rooted at $LR sup i-1$ is to be embedded within $0 sup i-1 1 \*(st sup n-i$. When splitting $C[R sup i-1 ]$, some of the faults within the subcube fall into $C[LR sup i-1 ]$. With the arrangement of dimensions in Section 2.3.1, $C[LR sup i-1 ]$ gets as many faults as possible but no more than $n-i-2$ (the fault-tolerance capacity of $C[LR sup i-1 ]$). Moreover, it does not contain any assigned nodes except $H[LR sup i-1 ]$ itself (to be proved later). Hence, the $LR sup i$-embedding can be done recursively. .pp On the other hand, $C[RR sup i-1 ]~=~0 sup i-1 0 \*(st sup n-i$ will get the remaining faults together with the assigned nodes: $H[ epsilon ]$, $H[R]$, \(el , $H[R sup i-1 ]$. Note that these are the only assigned nodes we need to take care of while mapping the tree node $RR sup i-1$ in $C[RR sup i-1 ]$. It is because the subtrees rooted at $L$, $LR$, \(el, $LR sup i-1$ will not be embedded within $C[RR sup i-1 ]$ and the descendants of $RR sup i-1$ have not been assigned yet. Moreover, it will be proved that these assigned nodes will not fall into $C[LR sup i-1 ]$. Consider dimensions $i+1$ to $n$. We must map $RR sup i-1$ to a neighbor of $H[R sup i-1 ]$ on one of these dimensions. Among them, we choose dimension $m+1-i$ so that the Hamming distances between $H[RR sup i-1 ]$ and most of the faults are greater than those between $H[R sup i-1 ]$ and the corresponding faults. This way, the roots of lower subtrees will be further and further away from most of the faults. .pp By the time $i~=~\(lfm/2\(rf$, there will be approximately $m/2$ assigned nodes and at most $n-2-m/2$ faults within $C[R sup \(lfm/2\(rf ]$. By splitting on dimension $n$ and choosing a suitable $H[RR sup \(lfm/2\(rf ]$ (depending on whether $m$ is even or odd), it can be shown that $C[LR sup \(lfm/2\(rf ]$ contains all the remaining faults while $C[RR sup \(lfm/2\(rf ]$ contains all the assigned nodes. However, many of the faults will be very far from $H[LR sup \(lfm/2\(rf ]$. In fact, when $m$ is even, most of the faults will be too far to affect the embedding. When $m$ is odd, there are also several faults which can be ignored. Anyway, the number of \fIeffective\fR faults/assigned nodes within each subcube does not exceed their fault-tolerance capacities. Hence the $LR sup \(lfm/2\(rf$-, and $RR sup \(lfm/2\(rf$-embeddings can also be done recursively. The whole $epsilon$-embedding is then completed. .pp Refer to Figure 2.4 for a pictorial view of the general embedding. .ip "Step (1)" 10 For $i~=1,\(el,~\(lfm/2\(rf$, let .sp .25 .in 1i $H[LR sup i-1 ]~=~ 0 sup i-1 10 sup m-2i 01 sup i-1 0 sup n-m$ $C[LR sup i-1 ]~=~ 0 sup i-1 1 \*(st sup n-i$ .br $H[RR sup i-1 ]~=~ 0 sup i-1 00 sup m-2i 11 sup i-1 0 sup n-m$ $C[RR sup i-1 ]~=~ 0 sup i-1 0 \*(st sup n-i$ .in 0 .sp .25 .ip "Step (2)" 10 For $i~=1,\(el,~\(lfm/2\(rf$, recursively perform the $LR sup i-1$-embedding, i.e., embed the $(n-1-i)$-tree rooted at $LR sup i-1$ into the $(n-i)$-cube $C[LR sup i-1 ]$. .ip "Step (3)" 10 Suppose $H[R sup \(lfm/2\(rf ]~=~$ $0 sup \(lcm/2\(rc 1 sup \(lfm/2\(rf 0 sup n-m ~=~ 0 sup \(lfm/2\(rf a sub \(lfm/2\(rf+1 \(el a sub n$. .br Then, we let .in 1i $H[ LR sup \(lfm/2\(rf ]~=~ 0 sup \(lfm/2\(rf a sub \(lfm/2\(rf+1 \(el a sub n-1 a bar sub n$, $C[LR sup \(lfm/2\(rf ] ~=~ 0 sup \(lfm/2\(rf \*(st sup n-\(lfm/2\(rf-1 a bar sub n$, $H[ RR sup \(lfm/2\(rf ]~=~ left {~~~ lpile { 0 sup m/2 a sub m/2+1 \(el a sub n-2 a bar sub n-1 a sub n above 0 sup \(lfm/2\(rf a bar sub \(lfm/2\(rf+1 a sub \(lfm/2\(rf+2 \(el a sub n }~~~ lpile { for~m~ roman {even} above for~m~ roman {odd} }~~~$ and $C[RR sup \(lfm/2\(rf ] ~=~ 0 sup \(lfm/2\(rf \*(st sup n-\(lfm/2\(rf-1 a sub n$. .in 0i .ip "Step (4)" 10 Recursively perform the $RR sup \(lfm/2\(rf$-embedding, i.e., embed the $(n- \(lfm/2\(rf -2 )$-tree rooted at $RR sup \(lfm/2\(rf$ in the $(n- \(lfm/2\(rf -1 )$-cube, $C[RR sup \(lfm/2\(rf ]$. .ip "Step (5)" 10 Recursively perform the $LR sup \(lfm/2\(rf$-embedding, i.e., embed the $(n- \(lfm/2\(rf-2 )$-tree rooted at $LR sup \(lfm/2\(rf$ in the $(n- \(lfm/2\(rf-1 )$-cube, $C[LR sup \(lfm/2\(rf ]$. .(z $gsize 10$ .PS .ps 10 B:[ box invis wid 1.4i ht 1i line from last box.sw to last box.n line from last box.se to last box.n ] BR:[ box invis wid 1.4i ht 1i line from last box.sw to last box.n line from last box.se to last box.n ] with .n at B.se BRR:[ box invis wid 3i ht 1i line from last box.sw to last box.n line from last box.se to last box.n ] with .n at BR.se + (0,-1i) BRRR:[ box invis wid 3i ht 1i line from last box.sw to last box.n line from last box.se to last box.n ] with .n at BRR.se "\(bu" at B.n "\(bu" at B.sw "\(bu" at BR.n "\(bu" at BR.sw "\(bu" at BR.se "\(bu" at BR.se + (0,-.6i) "\(bu" at BR.se + (0,-.7i) "\(bu" at BR.se + (0,-.8i) "\(bu" at BRR.n "\(bu" at BRR.sw "\(bu" at BRRR.n "\(bu" at BRRR.sw "\(bu" at BRRR.se "1" at B.sw + (.3i,.5i) "$m$" at B.se + (-.25i,.5i) "2" at BR.sw + (.3i,.5i) "$m-1$" at BR.se + (-.15i,.5i) "$\(lfm/2\(rf$" at BRR.sw + (.5i,.5i) "$\(lcm/2\(rc+1$" at BRR.se + (-.4i,.5i) "$n$" at BRRR.sw + (.6i,.5i) "$H[ epsilon ]~=~0 sup n$" at B.n + (0,.3i) "$C[ epsilon ]~=~\*(st sup n$" at B.n + (0,.1i) "$H[L]~=~10 sup m-2 10 sup n-m$" at B.sw + (0,-.2i) "$C[L]~=~1\*(st sup n-1$" at B.sw + (0,-.4i) "$H[R]~=~00 sup m-2 1 0 sup n-m$" at BR.n + (.8i,.1i) "$C[R]~=~0\*(st sup n-1$" at BR.n + (.8i,-.1i) "$H[LR]~=~010 sup m-4 010 sup n-m$" at BR.sw + (0,-.2i) "$C[LR]~=~01\*(st sup n-2$" at BR.sw + (0,-.4i) "$H[R sup 2 ]~=~00 sup m-4 110 sup n-m$" at BR.se + (0,-.2i) "$C[R sup 2 ]~=~00\*(st sup n-2$" at BR.se + (0,-.4i) "$H[R sup \(lfm/2\(rf-1 ]~=~0 sup \(lcm/2\(rc+1 1 sup \(lfm/2\(rf-1 0 sup n-m$" at BRR.n + (1.2i,.1i) "$C[R sup \(lfm/2\(rf-1 ]~=~0 sup \(lfm/2\(rf-1 \*(st sup n-\(lfm/2\(rf+1$" at BRR.n + (1.2i,-.1i) "$H[LR sup \(lfm/2\(rf-1 ]~=~0 sup \(lfm/2\(rf-1 10 sup \(lcm/2\(rc-\(lfm/2\(rf+1 1 sup \(lfm/2\(rf-1 0 sup n-m$" at BRR.sw + (0,-.2i) "$C[LR sup \(lfm/2\(rf-1 ]~=~0 sup \(lfm/2\(rf-1 1\*(st sup n-\(lfm/2\(rf$" at BRR.sw + (0,-.4i) "$lpile { H[R sup \(lfm/2\(rf ] above ~~ } ~ lpile { =~0 sup \(lcm/2\(rc 1 sup \(lfm/2\(rf 0 sup n-m above =~0 sup \(lfm/2\(rf a sub \(lfm/2\(rf+1 \(el a sub n-1 a sub n }$" at BRRR.n + (1.3i,.1i) "$C[R sup \(lfm/2\(rf ]~=~0 sup \(lfm/2\(rf \*(st sup n-\(lfm/2\(rf$" at BRRR.n + (1.3i,-.1i) "$H[LR sup \(lfm/2\(rf ]~=~0 sup \(lfm/2\(rf a sub \(lfm/2\(rf+1 \(el a sub n-1 a bar sub n$" at BRRR.sw + (-.5i,-.1i) "$C[LR sup \(lfm/2\(rf ]~=~0 sup \(lfm/2\(rf \*(st sup n-\(lfm/2\(rf-1 a bar sub n$" at BRRR.sw + (-.5i,-.3i) "$H[RR sup \(lfm/2\(rf ]~=~left {~ lpile { 0 sup m/2 a sub (m/2)+1 \(el a bar sub n-1 a sub n above 0 sup \(lfm/2\(rf a bar sub \(lfm/2\(rf+1 a sub \(lfm/2\(rf+2 \(el a sub n }~~ lpile { for~m~even above for~m~odd }$" at BRRR.se + (-.5i,0) "$C[RR sup \(lfm/2\(rf ]~=~0 sup \(lfm/2\(rf \*(st sup n-\(lfm/2\(rf-1 a sub n$" at BRRR.se + (-.5i,-.3i) .ps 12 .PE $gsize 12$ .ce Fig. 2.4. Description of the Embedding .)z .pp There are a number of observations we can make to argue the validity of the above strategy: .ip (1) $m~>=~3$ (Lemma 2.8) .ip (2) For $i~=~1,\(el,\(lfm/2\(rf+1$, $H[LR sup i-1 ]$ and $H[RR sup i-1 ]$ are adjacent to $H[R sup i-1 ]$ (Lemmas 2.9a, 2.10a); .ip (3) For $i~=~1,\(el,\(lfm/2\(rf+1$, $H[LR sup i-1 ]$ and $H[RR sup i-1 ]$ are nonfaulty (Lemmas 2.9c, 2.10c); .ip (4) For $i~=~1,\(el,\(lfm/2\(rf+1$, $H[LR sup i-1 ]$ and $H[RR sup i-1 ]$ are distinct (Lemmas 2.9d, 2.10d); .ip (5) It is always possible to perform the $RR sup \(lfm/2\(rf$-embedding (Lemma 2.11); .ip (6) It is always possible to perform the $LR sup i-1$-embedding for $i~=~1~,\(el,~\(lfm/2\(rf$ (Lemma B.3 in Appendix B); .ip (7) It is always possible to perform the $LR sup \(lfm/2\(rf$-embedding with node borrowing (Lemma B.4 in Appendix B, Lemmas 2.12 and 2.13). .lp The above observations allow us to conclude that the embedding of an $(n-1)$-tree into an $n$-cube containing $n-2$ faults, with the root of the tree mapped to a specified nonfaulty hypercube node $S$, can be done when $n~>=~6$, $p~<=~1$. .lp \fBLemma 2.8: \fR For $n~>=~6$, $n-m~<=~3$ and $m~>=~3$. .lp \fBProof: \fR Assume to the contrary that $n-m~>=~4$. Note that all faults in $0 \*(st sup n-1$ lie in $0 \*(st sup m-1 1 sup n-m$ (condition (B2)). In other words, each fault is either in $0 \*(st sup k-2 1 \*(st sup m-k 1 sup n-m$ for some $2~<=~k~<=m$ or $0 sup m 1 sup n-m$. We can show that $0 \*(st sup k-2 1 \*(st sup m-k 1 sup n-m$ contains at most 1 fault (Lemma B.2a in Appendix B). Therefore the maximum possible number of faults in $0 \*(st sup n-1$ is $<=~m-1+1~=~m~<=~n-4~<~n-2-p$ which is impossible. Therefore $n-m~<=~3$ and hence $m~>=~3$ (as $n~>=~6$). \*(sq .lp Lemma 2.8 ensures that $\(lfm/2\(rf~>=~1$ and hence the above embedding strategy is well-defined. .lp \fBLemma 2.9: \fR For $i~=~1,~\(el,~\(lfm/2\(rf$, .ip (a) $H[LR sup i-1 ]$ and $H[RR sup i-1 ]$ are neighbors of $H[R sup i-1 ]$ on dimensions $i$ and $m+1-i$ respectively, .ip (b) $C[LR sup i-1 ]$ and $C[RR sup i-1 ]$ are disjoint subcubes obtained by splitting $C[R sup i-1 ]$ on dimension $i$, .ip (c) $H[LR sup i-1 ]$ and $H[RR sup i-1 ]$ are nonfaulty, .ip (d) $H[LR sup i-1 ]$ and $H[RR sup i-1 ]$ avoid all the assigned nodes above level $i$ (i.e., those $H[T]$ where $T$ is a tree node at level $j~<~i$) that lie in $C[R sup i-1 ]$. .lp \fBProof: \fR .br (a) and (b) are obvious by noting that $H[R sup i-1 ]~=~0 sup i-1 00 sup m-2i 01 sup i-1 0 sup n-m$, $H[LR sup i-1 ]~=~0 sup i-1 10 sup m-2i 01 sup i-1 0 sup n-m$, $H[RR sup i-1 ]~=~0 sup i-1 00 sup m-2i 11 sup i-1 0 sup n-m$; and that $C[R sup i-1 ]~=~0 sup i-1 \*(st sup n-i+1$, $C[LR sup i-1 ]~=~0 sup i-1 1\*(st sup n-i$, $C[RR sup i-1 ]~=~0 sup i-1 0\*(st sup n-i$. .lp (c) Since $H[LR sup i-1 ]$ and $H[RR sup i-1 ]$ (except $H[L]$) lie in $left {~~~ lpile { 0 \*(st sup m-1 0 sup n-m above 0 \*(st sup m-1 1 }~~~ lpile { n~>~m above n~=~m }~~~$ while all faults in $0 \*(st sup n-1$ are in $left {~~~ lpile { 0 \*(st sup m-1 1 sup n-m above 0 \*(st sup m-1 0 }~~~ lpile { n~>~m above n~=~m }~~~$ by condition (B2), these nodes are nonfaulty. Also, $H[L]$ is chosen as nonfaulty by condition (B1). .lp (d) Since $C[L]$, $C[LR]$, \(el, $C[LR sup i-2 ]$ and $C[RR sup i-2 ]~=~C[R sup i-1 ]$ are disjoint subcubes (a corollary of Lemma 2.9b), the subtrees rooted at $L$, $LR$, \(el, $LR sup i-2$ will not be mapped to nodes in $C[R sup i-1 ]$. Hence $H[ R sup j ]~=~0 sup j 0 sup m-2j 1 sup j 0 sup n-m$ for $j~=~0,~\(el,~i-1$ are the only assigned nodes above level $i$ that lie in $C[R sup i-1 ]$. After splitting $C[R sup i-1 ]$ on dimension $i$, they will fall into $C[RR sup i-1 ]$ (hence distinct from $H[LR sup i-1 ]$) and are at Hamming distance $i-j~>~0$ from $H[RR sup i-1 ]$. \(sq .lp \fBLemma 2.10: \fR .ip (a) $H[LR sup \(lfm/2\(rf ]$ and $H[RR sup \(lfm/2\(rf ]$ are neighbors of $H[R sup \(lfm/2\(rf ]$ on dimension $n$ and dimension $left {~~~ lpile { n-1 above \(lfm/2\(rf+1 }~~~ lpile { m~ roman {even} above m~ roman {odd} }~~~$ respectively; .ip (b) $C[LR sup \(lfm/2\(rf ]$ and $C[RR sup \(lfm/2\(rf ]$ are disjoint subcubes obtained by splitting $C[R sup \(lfm/2\(rf ]$ on dimension $n$; .ip (c) $H[LR sup \(lfm/2\(rf ]$ and $H[RR sup \(lfm/2\(rf ]$ are nonfaulty; .ip (d) $H[LR sup \(lfm/2\(rf ]$ and $H[RR sup \(lfm/2\(rf ]$ avoid all the assigned nodes above level $\(lfm/2\(rf+1$ that lie in $C[R sup \(lfm/2\(rf ]$. .lp \fBProof: \fR .br (a) and (b) are obvious from Step (3) of our embedding algorithm. .lp (c) $H[LR sup \(lfm/2\(rf ]$ is, in fact, the hypercube node $left {~~~ lpile { 0 sup \(lcm/2\(rc 1 sup \(lfm/2\(rf 0 sup n-m-1 1 above 0 sup \(lcm/2\(rc 1 sup \(lfm/2\(rf-1 0 }~~~ lpile { if~n~>~m above if~n~=~m }~~~$ and hence nonfaulty due to condition (B4). $H[RR sup \(lfm/2\(rf ]$ is nonfaulty using the same argument as in Lemma 2.9c. .lp (d) The only assigned nodes above level $\(lfm/2\(rf+1$ that lie in $C[R sup \(lfm/2\(rf ]$ are $H[R sup j ]$ for $j~=~1,~\(el,~\(lfm/2\(rf$ and if $n~>~m$, $H[ epsilon ]$ also. By splitting $C[R sup \(lfm/2\(rf ]$ on dimension $n$, they will be in $C[RR sup \(lfm/2\(rf ]$ (hence distinct from $H[LR sup \(lfm/2\(rf ]$) and at Hamming distance $left {~~~ lpile { (m/2)-2 above \(lfm/2\(rf-j+1 }~~~ lpile { j=1~and~n=m~and~m~ roman {even} above roman {otherwise} }~~~$ from $H[RR sup \(lfm/2\(rf ]$. \*(sq .pp Lemma 2.11 proves that the $RR sup \(lfm/2\(rf$-embedding can be done recursively by showing that the number of faults/assigned nodes in the subcube $C[RR sup \(lfm/2\(rf ]$ is no more than its fault-tolerance capacity, $n-\(lfm/2\(rf-3$. .lp \fBLemma 2.11: \fR It is always possible to perform the $RR sup \(lfm/2\(rf$-embedding. .lp \fBProof: \fR Note that $C[RR sup \(lfm/2\(rf ]~=~ 0 sup \(lfm/2\(rf \*(st sup n-\(lfm/2\(rf-1 a sub n$ where $a sub n ~=~ left {~~~ lpile { 0 above 1 }~~~ lpile { if~n~>~m above if~n~=~m }$ .br and hence does not contain any fault (condition (B2)). However, it contains the assigned nodes $H[R sup j ]$ for $j~=~1,\(el,\(lfm/2\(rf$ and if $n~>~m$, $H[ epsilon ]$ also. .lp Moreover, $H[RR sup \(lfm/2\(rf ]~=~ left {~~~ lpile { 0 sup (m/2) 1 sup (m/2) 0 sup n-m-2 10 above 0 sup (m/2) 1 sup (m/2)-1 00 above 0 sup (m/2) 1 sup (m/2)-2 01 above 0 sup \(lfm/2\(rf 1 sup \(lcm/2\(rc 0 sup n-m }~~~ lpile { if~m~ roman {even} ~and~n-m~>=~2 above if~m~ roman {even} ~and~n-m~=~1 above if~m~ roman {even} ~and~n-m~=~0 above if~m~ roman {odd} }~~$. .lp By rewriting $H[R sup j ]~=~0 sup j 0 sup m-2j 1 sup j 0 sup n-m$ as $0 sup \(lfm/2\(rf 0 sup \(lcm/2\(rc-j 1 sup j 0 sup n-m$, it is easy to see that $H[R sup j ]$ (except $H[ epsilon ]$ and $H[R]$ when $n~=~m$ and $m$ is even) is at Hamming distance $\(lfm/2\(rf-j+1$ from $H[RR sup \(lfm/2\(rf ]$. When $n~=~m$ and $m$ is even, $H[R]$ is at Hamming distance $\(lfm/2\(rf-2$ from $H[RR sup \(lfm/2\(rf ]$ and $H[ epsilon ]$ is outside $C[RR sup \(lfm/2\(rf ]$. Thus they will not affect the $RR sup \(lfm/2\(rf$-embedding. Since all the other assigned nodes have distinct Hamming distances from $H[RR sup \(lfm/2\(rf ]$, there are $<=~n-\(lfm/2\(rf-3$ assigned nodes at Hamming distance $<=~n-\(lfm/2\(rf-3$ from $H[RR sup \(lfm/2\(rf ]$. Hence the $RR sup \(lfm/2\(rf$-embedding can be done recursively. \*(sq .pp In a similar fashion, Lemma B.3 (in Appendix B) shows that the $LR sup i-1$-embedding for $i~=~1,\(el,~\(lfm/2\(rf$ can be done recursively and Lemma B.4 (in Appendix B) shows that the $LR sup \(lfm/2\(rf$-embedding is also possible when $n$ is even or $x~<~n-2$ (where $x$ is the number of faulty neighbors of $H[ epsilon ]$). Basically, the idea is to argue that the number of faults/assigned nodes in each of the subcubes is no more than its fault-tolerance capacity. .pp When $n$ is odd and $x~=~n-2$, for the $LR sup \(lfm/2\(rf$-embedding, we have to use node borrowing. Before we describe the embedding strategy for this case, let us consider the embedding of an $(n-1)$-tree into an $n$-cube with $n-1$ faults having a specific pattern and the tree root is mapped to a specific node (Lemma 2.12). The bit patterns of the specified root and faults can be described as follows. .(l .PS B: [ box invis wid 1i ht 1.5i ] "root" at B.nw + (-.5i,-.3i) "faults" at B.nw + (-.5i,-.5i) "0111\s-6\(bu\(bu\(bu\s011" at B.n + (0,-.3i) "0100\s-6\(bu\(bu\(bu\s000" at B.n + (0,-.5i) "0010\s-6\(bu\(bu\(bu\s000" at B.n + (0,-.7i) .ps 6 "\(bu" at B.n + (0,-.9i) "\(bu" at B.n + (0,-1.0i) "\(bu" at B.n + (0,-1.1i) .ps 12 "0000\s-6\(bu\(bu\(bu\s010" at B.n + (0,-1.3i) "0000\s-6\(bu\(bu\(bu\s001" at B.n + (0,-1.5i) .PE .)l .lp \fBLemma 2.12: \fR For all $n~>=~3$, it is always possible to embed an $(n-1)$-tree (except the leaf $L sup n-2$) into an $n$-cube with $n-1$ faults, $0 sup i 10 sup n-1-i$ for $i~=~1,~\(el,~n-1$ such that $H[ epsilon ]~=~01 sup n-1$ and $H[L sup n-3 ]~=~0 sup n-2 11$. .lp \fBProof: \fR The embedding can be done by having, for $i~=~1,\(el,~n-3$, .in 1i $H[LL sup i-1 ]~=~00 sup i-1 01 sup n-1-i$ $C[LL sup i-1 ] ~=~ \*(st 0 sup i-1 0 \*(st sup n-1-i$ .br $H[RL sup i-1 ]~=~10 sup i-1 11 sup n-1-i$ $C[RL sup i-1 ] ~=~ \*(st 0 sup i-1 1 \*(st sup n-1-i$ .in 0 .lp Refer to Figure 2.5 for a pictoral representation of the embedding. It can be shown that for $i~=~1,~\(el,~n-3$, $H[LL sup i-1 ]$ and $H[RL sup i-1 ]$ are neighbors of $H[L sup i-1 ]$ on dimension $i+1$ and 1 respectively. In addition, since these nodes have at least two 1's in their labels, they are nonfaulty. .lp Since for each $i~=~1,~\(el,~n-3$, the subcube $C[RL sup i-1 ]~=~ \*(st 0 sup i-1 1 \*(st sup n-i-1$ contains only one fault $0 sup i 1 0 sup n-i-1$ (which can be ignored by Theorem 2.2) and an assigned node $H[L sup i-1 ] ~=~0 sup i 1 sup n-i$, the $RL sup i-1$-embedding, for $i~=~1,~\(el,~n-3$, is possible by recursion. For the $L sup n-3$-embedding, $H[L sup n-3 ] ~=~00 sup n-3 11$ and $C[L sup n-3 ] ~=~\*(st 0 sup n-3 \*(st sup 2$ contains two faults $00 sup n-3 10$ and $00 sup n-3 01$. Hence, we can let $H[RL sup n-3 ]~=~10 sup n-3 11$. \*(sq .pp Note that in the above embedding, the tree node $L sup n-2$ cannot be embedded within $C[L sup n-3 ]$. .(z $gsize 10$ .PS .ps 10 B:[ box invis wid 1.4i ht 1i line from last box.sw to last box.n line from last box.se to last box.n ] BL:[ box invis wid 1.4i ht 1i line from last box.sw to last box.n line from last box.se to last box.n ] with .n at B.sw BLL:[ box invis wid 3i ht 1i line from last box.sw to last box.n line from last box.se to last box.n ] with .n at BL.sw + (0,-1i) "\(bu" at B.n "\(bu" at B.sw "\(bu" at B.se "\(bu" at BL.sw "\(bu" at BL.se "\(bu" at BL.sw + (0,-.6i) "\(bu" at BL.sw + (0,-.7i) "\(bu" at BL.sw + (0,-.8i) "\(bu" at BLL.n "\(bu" at BLL.sw "\(bu" at BLL.se "2" at B.sw + (.3i,.5i) "1" at B.se + (-.25i,.5i) "3" at BL.sw + (.3i,.5i) "1" at BL.se + (-.2i,.5i) "$n-2$" at BLL.sw + (.5i,.5i) "1" at BLL.se + (-.5i,.5i) "$H[ epsilon ]~=~01 sup n-1$" at B.n + (0,.3i) "$C[ epsilon ]~=~\*(st sup n$" at B.n + (0,.1i) "$H[L]~=~001 sup n-2$" at BL.n + (-.8i,.1i) "$C[L]~=~\*(st 0 \*(st sup n-2$" at BL.n + (-.8i,-.1i) "$H[R]~=~111 sup n-2$" at B.se + (0,-.2i) "$C[R]~=~\*(st 1 \*(st sup n-2$" at B.se + (0,-.4i) "$H[L sup 2 ]~=~0001 sup n-3$" at BL.sw + (0,-.2i) "$C[L sup 2 ]~=~\*(st 00 \*(st sup n-3$" at BL.sw + (0,-.4i) "$H[RL]~=~1011 sup n-3$" at BL.se + (0,-.2i) "$C[RL]~=~\*(st 01 \*(st sup n-3$" at BL.se + (0,-.4i) "$H[L sup n-4 ]~=~00 sup n-4 111$" at BLL.n + (1i,.1i) "$C[L sup n-4 ]~=~\*(st 0 sup n-4 \*(st\*(st\*(st$" at BLL.n + (1i,-.1i) "$H[L sup n-3 ]~=~00 sup n-4 011$" at BLL.sw + (0,-.2i) "$C[L sup n-3 ]~=~\*(st 0 sup n-4 0 \*(st\*(st$" at BLL.sw + (0,-.4i) "$H[RL sup n-4 ]~=~10 sup n-4 111$" at BLL.se + (0,-.2i) "$C[RL sup n-4 ]~=~\*(st 0 sup n-4 1 \*(st\*(st$" at BLL.se + (0,-.4i) .ps 12 .PE $gsize 12$ .ce Fig. 2.5. Description of the Embedding .)z .lp \fBLemma 2.13: \fR It is always possible to perform the $LR sup \(lfm/2\(rf$-embedding with node borrowing when $n$ is odd and $x~=~n-2$. (Note that $n~=~m$ in this case.) .lp \fBProof: \fR Note that $H[LR sup \(lfm/2\(rf ]~=~0 sup \(lfn/2\(rf 01 sup \(lfn/2\(rf-1 0$ and $C[LR sup \(lfm/2\(rf ]~=~0 sup \(lfn/2\(rf \*(st sup \(lcn/2\(rc-1 0$. Also the $n-\(lfm/2\(rf-2~=~\(lcn/2\(rc-2$ faults in $C[LR sup \(lfm/2\(rf ]$ are $0 sup \(lfn/2\(rf 00 sup i-1 10 sup \(lcn/2\(rc-2-i 0$ for $i~=~1,\(el,\(lcn/2\(rc-2$. Hence by Lemma 2.12, we can embed the subtree rooted at $LR sup \(lfm/2\(rf$ except the leaf $L sup n-2$. As $L sup n-3$ is mapped to $H[L sup n-3 ]~=~0 sup \(lfn/2\(rf 0 sup \(lfn/2\(rf-2 110$, we can borrow the node $10 sup \(lfn/2\(rf-1 0 sup \(lfn/2\(rf-2 110$ from $C[L]$, i.e., we can map $L sup n-2$ to that node. .lp Note that in this case where $x~=~n-2$, $p$ must be 0. Therefore $C[L]$ contains $p~=~0$ faults at Hamming distance $<=~n-3$ from $H[L]$. Hence the node $10 sup \(lfn/2\(rf-1 0 sup \(lfn/2\(rf-2 110$, which is at Hamming distance 2 from $H[L]~=~10 sup n-1$, must be nonfaulty. Finally, the $L$-embedding has to avoid the node $10 sup \(lfn/2\(rf-1 0 sup \(lfn/2\(rf-2 110$. As $n~>=~6$, this embedding is still possible by recursion. \*(sq .sh 2 "Base Cases" .pp When $n~=~2$, there are $n-2~=~0$ faults. When $n~=~3$, we can assume without loss of generality that the only fault is $001$. Thus we can set $H[L]~=~100$ and $H[R]~=~010$. .pp When $n~=~4$, we can enumerate all the sets of faults with Hamming distance at most 2 from $H[ epsilon ]~=~0000$, i.e., faults with one or two 1's. It is easy to see that any set of faults is equivalent to one of the following distinct sets by renaming of dimensions: {0100,0010}, {0100,1100}, {0100,1010}, {0110,1100} and {0110,1001}. In all cases, we can embed the 3-tree by setting $H[L]~=~1000$, $C[L]~=~1\*(st\*(st\*(st$, $H[R]~=~0001$ and $C[R]~=~0\*(st\*(st\*(st$. Note that $C[L]$ has at most 1 fault and $C[R]$ has 1 assigned node but no fault with Hamming distance $<=~1$ from $H[R]$. Hence both the $L$- and $R$-embeddings can be embedded easily. .pp When $n~=~5$, we try to split the 5-cube according to conditions (A1)-(A3). .br \(bu If $p~=~2$, $C[L]$ contains 2 faults and $C[R]$ contains 1 fault and $H[ epsilon ]$. Hence the $L$- and $R$-embeddings can be done recursively. .br \(bu If $p~=~1$, we can still apply the method in Section 2.3 to find the embedding. .br \(bu If $p~=~0$, there are only 2 possible sets of faults: {01000,00100,00010} and {01000,00100,01100}. Other sets of faults can be shown to be equivalent to one of them by arranging the dimensions according to Section 2.3.1. We can still apply the algorithm in Section 2.3.3. Although when the set of faults is {01000,00100,01100}, the 3-cube $01\*(st\*(st\*(st$ contains 2 faults, 01000 and 01100, the second one can be ignored (by Theorem 2.2). Hence the embedding can be done. .bp .sh 1 "Variable Root Tree Embedding" .pp In this section, we consider the problem of variable root tree embedding. Because we can choose any nonfaulty node as root, more faults can be tolerated. For example, consider the case of $n$ faults $0 sup i-1 10 sup n-i$, for $i~=~1,2,~\(el ,~n$, in the $n$-cube. While it is impossible to embed an $(n-1)$-tree rooted at $0 sup n$, it is easy to embed the tree rooted at $1 sup n$. In fact, we have the following result: .lp \fBTheorem 3.1: \fR For all $n~>=~5$ and $0~<=~f~<=~min (2n-7,2n-3-\(lc log n \(rc)$, there exists an embedding of an $(n-1)$-tree into an $n$-cube having $f$ faulty nodes/links. (In this case, the root can be mapped to any nonfaulty hypercube node.) .pp We still use cube splitting as our major technique for this problem. Suppose, for some dimension $i$, $\*(st sup i-1 1 \*(st sup n-i$ and $\*(st sup i-1 0 \*(st sup n-i$ contain $p$ and $q$ faults respectively. Without loss of generality, we assume $p~<=~q$. Then we set $C[R]~=~\*(st sup i-1 1 \*(st sup n-i$ and $C[L]~=~\*(st sup i-1 0 \*(st sup n-i$. Moreover, we shall map the root, $epsilon$, into $C[R]$. (See Figure 3.1 and note the difference between Figures 2.1 and 3.1.) .(z $gsize 10$ .PS .ps 10 EA:[ ellipse wid 1.5i ht 2.5i BA:[ box invis wid 1i ht 1i ] at last ellipse line from BA.sw to BA.se "$(n-2)$-tree" above line from BA.sw to BA.nw + (.5i,0) line from BA.se to BA.nw + (.5i,0) "\(bu" at BA.nw + (.5i,0) "$L$" at BA.nw + (.3i, 0) "$q$ faults" at BA.s + (0,-.3i) ] EB:[ ellipse wid 1.5i ht 2.5i BA:[ box invis wid 1i ht 1i ] at last ellipse line from BA.sw to BA.se "$(n-2)$-tree" above line from BA.sw to BA.nw + (.5i,0) line from BA.se to BA.nw + (.5i,0) "\(bu" at BA.nw + (.5i,0) "$R$" at BA.nw + (.7i, 0) "\(bu" at BA.nw + (.5i,.5i) "$epsilon$" at BA.nw + (.7i,.5i) line from BA.nw + (.5i,0) up .5i "$p$ faults" at BA.s + (0,-.3i) ] at EA + (2.5i,0) line from EA.BA.nw + (.5i,0) to EB.BA.nw + (.5i,.5i) "$C[L]=\*(st sup i-1 0 \*(st sup n-i$" at EA.BA.sw + (.5i,-1.1i) "$C[R]=\*(st sup i-1 1 \*(st sup n-i$" at EB.BA.sw + (.5i,-1.1i) "$i$" at EA.BA.n + (1.25i,.4i) .ps 12 .PE $gsize 12$ .ce Figure 3.1. Splitting $C[ epsilon ]~=~\*(st sup n$ on dimension $i$. .)z .pp Thus the $R$-embedding has to avoid $p+1$ faults effectively while the $L$-embedding has to avoid $q$ faults. As $p~<=~q$ and $f~<=~2n-7$, $p~<=~\(lff/2\(rf~<=~n-4$. Therefore we can map $R$ to any nonfaulty node in $C[R]$ as we wish and then perform the $R$-embedding using the specified root method. For the $L$-embedding, there may be more than $n-3$ faults in the $(n-1)$-cube $C[L]$. Hence we recursively apply the variable root method to perform the $L$-embedding. If we can show that the number of possible $L$-embeddings, each with a different $H[L]$, is greater than $p$, then there will always exist a choice for $H[L]$ in $C[L]$ whose neighbor in $C[R]$ is nonfaulty. Hence we can map $epsilon$ to this neighbor and map $R$ to a nonfaulty neighbor of $H[ epsilon ]$ in $C[R]$. (Remember that the $R$-embedding is always possible no matter where we place $H[R]$.) .pp Let $v(n,~f)$ be the number of nodes, $S$, in an $n$-cube with $f$ faulty nodes so that an $(n-1)$-tree can be embedded in the hypercube with the root mapped to $S$. .lp \fBLemma 3.1: \fR .ip (a) $v(n,f)~=~2 sup n -f$ for $f~=~0,1,~\(el ,~n-2$ and $n~>=~2$, .ip (b) $v(n,f)~>=~2 sup 2n-2-f -f$ for $f~=~n-2,~\(el ,~2n-7$ and $n~>=~5$. .lp \fBProof: \fR .ip (a) By Section 2, the embedding of an $(n-1)$-tree into an $n$-cube with at most $n-2$ faults is always possible as long as $H[ epsilon ]$ is nonfaulty. .ip (b) To be given in the rest of this section. \*(sq .pp A corollary of Lemma 3.1b is that $v(n,f)~>=~1$ as long as $f~<=~2n-3-\(lc log n \(rc$. Therefore, for the variable root embedding, we can tolerate up to $min (2n-7,2n-3-\(lc log n \(rc)$ faults, and hence Theorem 3.1 follows. We shall prove Lemma 3.1b by induction on $n$ with base case $n~=~5$. When $n~=~5$, $n-2~<=~f~<=~2n-7$ implies that $f~=~3$. By Lemma 3.1a, $v(n,f)~=~2 sup 5 -3~=~2 sup 2n-2-f -f$. Hence the base case is true. For $n~>=~6$, if $f~=~n-2$, then by Lemma 3.1a again, $v(n,f)~=~2 sup n -f~=~2 sup 2n-2-f -f$. Hence for the induction step, we just need to consider $n-1~<=~f~<=~2n-7$ only. .pp For $n~>=~6$ and $f~=~n-1,\(el, 2n-7$, we split $C[ epsilon ]$ on a dimension such that $p$ is as large as possible. There are two cases: .ip "Case (1):" 10 $p~>=~2$ (Section 3.1) .ip "Case (2):" 10 $p~=~1$ (Section 3.2) .sh 2 "Case (1)" where $p~>=~2$ .pp Note that $q~=~f-p~<=~f-2~<=~2(n-1)-7$. .sp .5v .br \(bu If $(n-1)-2~=~n-3~<=~q$, the $L$-embedding has $v(n-1,q)~>=~2 sup 2(n-1)-2-q -q$ possible nodes for $H[L]$ by the induction hypothesis. Of these nodes, at most $p$ have faulty neighbors in $C[R]$. For the other nodes, the root $epsilon$ can be mapped to their respective nonfaulty neighbors in $C[R]$ and the $R$-embedding can be done easily since $p~<=~n-4$. Hence $v(n,f)~>=~v(n-1,q)-p$ $>=~(2 sup 2n-2-(q+2) -q) -p~>=$ $2 sup 2n-2-f -f$ as $p~>=~2$. .sp .5v .br \(bu If $q~<=(n-1)-3~=~n-4$, then by Lemma 3.1a, the $L$-embedding has $v(n-1,q)~=~2 sup n-1 -q$ possible nodes for $H[L]$. Hence $v(n,f)~>=~v(n-1,q)-p$ = $(2 sup n-1 -q)-p~>=~2 sup 2n-2-f -f$ as $f~>=~n-1$. .sh 2 "Case (2)" where $p~=~1$ .pp In this case, we shall prove that $v(n,f)~>=~2 sup n-1 -f$ $>=~2 sup 2n-2-f -f$ for $f~>=~n-1$. We first prove that if $f~>=~n+2$, we can always find a dimension to split $C[ epsilon ]$ such that $q~>=~p~>=~2$. Hence $p~=~1$ implies $n-1~<=~f~<=~n+1$. .lp \fBLemma 3.2: \fR If $n~>=~4$ and $f~>=~n+2$, the $C[ epsilon ]$ can be split into two $(n-1)$-cubes, $C[L]$ and $C[R]$, such that $q~>=~p~>=~2$, where $q$ and $p$ are the number of faults in $C[L]$ and $C[R]$ respectively. .lp \fBProof: \fR Assume to the contrary that $p~<=~1$ for any dimension on which $C[ epsilon ]$ is split, in particular $C[L]~=~\*(st sup i-1 0 \*(st sup n-1$ and $C[R]~=~\*(st sup i-1 1 \*(st sup n-1$. (Note that if $q~<~p$, the $i$th bit of all faults can be complemented in order to have $q~>=~p$.) In other words, at most one fault has a 1 in its $i$th dimension. Thus, the total number of 1's in the labels of all the faults would be $<=~ n$. On the other hand, each fault (except $0 sup n$) has at least one 1 in its label. If there are $>=~ n+2$ faults, this would imply that there are $>=~ (n+1)$ 1's in the labels of all the faults. Thus, we can conclude that $p ~>=~ 2$. \*(sq .pp Since no less than $f-1$ faults (except $0 sup n$) have at least one 1 in their labels, it is easy to show that the set of faults possesses the following properties: .ip (P1) If $f~=~n+1$, the faults are $0 sup n$, and $0 sup i-1 1 0 sup n-i$ for $1~<=~i~<=~n$. .ip (P2) If $f~=~n$, there is at most one fault with two 1's. Should there be a fault with two 1's, there must exist fault $0 sup n$ with the remaining $n-2$ faults having a single 1 each. .ip (P3) If $f~=~n-1$, there are at most two faults with two 1's or (exclusive) one fault with three 1's. .ip (P4) There are at least $n-4$ faults with a single 1. .pp Let $S$ be an arbitrary nonfaulty hypercube node with 0's in $m$ dimensions. It is sufficient to show that the embedding is possible with $H[ epsilon ]~=~S$ provided $m$ is even and $<=~n-1$. .pp If $m~=~0$, i.e., $S~=~1 sup n$, at least $f-2$ faults are of Hamming distance $>=~n-1$ from $S$ and thus can be ignored (Theorem 2.2). As a consequence, the embedding of an $(n-1)$-tree into this $n$-cube is possible by the method in Section 2. .pp For $2~<=~m~<=~n-1$ where $m$ is even and $n~>=~6$, we shall arrange dimensions so that .ip (C1) $S$ is of the form $0 sup m 1 sup n-m $ with $n-m ~>=~ 1$, and subcube $0 sup m/2 \*(st sup n-(m/2)-1 1$ does not contain a fault with more than two 1's; .ip (C2) $10 sup n-1$ and $0 sup m-1 10 sup n-m$ are faulty; and .ip (C3) subcube $0 sup i-1 1 \*(st sup n-i$, $1~<=~i~<=~m-2$, contains at least as many faults as subcube $0 sup i 1 \*(st sup n-i-1$ does. More precisely, subcube $0 sup i-1 1 \*(st sup n-i$ contains exactly one fault for all $i$ such that $1~<=~i~<=~j$ for some $j~<=~m$. .pp Note that conditions (C1)-(C3) can always be satisfied through arrangement of dimensions. Consider condition (C1). There is at most one fault with more than two 1's (by property (P3)). Moreover it should be different from $S$ in at least one dimension because $S$ is nonfaulty. Suppose $S~=~0 sup m 1 sup n-m$. Then this fault must either have a 1 in a dimension from 1 to $m$ or a 0 in dimension from $m+1$ to $n$. By swapping this dimension to a dimension from 1 to $m/2$ or to dimension $n$, this fault will not lie in $0 sup m/2 \*(st sup n-(m/2)-1 1$. Hence condition (C1) is satisfied. Since there are at least two faults with a single 1 (from property (P4) and $n~>=~6$), condition (C2) can always be satisfied with arrangement of dimensions 1 and $m$. Furthermore, it is straightforward to arrange dimensions to satisfy condition (C3) without affecting dimension 1 and dimensions $m$ to $n$. .pp Our next step is to apply the embedding strategy for even $m$ and $2~<=~m~<=~n-1$ as described in Section 2.1. .sp .5 .in 0i .ip "Step (1)" 10 $H[ epsilon ] =~~ 0 sup m 1 sup n-m$ .sp .25 .in 0i .ip "Step (2)" 10 For $i~=~1,^\(el,^m/2$, .in 1i $H[LR sup i-1 ]~=~0 sup i-1 10 sup m-2i 01 sup i-1+n-m$ $C[LR sup i-1 ]~=~0 sup i-1 1 \*(st sup n-i$ .br $H[RR sup i-1 ]~=~0 sup i-1 00 sup m-2i 11 sup i-1+n-m$ $C[RR sup i-1 ]~=~0 sup i-1 0 \*(st sup n-i$ .sp .25 .in 0i .ip "Step (3)" 10 $H[LR sup m/2 ]~=~0 sup m/2 1 sup n-(m/2)-1 0$ $C[LR sup m/2 ]~=~0 sup m/2 \*(st sup n-(m/2)-1 0$ .br $H[RR sup m/2 ]~=~0 sup m/2 1 sup n-(m/2)-2 01$ $C[RR sup m/2 ]~=~0 sup m/2 \*(st sup n-(m/2)-1 1$. .in 0 .sp .5 By condition (C2) and $p~=~1$, $10 sup n-1$ and $0 sup m-1 10 sup n-m$ are the only faults in $1 \*(st sup n-1$ and $\*(st sup m-1 1 \*(st sup n-m$ respectively. Thus $H[L]$, $H[R]$, $H[LR]$ and $H[RR]$ cannot be faulty. $H[LR sup i-1 ]$ and $H[RR sup i-1 ]$ would not be faulty for $i~=~3,~\(el,~(m/2)+1$ as these nodes have more than three 1's. As each $C[LR sup i-1 ] ~=~0 sup i-1 1 \*(st sup n-i$ has exactly 1 fault for $i~=~1,~\(el,~m/2$, these $LR sup i-1$-embeddings can be done with recursion. .pp By step (3), $C[RR sup m/2 ] ~=~0 sup m/2 \*(st sup n-(m/2)-1 1$ contains all the assigned hypercube nodes $H[R sup j ]$, $j~=~0,\(el,~m/2$, and possibly at most another faulty node, whereas $C[LR sup m/2 ]$ contains only faulty nodes (at least $(m/2)-1$ of them). The following lemmas (similar to Lemmas 2.11 and B.4) will show that the $RR sup m/2$- and $LR sup m/2$-embeddings are always possible as long as conditions (C1)-(C3) are satisfied. .lp \fBLemma 3.3: \fR It is always possible to perform the $RR sup m/2$-embedding. .lp \fBProof: \fR If $C[RR sup m/2 ]$ contains a fault (i.e., that fault with a 1 in dimension $n$), because of condition (C1), that fault must have at most one 1 in dimensions $(m/2)+1$ to $n-1$ and have Hamming distance $>=~n-(m/2)-2$ away from $H[RR sup m/2 ]$. Thus it can be ignored in the embedding (Theorem 2.2). .pp Rewriting the assigned node $H[R sup j ]$ as $0 sup m/2 0 sup (m/2)-j 1 sup j 1 sup n-m$, the Hamming distance between $H[R sup j ]$ and $H[RR sup m/2 ]~=~0 sup m/2 1 sup m/2 1 sup n-m-2 01$ is $(m/2)-j+1$ except when $n-m~=~1$ and $j~=~0$. Note that when $n-m~=~1$, the Hamming distance between $H[ epsilon ]$ and $H[RR sup m/2 ]$ is $n-(m/2)-2$, thus $H[ epsilon ]$ is too far to affect the embedding. Since the other nodes have unique Hamming distances from $H[RR sup m/2 ]$, there are $n-(m/2)-3$ of them with Hamming distance $<=~n-(m/2)-3 $ away from $H[RR sup m/2 ]$. Thus $RR sup m/2$-embedding within $C[RR sup m/2 ]$ is always possible by recursion. \*(sq .lp \fBLemma 3.4: \fR It is always possible to perform the $LR sup m/2$-embedding. .lp \fBProof: \fR Note that all faults in $C[LR sup m/2 ]$ having exactly one 1 in their labels are of Hamming distance $n-(m/2)-2$ from the $H[LR sup m/2 ] ~=~0 sup m/2 1 sup n-(m/2)-1 0$. Since at most two faults cannot be ignored (by property (P3) and Theorem 2.2), the $LR sup m/2$-embedding is possible. \*(sq .pp From the above lemmas, it follows that the embedding is possible with $H[ epsilon ]~=~S$ for all nonfaulty hypercube node $S$ having $m$ 0's where $m$ is even and $<=~n-1$. Hence $v(n,f)~>=~ left ( pile {n above 0} right ) + left ( pile {n above 2} right ) + \(el + left ( pile {n above 2\(lf(n-1)/2\(rf} right ) ~-~f$ where the $left ( pile {n above i} right )$'s are the binomial coefficients. When $n$ is odd, $v(n,f)~>=~ left ( pile {n-1 above 0} right ) + left ( pile {n-1 above 1} right ) + \(el + left ( pile {n-1 above n-1} right ) ~-~f$ $=~ 2 sup n-1 -f$. When $n$ is even, by property (P4), there are at least $n-4$ faults having an odd number of 0's. Hence $v(n,f)~>=~ left ( pile {n-1 above 0} right ) + left ( pile {n-1 above 1} right ) + \(el + left ( pile {n-1 above n-2} right ) ~-~(f-n+4)$ $>=~ 2 sup n-1 -f$ for $n~>=~5$. Thus no matter $n$ is even or odd, $v(n,f)~>=~ 2 sup n-1 -f ~>=~ 2 sup 2n-2-f -f$ (as $f~>=~n-1$). .pp Note that embedding is also possible with the root mapped to nonfaulty $S$ such that $m~<=~n-1$ and $m$ is odd. However, the embedding is quite tedious and handling these cases does not improve the lower bound on $v(n,f)$. Hence the embedding is not shown here. .sh 2 "A Bound on the Number of Faults" .pp In this section, we establish an upper bound on the least number of faulty nodes present in an $n$-cube which can make the embedding of an $(n-1)$-tree impossible. We allow the embedding to have unbounded dilation, $O(1)$ load and the freedom to choose any nonfaulty node as the root. However, the embedding should never use any faulty hypercube node or any of its $n$ edges. We find that there exists a set of $O(1/ sqrt n ) \(mu 2 sup n$ faulty nodes which can make such an embedding impossible. .pp We first consider the case where load = 1. For convenience, we consider the $n$-cube as a graph of $n+1$ layers where layer $i$ includes all nodes with exactly $i$ 1's in their labels. A node is \fIabove\fR (or \fIbelow\fR) layer $i$ if its label has less (or more) than $i$ 1's. .pp Assume $n$ is even and consider the case that layer $n/2$ is faulty. Then there are $left ( pile {n above n/2} right )$ faulty nodes. By Stirling's formula, this is $<=~ sqrt {2 over \(*pn} 2 sup n e sup 1/12n$ which is an $O(1/ sqrt n )$ fraction of $2 sup n$. Moreover, it is impossible to embed an $(n-1)$-tree into such an $n$-cube with unit load. It is because the nodes above layer $n/2$ are disconnected from those below and both groups have less than $2 sup n-1 -1$ nodes when $n~>=~4$. .pp The situation is similar when $n$ is odd. We can make layers $\(lcn/2\(rc$ and $\(lfn/2\(rf$ faulty. Then there are $left ( pile {n above \(lcn/2\(rc} right ) + left ( pile {n above \(lfn/2\(rf} right )$ $=~ left ( pile {n+1 above (n+1)/2} right )$ $<=~ sqrt {2 over \(*p(n+1)} 2 sup n+1 e sup 1/12(n+1)$ faults which is again an $O(1/ sqrt n )$ fraction of $2 sup n$. Also, the number of nodes above layer $\(lfn/2\(rf$ is less than $2 sup n-1 -1$ for $n~>=~3$ (and so is the number of nodes below layer $\(lcn/2\(rc$). Hence the embedding of an $(n-1)$-tree is impossible. .pp Thus, for $n~>=~3$, it is not always possible to embed with unit load, an $(n-1)$-tree into an $n$-cube having an $O(1/ sqrt n )$ fraction of faults even though we are free to choose any nonfaulty node as the root of the tree. .pp If the load $=~c$, we can make layers $l sub 1 ,\(el, l sub 2c$ faulty where $0~<~l sub 1 =~ left floor {2 sup n-1 -1} over c right floor$ and that between layers $l sub i-1 +1$ and $l sub i -1$ (inclusively) is $<~ left floor {2 sup n-1 -1} over c right floor$. (For convenience, we let $l sub 0 ~=~-1$.) Note that nodes between layers $l sub i-1 +1$ and $l sub i -1$ are nonfaulty. Thus the nonfaulty nodes of the $n$-cube are separated into $2c$ or $2c+1$ groups (depending on $l sub 2c ~=~n$ or not), each having $<~ left floor {2 sup n-1 -1} over c right floor$ nodes. Note that the group of nodes below layer $l sub 2c$ has $<=~ 2 sup n - left ( 2c\(mu left floor {2 sup n-1 -1} over c right floor right )$ $<=~ 2c~<~ left floor {2 sup n-1 -1} over c right floor$ nodes for large enough $n$. Hence an $(n-1)$-tree cannot be embedded (wholly or partly) within any group. Finally, the total number of nodes in all the faulty layers is at most $2c\(muO(1/ sqrt n )\(mu 2 sup n$ or $O(1/ sqrt n )\(mu 2 sup n$. Hence our claim follows. .bp .sh 1 "Recursive Embeddings" .pp In this section, we study an interesting relationship between our embedding strategies and the \fIrecursive embedding\fR mentioned in [WCM]. .lp \fBDefinition 4.1: \fR A \fIrecursive embedding\fR is one that maps the left and right subtrees of every internal node of the binary tree into disjoint subcubes. .pp It was shown in [WCM] that any recursive (variable root) embedding of an $(n-1)$-tree into an $n$-cube with unit dilation and load can tolerate no more than $2n-3$ faults in the worst case. Before we prove this result, let us have the following definitions. .lp \fBDefinition 4.2: \fR Let $a sub 1 \(el a sub n$ be the label of a hypercube node $A$. Then parity of $A$ is defined as $parity(A)~=~( sum from i=1 to n {a sub i} )~ mod ~2$. .pp In other words, $parity(A)~=~0$ if $A$ has even number of 1's in its label and $parity(A)~=~1$ otherwise. .lp \fBLemma 4.1: \fR For any tree node $T$, $parity(H[T])~=~parity(H[ epsilon ])$ if and only if $T$ is at an even level. .lp \fBProof: \fR It is easily proved by induction on $n$, the level number of $T$. Suppose the lemma is true for $n-1$. Then $parity(H[S])~=~parity(H[ epsilon ])$ if and only if $S$ is at an even level, where $S$ is the parent of $T$. Since the number of 1's in $H[T]$ must differ from that in $H[S]$ by one (dilation one embedding), $parity(H[T])~!=~parity(H[S])$. Moreover, $T$ is at even level if and only if $S$ is not. Hence $parity(H[T])~=~parity(H[ epsilon ])$ if and only if $T$ is at an even level. \*(sq .lp \fBLemma 4.2: \fR For any leaf nodes $S$ and $T$, $parity(H[S])~=~parity(H[T])$. .lp \fBProof: \fR It follows directly from Lemma 4.1 as $S$ and $T$ are on the same level. \*(sq .pp The following lemma from [WCM] gives an important property about recursive embedding. .lp \fBLemma 4.3:[WCM] \fR For all $n~>=~2$ and for every hypercube node $A$ in an $n$-cube, there exists a leaf, $T sub A$, of the $(n-1)$-tree, such that the Hamming distance between $A$ and $H[T sub A ]$ is at most 2 where $H$ is a recursive embedding. .lp \fBProof: \fR By definition, the recursive embedding cuts the $n$-cube into $2 sup n-2$ disjoint 2-cubes, each containing one leaf. Hence every hypercube node, lying in some 2-cube, is at Hamming distance at most two from the leaf in that 2-cube. \*(sq .pp The following theorem from [WCM] gives an upper bound on the least number of faults such that no recursive embedding is possible. .lp \fBTheorem 4.1:[WCM] \fR For $n~>=~3$, there exists a set of $2n-2$ faults such that no recursive embedding can avoid all the faults. .lp \fBProof: \fR Consider the set of $2n-2$ faults: { $0 sup i-1 1 0 sup n-i-1 0$, $0 sup i-1 1 0 sup n-i-1 1$ for $i~=~1,\(el,n-1$}. They isolate the subcube $0 sup n-1 \*(st$ from the rest of nonfaulty nodes. Hence $0 sup n-1 \*(st$ cannot contain part of the $(n-1)$-tree. As $n~>=~3$, it cannot contain the whole $(n-1)$-tree too. By Lemma 4.3, there must exist two leaves, $U$ and $V$, such that $H[U]$ is at Hamming distance exactly 2 from $0 sup n-1 0$ and so is $H[V]$ from $0 sup n-1 1$. Hence $parity(H[U])~=~parity(0 sup n-1 0)~=~0$ and $parity(H[V])$ = $parity(0 sup n-1 1)$ = 1 $!=~parity(H[V])$, thus contradicting Lemma 4.2. \*(sq .pp It is easy to see that our specified root embedding is basically a recursive embedding. The only violation is the occasional use of node borrowing. We shall show in Theorem 4.2 that node borrowing is necessary for the specified root embedding to tolerate $n-2$ faults. Moreover, there is only one case in which the technique is required. On the other hand, our variable root embedding does not require node borrowing at all (to be proved in Theorem 4.3) and therefore is a recursive embedding. Thus we have achieved their $2n-3$ bound asymptotically. .lp \fBTheorem 4.2: \fR For the specified root embedding problem, recursive embedding fails if and only if $n~>=~5$, $n$ is odd and $x~=~n-2$ where $x$ is the number of faulty neighbors of $H[ epsilon ]$. .lp \fBProof: \fR \fI(if)\fR The parity of $H[ epsilon ]$ is 0. For odd $n$, the parity of the leaves of an $(n-1)$-tree is 1 (by Lemma 4.1). By Lemma 4.3, $H[ epsilon ]$ must be at Hamming distance 1 from a leaf. However, among the $n$ neighbors of $H[ epsilon ]$, $n-2$ of them are faulty and the other 2 are $H[L]$ and $H[R]$ which are internal nodes for $n~>=~4$. Thus, recursive embedding is not possible. .lp \fI(Only if)\fR Referring to our embedding algorithm, excluding the recursive calls, node borrowing is only used when $n$ is odd and $x~=~n-2$. Thus, it is sufficient to prove that node borrowing is also not needed in any of the recursive calls. We shall prove this by induction on $n$. For the base cases where $n~<=~4$, Section 2.4 shows that node borrowing is not needed. For the induction step, there are 4 cases to be considered. .lp Case (1) $0~<=~p~<=~1$ .br We need to argue that the $LR sup i-1$-embedding for $i~=~1,\(el,\(lfm/2\(rf+1$ and the $RR sup \(lfm/2\(rf$-embedding will not require node borrowing. Basically, we try to prove that at each recursive step, not many faults can be neighbors of the specified root. .pp First, $C[L]$ contains only $p~<=~1$ faults. Second, at most 1 fault in $C[LR sup i-1 ]$ for $i~=~2,\(el,\(lfm/2\(rf$ is adjacent to $H[LR sup i-1 ]$ since the $H[LR sup i-1 ]$'s lie in $left {~~~ lpile { 0 \*(st sup m-1 0 sup n-m above 0 \*(st sup n-2 1 }~~~ lpile { if~n~>~m above if~n~=~m }$ while the faults in $0\*(st sup n-1$ lie in $left {~~~ lpile { 0 \*(st sup m-1 1 sup n-m above 0 \*(st sup n-2 0 }~~~ lpile { if~n~>~m above if~n~=~m }$. .pp For the $LR sup \(lfm/2\(rf$-embedding, we shall show that there are less than $n-\(lfm/2\(rf-3$ faults adjacent to $H[LR sup \(lfm/2\(rf ]~=~ left {~~~ lpile { 0 sup \(lcm/2\(rc 1 sup \(lfm/2\(rf 0 sup n-m-1 1 above 0 sup \(lcm/2\(rc 1 sup \(lfm/2\(rf-1 0 }~~~ lpile { if~n~>~m above if~n~=~m }~~~$ provided $n-\(lfm/2\(rf-1~>=~5$. Consider a fault $A$, which is adjacent to $H[LR sup \(lfm/2\(rf ]$. There are 2 cases. .br \(bu If $n-m~>=~2$, then $A$ must disagree with $H[LR sup \(lfm/2\(rf ]$ in at least $n-m-1~>=~1$ dimensions. (Note that $A$ lies in $0 sup \(lfm/2\(rf \*(st sup \(lcm/2\(rc 1 sup n-m$ by condition (B2)). Hence $A$ must agree with $H[LR sup \(lfm/2\(rf ]$ in any dimension from $\(lcm/2\(rc+1$ to $m$. In other words, $A$ has 1's in all these dimensions. Then, since at most one fault in $C[LR sup \(lfm/2\(rf ]$ = $left {~~~ lpile { 0 sup \(lfm/2\(rf \*(st sup n-\(lfm/2\(rf-1 1 above 0 sup \(lfm/2\(rf \*(st sup n-\(lfm/2\(rf-1 0 }~~~ lpile { if~n~>~m above if~n~=~m }~~~$ can have a 1 in any of these dimensions (refer to the proof in Lemma B.4), no other faults can be adjacent to $H[LR sup \(lfm/2\(rf ]$. .br \(bu If $n-m~<=~1$, $A$ can disagree with $H[LR sup \(lfm/2\(rf ]$ in at most one dimension from $\(lcm/2\(rc+1$ to $m$. By similar argument as above, no other faults can disagree with $H[LR sup \(lfm/2\(rf ]$ in at most one of these dimensions unless $\(lfm/2\(rf-1~<=~2$ but this implies $n-\(lfm/2\(rf-1~<=~4$. .pp Consider the $RR sup \(lfm/2\(rf$-embedding. Referring to Lemma 2.11, $C[RR sup \(lfm/2\(rf ]$ contains the assigned nodes $H[R sup j ]$ for $j~=~1,\(el,\(lfm/2\(rf$ and if $n~>~m$, $H[ epsilon ]$ also. However, it does not contain any fault by condition (B2). Since the Hamming distance between $H[R sup j ]$ (except $H[ epsilon ]$ and $H[R]$ when $n~=~m$ and $m$ is even) and $H[RR sup \(lfm/2\(rf ]$ is $\(lfm/2\(rf-j+1$, only $H[R sup \(lfm/2\(rf ]$ is adjacent to $H[RR sup \(lfm/2\(rf ]$. Furthermore, $H[ epsilon ]$ and $H[R]$, when $n~=~m$ and $m$ is even, are either outside $C[RR sup \(lfm/2\(rf ]$ or not adjacent to $H[RR sup \(lfm/2\(rf ]$ (refer to Lemma 2.11). .lp Case (2) $p~=~2$ .br $C[L]$ and $C[R]$ contains $2$ and $n-3$ faults/assigned nodes respectively. Consider the $n-4$ faults (excluding the assigned node) in $C[R]$. We shall show that at most 2 of them can be adjacent to $H[R]$ if we have chosen $H[R]$ carefully. .lp Suppose $A$ is a fault adjacent to $H[R]$ ( $=~0 sup j-1 1 0 sup n-j$, say). Then it must have 1's in exactly two dimensions and one of them must be dimension $j$. However, if we have chosen $j$ (i.e., $H[R]$) carefully such that $0 sup j-1 10 sup n-j$ is nonfaulty and $\*(st sup j-1 1\*(st sup n-j$ contains $=~2$, the node mentioned in condition (B4) becomes $0 sup \(lcm/2\(rc 1 sup \(lfm/2\(rf 0 sup n-m-1 1$ which is never faulty by condition (B2). So nothing has to be done. .lp For $n-m~<=~1$, if the node mentioned in condition (B4) is faulty, we show that dimensions $\(lcm/2\(rc$ and $\(lcm/2\(rc+1$ can be swapped so that the node becomes nonfaulty and at the same time, conditions (B1)-(B3) are preserved. .pp We claim that both $0 sup \(lcm/2\(rc-1 1 \*(st sup \(lfm/2\(rf+n-m$ and $0 sup \(lcm/2\(rc 1 \*(st sup \(lfm/2\(rf+n-m-1$ contain exactly 1 fault. Since the node mentioned in condition (B4) is faulty, $0 sup \(lcm/2\(rc 1 \*(st sup \(lfm/2\(rf+n-m-1$ contains $r~>=~1$ faults. On the other hand, $0 sup \(lcm/2\(rc-1 1 \*(st sup \(lfm/2\(rf+n-m$ contains $<=1$ faults. Otherwise, the total number of faults in $C[ epsilon ]$ is at least $2(\(lcm/2\(rc-1)+p+r$ (by condition (B3)) and hence at least $n-3+p+r$ (as $n-m~<=1~$). If $p~=~1$, $p+r~>=~2$. If $p~=~0$, then by Lemma 2.1b, $0 sup \(lcm/2\(rc 1 \*(st sup \(lfm/2\(rf+n-m-1$ must also contain the fault $0 sup \(lcm/2\(rc 1 0 sup \(lfm/2\(rf+n-m-1$. Hence $r~>=~2$. Consequently, no matter whether $p$ is 0 or 1, the total number of faults in $C[ epsilon ]$ is greater than $n-2$ which is impossible. Thus by condition (B3), we can conclude that both $0 sup \(lcm/2\(rc-1 1 \*(st sup \(lfm/2\(rf+n-m$ and $0 sup \(lcm/2\(rc 1 \*(st sup \(lfm/2\(rf+n-m-1$ contain exactly 1 fault. .pp It follows from the claim that conditions (B1)-(B3) are preserved even if we swap dimensions $\(lcm/2\(rc$ and $\(lcm/2\(rc+1$. Moreover, the fault in the former subcube, $0 sup \(lcm/2\(rc-1 1\*(st sup \(lfm/2\(rf+n-m$, must be $left {~~~ lpile { 0 sup \(lcm/2\(rc-1 1 0 sup \(lfm/2\(rf+n-m-1 1 above 0 sup \(lcm/2\(rc-1 1 0 sup \(lfm/2\(rf+n-m-1 0 }~~~ lpile { if~n-m~=~1 above if~n-m~=~0 }~~~$ before the dimensions are swapped because the node $left {~~ lpile { 0 sup \(lcm/2\(rc 1 sup \(lfm/2\(rf 0 sup n-m-1 1 above 0 sup \(lcm/2\(rc 1 sup \(lfm/2\(rf-1 0 }~~ lpile { if~n~>~m above if~n~=~m }~~$ is faulty and $p~<=~1$. By exchanging dimensions $\(lcm/2\(rc$ and $\(lcm/2\(rc+1$, it is changed to $left {~~~ lpile { 0 sup \(lcm/2\(rc 1 0 sup \(lfm/2\(rf+n-m-2 1 above 0 sup \(lcm/2\(rc 1 0 sup \(lfm/2\(rf+n-m-2 0 }~~~ lpile { if~n-m~=~1 above if~n-m~=~0 }~~~$. Also, the fault in latter subcube, $0 sup \(lcm/2\(rc 1\*(st sup \(lfm/2\(rf+n-m-1$, is changed to $left {~~~ lpile { 0 sup \(lcm/2\(rc-1 1 0 1 sup \(lfm/2\(rf+n-m-2 1 above 0 sup \(lcm/2\(rc-1 1 0 1 sup \(lfm/2\(rf+n-m-2 0 }~~~ lpile { if~n-m~=~1 above if~n-m~=~0 }~~~$. \*(sq .fo ''- B% -'' .bp .nr % 1 .uh "Appendix B" .pp This section contains the lemmas which show the feasibility of the $LR sup i-1$-embeddings for $i~=~1,\(el,~\(lfm/2\(rf+1$ and the $RR sup \(lfm/2\(rf$-embedding. .pp Before we study these embeddings, let us consider some properties of the faults in $0\*(st sup n-1$. We shall show that there exists a subset $E$ of the faults in $0\*(st sup n-1$ such that for all $k$ where $2~<=~k~<=~m$, $0\*(st sup k-2 1\*(st sup m-k 1 sup n-m$ contains at most one fault in $E$, i.e., at most one fault in $E$ has a 1 in dimension $k$. Hence each $C[LR sup i ]$ = $0 sup i-1 1\*(st sup n-i$ contains at most one fault in $E$, i.e., at least $e-1$ faults are not in $C[LR sup i ]$. Lemma B.1 below shows that $e$, the size of $E$, is not too small. This ensures that the remaining faults in $0\*(st sup n-1$ can be separated (by splitting the $C[R sup i ]$'s on suitable dimensions) so that the $C[LR sup i ]$'s will not have too many faults. In the case where $n~>~m$, Lemma B.2 shows that $E$ can even include all the faults in $0 \*(st sup n-1$. For instance, in Example 2.2, we can have $E$ = {$beta sub 1 ,~ beta sub 2 ,~ beta sub 3 ,~ beta sub 4$} while in Example 2.3, we can have $E$ = {$beta sub 1 ,~ beta sub 2 ,~ beta sub 3$} or {$beta sub 3 ,~ beta sub 4$}. .lp \fBLemma B.1: \fR .ip (a) when $p~=~0$, there exists a set of faults, $E$, with cardinality $e~>=~3$; .ip (b) when $p~=~1$, there exists a set of faults, $E$, with cardinality $e~>=~2$. .lp \fBProof: \fR .br (a) When $p~=~0$, the number of faulty neighbors of $H[ epsilon ]$, $x$, is $>=~ \(lc log (n-1) \(rc ~>=~ 3$ (by Lemma 2.2b and $n~>=~6$). Also, these faults satisfy the conditions for $E$. Therefore, $e~>=~x~>=~3$. .lp (b) When $p~=~1$, .lp \(bu if there is no faulty neighbor of $H[ epsilon ]$ on dimensions 2 to $m$: .br Then $0 \*(st sup k-2 1 \*(st sup m-k 1 sup n-m$ must contain at most 1 fault in $0 \*(st sup n-1$ for all $2 ~<=~ k ~<=~ m$. Therefore, the set of all faults in $0 \*(st sup n-1$ satisfies the conditions of $E$. Hence $e~=~n-2-p~>=~3$, as $n~>=~6$. .lp \(bu if there is at least one neighboring fault, $0 sup k-1 1 0 sup n-k$ where $2~<=~k~<=~m$: .br Then the required set can be formed by having the fault $00 sup k-2 1 0 sup n-k$ together with one more fault which does not belong to the subcube $0 \*(st sup k-2 1 \*(st sup n-k$. Then $e~>=~2$. Note that we can always find such an additional fault; otherwise, the subcube $0 \*(st sup k-2 1 \*(st sup n-k$ would contain all the faults in $0 \*(st sup n-1$ and dimension $k$ would have been moved to one of the rightmost $n-m$ dimensions to satisfy condition (B2). \*(sq .lp \fBLemma B.2: \fR If $n-m~>~0$, then .ip (a) the set of all faults in $0 \*(st sup n-1$ satisfies the condition of $E$ and .ip (b) $p~=~1$ .lp \fBProof: \fR .br (a) When $n-m~>~0$, there does not exist a $k$ such that $2~<=~k~<=~m$ and $0 sup k-1 1 0 sup n-k$ is faulty (by condition (B2)). Similar to the proof for Lemma B.1b where there is no faulty neighbors of $H[ epsilon ]$, the set of all faults in $0\*(st sup n-1$ satisfies the condition of $E$. .br (b) If all subcubes $0\*(st sup k-2 1 \*(st sup n-k$ contains 0 faults, all the faults would be identical to $0 sup m 1 sup n-m$. Hence there must be some of them containing 1 fault. Then $p~=~1$. \*(sq .lp \fBLemma B.3: \fR It is always possible to perform the $LR sup i-1$-embedding for $i~=~1~,\(el,~\(lfm/2\(rf$. .lp \fBProof: \fR First, the $L$-embedding can always be performed since $C[L]$ contains only $p~<=~1$ faults and zero assigned nodes above level 1. .lp Now, consider the $LR sup i-1$-embedding for $i~=~2,~\(el,~\(lfm/2\(rf$. The subcubes $0 sup j-1 1 \*(st sup n-j$ where $2~<=~j~<=~i$ can, in total, contain at most $i-1$ faults of the set $E$ and all faults in $0 \*(st sup n-1$ not in $E$. In other words, they contain at most $n-2-(p+e)+(i-1)$ faults where $e$ is the size of $E$ as defined in Lemma B.1. From condition (B3), $C[LR sup j-1 ]~=~0 sup j-1 1\*(st sup n-j$ contains at least as many faults as in $C[LR sup i-1 ]~=~0 sup i-1 1\*(st sup n-i$ for $2~<=~j~<=~i$. Therefore, the number of faults in $C[LR sup i-1 ]$ is at most $left floor n-2-(p+e)+(i-1) over i-1 right floor$ which is $<=~ n-i-2$ provided $n-2-(p+e)+(i-1)~-~(n-i-2)(i-1)$ $<=~i-2$ or $(i-2)(n-3-i)~+(e+p)-3~>=~0$. This condition is always satisfied as $p+e~>=~3$ (Lemma B.1) and $(i-2)(n-3-i)~>=~0$ ($n~>=~6$ and $2~<=~i~<=~\(lfm/2\(rf$). Moreover, $C[LR sup i-1 ]$ does not contain any assigned nodes above level $i$. Hence the $LR sup i-1$-embedding can always be done. \*(sq .lp \fBLemma B.4: \fR It is always possible to perform the $LR sup \(lfm/2\(rf$-embedding unless $n$ is odd and $x~=~n-2$. .lp \fBProof: \fR Consider $C[LR sup \(lfm/2\(rf ]~=~ 0 sup \(lfm/2\(rf \*(st sup n-\(lfm/2\(rf-1 a bar sub n$ where $a sub n ~=~ left {~~~ lpile { 0 above 1 }~~~ lpile { n~>~m above n~=~m }~~$. .lp It may contain some faults but no assigned nodes above level $\(lfm/2\(rf+1$ except $H[ epsilon ]$ when $n~=~m$. Now, we claim that at most one fault in $C[LR sup \(lfm/2\(rf ]$ has a 1 in dimensions $\(lfm/2\(rf+1$ to $min (m,n-1)$, i.e., for $i~=~1,\(el, min (\(lcm/2\(rc,n-\(lfm/2\(rf-1)$, the subcube $0 sup \(lfm/2\(rf \*(st sup i-1 1 \*(st sup n-\(lfm/2\(rf-1-i a bar sub n$ contains at most 1 fault. This is obvious when $n~>~m$ (Lemma B.2a). Consider $n~=~m$. If for some $i$, the subcube $0 sup \(lfm/2\(rf \*(st sup i-1 1 \*(st sup n-\(lfm/2\(rf-1-i a bar sub n$ contains $>=~2$ faults, then by condition (B3), the total number of faults in the $n$-cube is $>=~2\(lfm/2\(rf$ $=~2\(lfn/2\(rf$ $>=~n-1$ which is impossible. Hence our claim follows. .lp Next, we consider the number of faults with Hamming distance $<=~n-\(lfm/2\(rf-3$ from $H[LR sup \(lfm/2\(rf ]$ = $left {~~~ lpile { 0 sup \(lcm/2\(rc 1 sup \(lfm/2\(rf 0 sup n-m-1 1 above 0 sup \(lcm/2\(rc 1 sup \(lfm/2\(rf-1 0 }~~~ lpile { if~n~>~m above if~n~=~m }~~$. .lp Case (i) even $m$ .br A fault in $C[LR sup \(lfm/2\(rf ]$ is at Hamming distance $<=~n-\(lfm/2\(rf-3$ from $H[LR sup \(lfm/2\(rf ]$ if and only if it agrees with $H[LR sup \(lfm/2\(rf ]$ in at least 2 dimensions from dimensions $\(lfm/2\(rf+1$ to $min (m,n-1)$. (They must disagree in dimensions $min (m,n-1)+1$ to $n-1$ by condition (B2).) In other words, it must have 1 in at least 2 of these dimensions. Hence there are $<=~left floor {min (m,n-1)-(m/2)} over 2 right floor$ $=~left floor {min ((m/2),n-(m/2)-1)} over 2 right floor$ such faults. Note that this is $<=~n-\(lfm/2\(rf-3$ provided $n+(n-m)~>=~8$ or $n+3(n-m)~>=~10$. .br \(bu When $n-m~>=~2$, the first inequality holds (as $n~>=~6$). .br \(bu When $n-m~=~1$, $n~>=~7$ (so that $m$ is even). Hence the second inequality is satisfied. .br \(bu When $n-m~=~0$, the first inequality is true if $n~>=~8$. It is also impossible to have $n~=~7$ (for $m$ is even). If $n~=~6$, $left floor {min ((m/2),n-(m/2)-1)} over 2 right floor ~=~1$. The only fault here is $000110~=~0 sup \(lcm/2\(rc 1 sup \(lfm/2\(rf-1 0$ which is impossible by condition (B4). Hence the $LR sup \(lfm/2\(rf$-embedding can be done recursively. .lp Case (ii) odd $m$ .br If $C[LR sup \(lfm/2\(rf ]$ = $0 sup \(lfm/2\(rf \*(st sup n-\(lfm/2\(rf-1 a bar sub n$ contains at least 1 fault, then so does $0 sup \(lfm/2\(rf 1 \*(st sup n-\(lfm/2\(rf-2 a bar sub n$ (condition (B3)). Consider a fault $A$ in this subcube (there can be only one fault in this subcube). There are two cases to be considered. .lp (a) If fault $A$ is at Hamming distance $<=~n-\(lfm/2\(rf-3$ from $H[LR sup \(lfm/2\(rf ]$, it has a 1 in at least 2 dimensions from $\(lfm/2\(rf+2$ to $min (m,n-1)$. Hence the total number of faults in $C[LR sup \(lfm/2\(rf ]$ that can affect the embedding is $<=~1+ min (m,n-1)-\(lfm/2\(rf-3$ or $<=~min (\(lcm/2\(rc-2,n-\(lfm/2\(rf-3)$ or $<=~n-\(lfm/2\(rf-3$. .lp (b) If fault $A$ does not affect the embedding, then it has at most one 1 in dimensions from $\(lfm/2\(rf+2$ to $min (m,n-1)$. .br \(bu When $n-m~>=~1$, there should be at most $n-\(lfm/2\(rf-3$ faults that can affect the embedding. Otherwise the total number of faults in $C[ epsilon ]$ (including the fault A which cannot affect the embedding) would be $>=~(n-\(lfm/2\(rf-2)+(p+\(lfm/2\(rf)$ $>=~n-1$ (as $p~=~1$ by Lemma B.2b). .br \(bu When $n-m~=~0$, it is impossible to have $n-\(lfm/2\(rf-2$ faults. Otherwise, the $n-2$ faults must be $00 sup i-2 1 0 sup n-i $ for $i~=~2,\(el,n-1$. In other words, they are all neighbors of $H[ epsilon ]~=~0 sup n$, i.e., $x~=~n-2$. Since $n~=~m$ and $m$ is odd, $n$ is odd. The case where $n$ is odd and $x~=~n-2$ is excluded from consideration here. \*(sq