Microsoft Word - Proofreading-Comp040910-final.doc 63-75 SQU Journal For Science, 10 (2005) © 2005 Sultan Qaboos University 63 The Conditional Fault-Diameter of the K-ary n-Cube Khaled Day and Abderezak Touzene Department of Computer Science, College of Science, Sultan Qaboos University, P.O. Box 36, Al-Khod 123, Sultanate of Oman, Email: kday@squ.edu.om, touzene@squ.edu.om. k-ary n-cubeالقطر المختل المشروط لشبكات خالد داي وعبدالرزاق توزان المختلة مع افتراض توزيعـات مشـروطة k-ary n-Cubeنحصل في هذا البحث على قطر شبكات : خالصة . لنقاط الخلل حيث أننا نفترض أن لكل نقطة سليمة في الشبكة ما ال يقل عن نقطة مجاورة سـليمة مـن الخلـل وتحت الشرط المذكور لتوزيع نقاط الخلل ، ، 2n التي يساوي مقدار الربط فيها k-ary n-Cube برهن أن شبكةن -kكما نستنتج أن القطر المختل المشروط لشـبكات .خلل بدون قطع االتصال بينها نقطة 4n-3 تتحمليمكن أن ary n-Cubeمن هذه النتيجة أنه إذا وجد ما ال يزيد نستخلص. يساوي القطر في غياب أي خلل زائداً وحدتان وإذا كان لكل نقطة سليمة ماال يقل عن نقطة مجاورة سليمة ، k-ary n-Cube نقطة خلل في شبكة الn4-3عن تبين في هذا البحـث . فالبد أن يكون هنالك طريق موصل خال من األعطال في الشبكة بين كل نقطتين سليمتين إلى مجموعـة k-ary n-Cube بهذه النتيجة تنضم شبكة.وصل الخالي من األعطالكيفية بناء هذا الطريق الم والتي يساوي القطـر المختـل ) star-graph وشبكات hypercubeالتي تحتوي على شبكات (شبكات التوصيل .المشروط فيها القطر السليم زائداً وحدتان ABSTRACT: We obtain the conditional fault diameter of the k-ary n-cube interconnection network. It has been previously shown that under the condition of forbidden faulty sets (i.e. assuming each non-faulty node has at least one non-faulty neighbor), the k-ary n-cube, whose connectivity is 2n, can tolerate up to 4n-3 faulty nodes without becoming disconnected. We extend this result by showing that the conditional fault-diameter of the k-ary n-cube is equal to the fault-free diameter plus two. This means that if there are at most 4n-3 faulty nodes in the k-ary n-cube and if every non-faulty node has at least one non-faulty neighbor, then there exists a fault-free path of length at most the diameter plus two between any two non faulty nodes. We also show how to construct these fault-free paths. With this result the k-ary n-cube joins a group of interconnection networks (including the hypercube and the star-graph) whose conditional fault diameter has been shown to be only two units over the fault-free diameter. KEYWORDS: Fault-tolerance, multiprocessor systems, interconnection architectures, k- ary n-cube, torus. KHALED DAY and ABDEREZAK TOUZENE 64 1. Introduction he node connectivity and the fault diameter have been used as measures of the fault-tolerance of interconnection networks. These measures however do not reflect the real resilience of these networks. It is true that when the number of faulty nodes is equal to the connectivity the network may become disconnected. However, this is very unlikely to happen since only very special fault distributions of these faults cause disconnection. For instance, in the k-ary n-cube, the node- connectivity is 2n and 2n faulty nodes may cause disconnection. But the network becomes disconnected only when all the 2n faults are adjacent to the same node which is very improbable. In an attempt to better quantify the fault resilience of a network, the concept of forbidden faulty sets has been introduced by Esfahanian (1989). The idea is to assume that each node has at least one non-faulty neighbor. Under this forbidden faulty set condition, the number of tolerable faulty nodes is significantly larger with a slight increase in the fault diameter. Esfahanian (1989) has proven that for the binary n-cube, whose connectivity is n, 2n-3 nodes can fail (under the forbidden faulty set condition) without disconnecting the network. Latifi (1993) has then showed that the corresponding conditional fault diameter increases only by 2 over the fault-free diameter. In Rouskov et al. (1996) similar results for the star graph network have been established. Latifi et al. (1994) have generalized this idea by assuming that each node has at least k non-faulty neighbors. Similar results for the m-ary generalized n-cube network have also been obtained in Wu (1998). It has been previously shown (Day, 2004) that for k ≥ 4 and n ≥ 2, the k-ary n-cube, whose connectivity is 2n, can tolerate up to 4n-3 faulty nodes without becoming disconnected. The corresponding conditional node connectivity is therefore 4n-2. The result for the remaining small values of k and n has also been obtained in Day (2004). We extend these results in this paper by showing that the conditional fault-diameter of the k-ary n-cube is equal to / 2 2n k⎢ ⎥⎣ ⎦ + . We therefore establish that the k-ary n-cube, like the hypercube and the star-graph, has conditional fault diameter equal to two plus the fault-free diameter. This paper is organized as follows: section 2 presents some notations; section 3 obtains some preliminary results useful for the derivation of the conditional fault diameter in section 4. Section 5 concludes the paper. 2. Notations The k-ary n-cube knQ has N = k n nodes each of the form X = x n-1 x n-2 ...x 0 , 0 ≤ xi< k, for 0≤i 0, there is a path of length l+k-2wi (h paths). In preparation for the proof of the conditional fault-diameter of the k-ary n-cube given in the next section, we present the corresponding result for the special case of the k-ary 2-cube (also called the k-torus). The k-torus is a wrap-around mesh which consists of k rows and k columns. Each row and each column consists of a cycle of k nodes. There are four node-disjoint paths connecting any two KHALED DAY and ABDEREZAK TOUZENE 66 nodes of the k-torus. The connectivity of the k-torus is therefore equal to 4. Any two nodes on the same cycle (row or column) are connected by two paths along the cycle. One is called the shortest path on the cycle and the other is called the longest path. We show that under the FFSC, the k-torus, whose connectivity is 4, can tolerate up to 5 faulty nodes without becoming disconnected. The conditional node connectivity of the k-torus is therefore 6. We also show that the conditional fault- diameter of the k-torus is equal to its fault-free diameter plus two. The proof of the following theorem consists of a lengthy manual construction of fault-free paths between any two non faulty nodes of the k-torus considering all possible relative locations of the source and destination nodes and those of the 5 faulty nodes. For brevity, we omit this lengthy construction here. Interested readers can find it in Touzene and Day (2005). Theorem 3. The conditional fault diameter of the k-torus under the FFSC is 2 / 2 2k⎢ ⎥⎣ ⎦ + . The next result states that it is always possible to construct between any two non-faulty nodes of k nQ a fault-free path of length at most the diameter if the number of faults does not exceed two. This result will be used in the next section to prove the conditional fault diameter of knQ . Lemma 1. In knQ , if k ≥ 4, n ≥ 2 and if there are two or less faulty nodes, then there exists between any two non-faulty nodes at least one fault-free path of length at most / 2n k⎢ ⎥⎣ ⎦ . Proof. Let X and Y be any two distinct non-faulty nodes in knQ . By Theorem 2, there exist between X and Y in knQ a first set of h = dH (X,Y) paths each of length dL (X,Y) (which is at most / 2h k⎢ ⎥⎣ ⎦ ) and a second set of 2n-2h paths each of length d L (X,Y)+2 (which is at most / 2 2h k⎢ ⎥⎣ ⎦ + ). Hence we have in total 2n-h paths between X and Y in knQ each of length at most / 2 2h k⎢ ⎥⎣ ⎦ + . We distinguish the following cases: • If h = 1 then 2n-h = 2n-1 ≥ 3, and / 2 2 / 2 2 / 2h k k n k⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎣ ⎦ ⎣ ⎦ ⎣ ⎦+ = + ≤ (since n≥2 and k≥4). Hence we have at least 3 paths each of length at most / 2n k⎢ ⎥⎣ ⎦ and at least one of these paths must be fault-free. • If h = 2 and n = 2, the result is derived from the proof of the fault-diameter of the 2-ary n-cube (k-torus) available in Touzene and Day (2005). • If h =2 and n ≥ 3 then 2n-h = 2n-2 ≥ 4 and / 2 2 2 / 2 2 / 2h k k n k⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎣ ⎦ ⎣ ⎦ ⎣ ⎦+ = + ≤ (since n≥3 and k≥4). Hence we have at least 4 paths each of length at most / 2n k⎢ ⎥⎣ ⎦ , one of which must be fault-free. • If h ≥ 3 then at least one of the first set of h paths each of length at most / 2 / 2h k n k⎢ ⎥ ⎢ ⎥⎣ ⎦ ⎣ ⎦≤ is fault-free. 4. The Conditional Fault Diameter of the k-Ary n-Cube The following result establishes a lower bound on the conditional fault-diameter of knQ . Lemma 2. CFD ( knQ ) ≥ / 2 2n k⎢ ⎥⎣ ⎦ + , for k ≥ 4, n ≥ 2. Proof. Let X and Y be two nodes in knQ at the maximum distance equal to the diameter / 2n k⎢ ⎥⎣ ⎦ . Let Z be a neighbor of Y and let T be a neighbor of Z other than Y (see Figure 1). Assume that all 2n-2 neighbors of Z other than Y and T are faulty and that all 2n-1 neighbors of T other than Z are faulty. Notice that the former set of 2n-2 faults and the latter set of 2n -1 faults must be disjoint since k ≥ 4 CONDITIONAL FAULT-DIAMETER OF K-ARY N CUBE 67 (otherwise, if F were a faulty node appearing in both sets then Z F T would form a cycle of length 3 which is impossible for k ≥ 4). Assume there are no other faults. The total number of faults is therefore 4n-3. A path from T to X must first go through Z then through Y then from Y to X in at least / 2n k⎢ ⎥⎣ ⎦ moves and, hence, will be of length of at least / 2 2n k⎢ ⎥⎣ ⎦ + . Therefore, the conditional fault diameter satisfies: CFD ( knQ ) ≥ / 2 2n k +⎢ ⎥⎣ ⎦ . Now we establish an upper bound on the conditional fault-diameter of knQ . Lemma 3. CFD ( knQ ) ≤ / 2 2n k +⎢ ⎥⎣ ⎦ , for k ≥ 4, n ≥ 2. Proof . We proceed by induction on n. The induction basis (n = 2) is given by Theorem 3. Now we prove the result for n ≥ 3 assuming it is true for smaller n values. Consider two arbitrary non-faulty nodes X = x n-1 x n-2 ...x 0 and Y = y n-1 y n-2 ...y 0 in knQ . Assume the number of faulty nodes is at most 4n-3 and that the FFSC is satisfied. Our aim is to show that it is always possible to find a fault-free path between X and Y of length at most / 2 2n k⎢ ⎥⎣ ⎦ + . We distinguish the following cases: Case 1. there exists m, 0 ≤ m < n, such that x m = y m = i (assume without loss of generality m = n-1), then both nodes X and Y belong to the sub-graph ,1 k i nQ − . Case 1.1. ,1 k i nQ − has at most 4(n-1)-3 = 4n-7 faults. By induction hypothesis there must exist a fault- free path from X to Y in ,1 k i nQ − of length at most [ ] [ ]/ 2 / 2( 1) 2 2k kn n− + ≤ + . Case 1.2. ,1 k i nQ − has more than 4n-7 faults. This means that there are at most 3 faults outside , 1 k i nQ − . Case 1.2.1. each of X and Y has all its 2n-2 neighbors inside ,1 k i nQ − faulty. There must exist at most one faulty node outside ,1 k i nQ − . Therefore either , 1 1 k i nQ − − or , 1 1 k i nQ + − is fault- free (notice i-1 and i +1 are modulo k). Let X i-1 (respectively X i+1) denote the neighbor of X in , 11 k i nQ − − (respectively , 11 k i nQ + − ). Similarly for Y i-1 and Y i+1 (see Figure 2). Since either , 11 k i nQ − − or , 1 1 k i nQ + − is fault-free, at least one of the two paths: X → X i-1 || * 1, 1 − − ik nQ π (X i-1, Y i-1) || Y i-1 → Y, or X → Xi+1 || * 1, 1 + − ik nQ π (X i+1, Y i+1) || Yi+1 → Y YX Z T 2n-2 faulty neighbors of Z 2n-1 faulty neighbors of T X and Y at distance / 2n k⎢ ⎥⎣ ⎦ Figure 1. / 2 2n k⎢ ⎥⎣ ⎦ + is a lower bound of CFD ( k nQ ). KHALED DAY and ABDEREZAK TOUZENE 68 is fault-free and is of length at most ( 1) / 2 2n k⎢ ⎥⎣ ⎦− + (since it is contained in a fault-free 1 k nQ − sub- graph except for two edges). The symbol || is used to denote path concatenation. Case 1.2.2. X or Y has a non-faulty neighbor inside ,1 k i nQ − . X Y X i-1 Y i-1 X i+1 Y i+1 1, 1 − − ik nQ ik nQ , 1− 1, 1 + − ik nQ Figure 2. Path construction for Case 1.2.1. Figure 3. Path construction for Case 1.2.2.1. X Y X i-1 Y i-1 1, 1 − − ik nQ ik nQ , 1− X’X’ i-1 X Y X i-1 Y i-1 1, 1 − − ik nQ ik nQ , 1− Y’Y’ i-1 Figure 4. Path construction for Case 1.2.2.3.1. CONDITIONAL FAULT-DIAMETER OF K-ARY N CUBE 69 Assume it is X which has a non-faulty neighbor X’ inside ,1 k i nQ − (case of Y is similar). Since there are at most three faulty nodes outside ,1 k i nQ − , either , 1 1 k i nQ − − or , 1 1 k i nQ + − has at most one faulty node. Assume , 11 k i nQ − − has at most one faulty node (the other case is similar). Case 1.2.2.1. X i-1 is faulty (hence X i-1 is the only faulty node in , 11 k i nQ − − ). Let X’ i-1 be the neighbor of X’ located in , 11 k i nQ − − (see Figure 3). By Lemma 1, there exists at least one fault-free path π (X’ i-1,Yi-1) of length at most ( 1) / 2n k⎢ ⎥⎣ ⎦− between X’ i-1 and Y i-1 in , 11 k i nQ − − . We have, therefore, a fault-free path: X → X’ → X’ i-1 || π (X’ i-1,Yi-1) || Yi-1 → Y of length at most ( 1) / 2 3n k⎢ ⎥⎣ ⎦− + which is less than or equal to / 2 2n k⎢ ⎥⎣ ⎦ + since k ≥ 4. Case 1.2.2.2. Xi-1 is non-faulty and Yi-1 is non-faulty. Figure 5. Path construction for Case 1.2.2.3.2. X Y X i+1 Y i+1 ik nQ , 1− 1, 1 + − ik nQ X’ X’ i+1 X” X” i+1 Figure 6. Path construction for Case 2. X Y X j Y i X ’ X ’ j Y ’Y ’ i ΠX ΠY X j+1 Y j+1 X ’ j+1 Y ’ j+1 Y j-1 X j-1 jk nQ , 1− 1, 1 + − jk nQ ik nQ , 1− KHALED DAY and ABDEREZAK TOUZENE 70 Since there is at most one fault in 1, 1 − − ik nQ , Lemma 1 gives a path π ( X i-1,Y i-1) of length at most ( 1) / 2n k⎢ ⎥⎣ ⎦− in 1, 1 − − ik nQ yielding the path: X → X i-1 ||π ( X i-1,Y i-1) || Y i-1 → Y of length at most ( 1) / 2 2 / 2n k n k⎢ ⎥ ⎢ ⎥⎣ ⎦ ⎣ ⎦− + ≤ (since k ≥ 4). Case 1.2.2.3. Xi-1 non-faulty and Yi-1 faulty (the only fault in 1, 1 − − ik nQ ). Case 1.2.2.3.1. Y has a non faulty neighbor Y’ in iknQ , 1− . Let Y’ i-1 be the neighbor of Y’ located in 1, 1 − − ik nQ (Figure 4). By Lemma 1, there exists at least one fault-free path π (X i-1,Y’ i-1) of length at most ( 1) / 2n k⎢ ⎥⎣ ⎦− from X i-1 to Y’ i-1 in 1, 1 − − ik nQ . Therefore the path: X → X i-1 ||π (X i-1,Y’ i-1) || Y’ i-1 → Y i-1 → Y is fault-free and is of length at most ( 1) / 2 3n k⎢ ⎥⎣ ⎦− + ≤ / 2 2n k⎢ ⎥⎣ ⎦ + (since k ≥ 4). Case 1.2.2.3.2. all neighbors of Y in iknQ , 1− are faulty. In this case Y i+1 must be non-faulty (by the FFSC). We know that 1, 1 + − ik nQ has at most 2 faulty nodes. If it has only one faulty node then it is possible to enter 1, 1 + − ik nQ from X going directly from X to X i+1 or from X to X’ then to X’ i+1 requiring in both cases at most two moves (see Figure 5). We can then use Lemma 1 in 1, 1 + − ik nQ to obtain a fault-free path of length at most ( 1) / 2n k− ⎢ ⎥⎣ ⎦ from X i+1 or from X’ i+1 to Y i+1 and then make a final move from Y i+1 to Y. Hence we have a fault-free path from X to Y of length at most ( 1) / 2 3n k− +⎢ ⎥⎣ ⎦ which is at most / 2 2n k +⎢ ⎥⎣ ⎦ since k ≥ 4. 001 006 360 Figure 7. An Example of the 4n-2 node-disjoint paths in for 3 and 7.n kx yΠ ∪ Π = = 0,7 2Q ΠX ΠY 3,7 2Q X=000 060 010 X 3 =300 301 306 310 101 201 106 206 110 210 160 260 234 132 323 023 134 332 034 032 Y 0 =033 043 Y=333 334 343 232 133 233 123 223 143 243 100 200 7 3Q CONDITIONAL FAULT-DIAMETER OF K-ARY N CUBE 71 If, however, 1, 1 + − ik nQ has two faulty nodes, then X must have a second non-faulty neighbor X” inside ik nQ , 1− (see Figure 5), otherwise the total number of faulty nodes would include 2n-2 faulty neighbors of Y inside iknQ , 1− , 2n-3 faulty neighbors of X inside ik nQ , 1− , two faults inside 1, 1 + − ik nQ and one fault (namely Y i-1) inside 1, 1 − − ik nQ for a total of 4n-2 which exceeds 4n-3. Let X” i+1 denote the neighbor of X” located in 1, 1 + − ik nQ . At least one of the three nodes X i+1, X’ i+1 or X” i+1 must be non-faulty since there are only two faults in 1, 1 + − ik nQ . Let X* i+1 denote this non-faulty node. So it is possible to enter 1, 1 + − ik nQ starting from X in at most two moves. We can then use Lemma 1 in 1, 1 + − ik nQ to obtain a fault- free path of length at most ( 1) / 2n k⎢ ⎥⎣ ⎦− from X* i+1 to Y i+1 and then make a final move from Y i+1 to Y. Hence we have in total a fault-free path from X to Y of length at most ( 1) / 2 3n k⎢ ⎥⎣ ⎦− + which is at most / 2 2n k⎢ ⎥⎣ ⎦ + since k ≥ 4. Case 2. x m ≠ y m for all m, 0 ≤ m < n. In this case, X and Y differ in all n dimensions. Let i = x n-1 and j = y n-1 (i ≠ j). We therefore have X ∈ ik nQ , 1− and Y ∈ jk nQ , 1− . Hence X and Y are of the form: X = i xn-2 xn-3...x0 and Y = j yn-2 yn-3...y0. Assume without loss of generality that i, i+1, … j is the shortest path between i and j on the cycle 0, 1, 2, … k- 1. Let xΠ be the set of 2n-1 minimum-distance paths each joining either X to jX or any of the 2n- 2 neighbors X’ of X in iknQ , 1− to its isomorphic node jX ' in jknQ , 1− (see Figure 6). The notations xπ (X, jX ) and xπ (X’, jX ' ) will be used to denote these 2n-1 paths of xΠ . Similarly, let yΠ be the set of 2n-1 minimum-distance paths each joining either Y to iY or any of the 2n-2 neighbors Y’ of Y in jknQ , 1− to its isomorphic node iY ' in iknQ , 1− . The notations yπ ( iY , Y) and yπ ( iY ' , Y’ ) will be used to denote these 2n-1 paths of yΠ . The 4n-2 paths in x yΠ ∪Π are all minimum-distance paths. Each is of length equal to d L (X, jX ) = d L ( iY ,Y) which is at most / 2k⎢ ⎥⎣ ⎦ and they are all mutually node-disjoint. Figure 7 illustrates the 4n-2 paths of x yΠ ∪Π for n = 3, k = 7, X = 000, and Y = 333. These 4n-2 paths are mutually disjoint and therefore at least one of them must be completely fault-free (since the total number of faults is at most 4n-3). Let π be this fault-free path and assume that π ∈ xΠ (the case π ∈ yΠ is symmetric). Let X* denote the end node of *X located in jknQ , 1− (i.e. X* is either jX or one of the 2n-2 nodes denoted jX ' ). From the previous discussion we have: |π | = d L (X, jX ) ≤ / 2k⎢ ⎥⎣ ⎦ . Notice also that at most one of the sub-graphs lknQ , 1− , 0 ≤ l < k, can possibly contain more than 4n-7 faulty nodes otherwise the number of faults would exceed 4n-3 since n ≥ 3 (by assumption of the induction step). Case 2.1. jknQ , 1− has at most 4n-7 faults. KHALED DAY and ABDEREZAK TOUZENE 72 We can build a path π || π (X*,Y) of length at most / 2 2n k +⎢ ⎥⎣ ⎦ , where π (X*,Y) is a fault-free path between X* and Y in jknQ , 1− of length at most ( 1) / 2 2n k− +⎢ ⎥⎣ ⎦ obtained using the induction hypothesis in jknQ , 1− . Case 2.2. If jknQ , 1− has more than 4n-7 faults (hence at most 3 faults outside jk nQ , 1− ). Case 2.2.1. If yπ ( iY , Y) is fault-free. In this case we can build a path: π (X, iY ) || yπ ( iY , Y) of length at most / 2 2n k +⎢ ⎥⎣ ⎦ , where the path π (X, iY ) is a fault-free path of length at most ( 1) / 2 2n k⎢ ⎥⎣ ⎦− + between X and iY in iknQ , 1− obtained using the induction hypothesis in iknQ , 1− . Notice here that the induction hypothesis applies in ik nQ , 1− since the number of faults outside jk nQ , 1− (hence inside ik nQ , 1− ) is at most 3 which is less than 4(n-1)-2 (since n ≥ 3, by induction step assumption). Furthermore, the FFSC is satisfied in iknQ , 1− because it would take at least 2n-2 faults inside iknQ , 1− to make all the neighbors of one of its nodes faulty which is not possible since 2n-2 > 3 (because n ≥ 3) and there are at most 3 faults in iknQ , 1− . Case 2.2.2. yπ ( iY , Y) is faulty. Case 2.2.2.1. 1* +jX is not faulty and 1+jY is not faulty. If d L (X,Y) < / 2n k⎢ ⎥⎣ ⎦ , we can build a path: π || *X → 1* +jX || π ( 1* +jX , 1+jY ) || 1+jY → Y of length at most / 2 2n k⎢ ⎥⎣ ⎦ + , where π ( 1* +jX , 1+jY ) is a fault-free path between 1* +jX and 1+jY of length at most ( 1) / 2n k⎢ ⎥⎣ ⎦− obtained using Lemma 1 in 1, 1 + − jk nQ . Notice that there are at most three faults outside jknQ , 1− and one of them is located on yπ ( iY , Y), therefore there are at most two faults inside 1, 1 + − jk nQ and hence Lemma 1 applies in 1, 1 + − jk nQ . If, however, d L (X,Y) = / 2n k⎢ ⎥⎣ ⎦ , let ' 1X and ' 2X be neighbors of X in ik nQ , 1− corresponding to minimum distance moves from X to Y along two different dimensions (these neighbors exist since n ≥ 3). Consider the 3 paths joining X to 1+jX , '1X to 1' 1 +jX , and '2X to 1' 2 +jX , corresponding to the sequence of moves i → i-1 → i-2 → … → j+1 in dimension n-1. These paths are node-disjoint and each is of length at most / 2 1k⎢ ⎥⎣ ⎦ + . Therefore, it is possible to enter the sub-graph 1, 1 + − jk nQ from X in at most / 2 2k⎢ ⎥⎣ ⎦ + moves (in fact if we had started with the edge X→ 1−iX then we would enter the sub-graph 1, 1 + − jk nQ from X in at most / 2 1k⎢ ⎥⎣ ⎦ + moves). Since in addition 1, 1 + − jk nQ has at most two faults, Lemma 1 can be used to go from one of the nodes 1+jX , 1'1 +jX or 1'2 +jX to 1+jY in at most ( 1) / 2n k⎢ ⎥⎣ ⎦− moves (in fact in at most ( 1 / 2 1n k⎢ ⎥⎣ ⎦− − moves if we had started with edge X → ' 1X or edge X → '2X since the initial move is a minimum distance move) and then from 1+jY to Y yielding an overall path from X to Y of length at most / 2 2n k⎢ ⎥⎣ ⎦ + . Case 2.2.2.2. Both 1* +jX and 1+jY are faulty. CONDITIONAL FAULT-DIAMETER OF K-ARY N CUBE 73 Case 2.2.2.2.1. 1−jY is not faulty. In this case, the only faulty nodes outside jknQ , 1− are 1* +jX , 1+jY and one node other than 1−jY on yπ ( iY , Y). In this case we can build a path: π -1 || π ( 1−jX , 1−jY ) || 1−jY → Y, of length at most / 2 2n k⎢ ⎥⎣ ⎦ + , where π ( 1−jX , 1−jY ) is a minimum distance fault-free path between 1−jX and 1−jY in 1, 1 − − jk nQ (notice that there are no faults in 1, 1 − − jk nQ in this case) and π -1 denotes the path obtained from π by removing its last 1−jX → X* edge. Case 2.2.2.2.2. 1−jY is faulty. The only faulty nodes outside jknQ , 1− are 1* +jX , 1+jY and 1−jY . In this case, Y must have at least one neighbor Y’ inside jknQ , 1− which is not faulty (by FFSC). We can, therefore, build a fault-free path: π ( X, iY ' ) || yπ ( iY ' , 'Y ) || 'Y → Y of length at most / 2 2n k⎢ ⎥⎣ ⎦ + where π ( X, iY ' ) is a minimum distance fault-free path between X and iY ' in iknQ , 1− (notice that there are no faults in ik nQ , 1− in this case). Case 2.2.2.3. 1* +jX is not faulty and 1+jY is faulty. Here 1+jY is faulty and we have at least one fault located on yπ ( iY , Y) (condition of all sub cases under case 2.2.2). Therefore, there is at most one other fault outside jknQ , 1− . Furthermore, node Y must have at least one non faulty neighbor (by FFSC). We distinguish the following two sub-cases: Case 2.2.2.3.1. Some neighbor Y’ of Y inside jknQ , 1− is not faulty. Hence, at least one of the following two paths must be fault-free: π ( X, iY ' ) || yπ ( iY ' , 'Y ) || 'Y → Y, (here |π ( X, iY ' )| ≤ ( 1) / 2n k⎢ ⎥⎣ ⎦− (by Lemma 1) π || *X → 1* +jX ||π ( 1* +jX , 1' +jY ) || 1' +jY → 'Y → Y (all moves are minimum distance moves except for the two moves *X → 1* +jX and 1' +jY → 'Y ). The length of each of these two paths is clearly at most / 2 2n k⎢ ⎥ +⎣ ⎦ . Case 2.2.2.3.2. The neighbor 1−jY of Y is not faulty. Let 1' −jY and 1" −jY denote two neighbors of 1−jY inside 1, 1 − − jk nQ . Obviously 1' −jY and 1" −jY cannot be on the path yπ (Y, iY ) since 1−jY is the only node on this path that is located in 1, 1 − − jk nQ (this is justified by the fact that the paths in yΠ are minimum distance paths). Therefore, at least one of the following two paths must be fault-free and is of length at most / 2 2n k⎢ ⎥⎣ ⎦ + : π ( X, iY ' ) || yπ ( iY ' , 'Y )-1 || 1' −jY → 1−jY → Y π ( X, iY " ) || yπ ( iY " , "Y )-1 || 1" −jY → 1−jY → Y where π ( X, iY ' ) and π ( X, iY " ) are paths of length at most [ ]/ 2( 1) kn − obtained using Lemma 1 in iknQ , 1− . Case 2.2.2.4. 1* +jX is faulty and 1+jY is not faulty. KHALED DAY and ABDEREZAK TOUZENE 74 If Y has a non faulty neighbor other than 1+jY then the same sub-cases 2.2.2.3.1 and 2.2.2.3.2 apply for this case too. If, however, all the 2n-1 neighbors of Y other than 1+jY are faulty, then for at least one of the 2n-2 neighbors '*X of *X inside jknQ , 1− we must have both '*X and its neighbor 1'* +jX in 1, 1 + − jk nQ non-faulty. Otherwise, there will be at least 2n-1 (neighbors of Y) plus 2n-2 (neighbors '*X of *X in jknQ , 1− or their corresponding 1'* +jX in 1, 1 + − jk nQ ) plus one ( 1* +jX ) faults for a total of 4n-2 faults which exceeds the number of faults 4n-3. In this case the path: π || *X → '*X → 1'* +jX ||π ( 1'* +jX , 1+jY ) || 1+jY → Y is fault-free, where π ( 1'* +jX , 1+jY ) is a path of length at most ( 1) / 2n k− ⎢ ⎥⎣ ⎦ obtained applying Lemma 1 in 1, 1 + − jk nQ . The overall length would not exceed / 2 2n k +⎢ ⎥⎣ ⎦ if the length of π is strictly less than / 2k⎢ ⎥⎣ ⎦ . If however the length of π is at its maximum value / 2k⎢ ⎥⎣ ⎦ (i.e. X and Y are diametrically opposite along dimension n-1) then a different path is needed. An alternative path can be built going first from X to a non faulty neighbor iY ' of iY following edges of a minimum distance path from X to iY inside iknQ , 1− (this is possible making use of Theorem 2 inside ik nQ , 1− and remembering that X and Y differ in all dimensions and that iknQ , 1− contains at most one faulty node). In fact it is possible to find a non faulty neighbor iY ' of iY such that 1' +jY is also not faulty since we are left only with one fault outside jknQ , 1− other than 1* +jX and 1−jY . The path can then continue going from iY ' to 1' +jY correcting the digit at dimension n-1 along the opposite direction of that followed along yπ ( iY ,Y) (i.e. in the direction i → i-1 → i-2 … → j+1). Going in this direction along dimension n-1 requires at most one extra move beyond the minimum distance since X and Y are diametrically opposite along dimension n-1. The alternative path can be completed by the two moves from 1' +jY to 1+jY and then from 1+jY to Y . The overall length of this alternative path would not exceed / 2 2n k⎢ ⎥⎣ ⎦ + since all moves are along minimum distance paths except possibly for the one extra move on the path from iY ' to 1' +jY (the opposite direction path) and the last move from 1+jY to Y. Theorem 4. The conditional fault-diameter of the k-ary n-cube is equal to / 2 2n k⎢ ⎥⎣ ⎦ + for k ≥ 4 and n ≥ 2. Proof. Derived from combining the results of Lemma 2 and Lemma 3. 5. Conclusion We have contributed to the study of the fault-tolerance of the k-ary n-cube interconnection network by establishing its conditional fault-diameter under the FFSC (i.e., assuming that each non- faulty processor has at least one non-faulty neighbor). We have shown that under this condition and for k ≥ 4 and n ≥ 2, the conditional fault-diameter of the k-ary n-cube is / 2 2n k⎢ ⎥⎣ ⎦ + . This means that if there are less than 4n-2 faults in the k-ary n-cube and if every non faulty node has at least one non- faulty neighbor, then there is a fault-free path of length at most / 2 2n k⎢ ⎥⎣ ⎦ + between any two non- CONDITIONAL FAULT-DIAMETER OF K-ARY N CUBE 75 faulty nodes. We have shown how to construct these fault-free paths. With this result the k-ary n-cube joins a group of interconnection networks (including the hypercube and the star-graph) whose conditional fault-diameter have been proved to be only two units over the fault-free diameter. 6. References BOSE, B., BROEG, B., KWON, Y. and ASHIR, Y. 1995. Lee distance and topological properties of k-ary n-cubes, IEEE Trans. Computer, 44(8): 1021-1030. DAY, K. 2004. The Conditional Node-Connectivity of the k-ary n-Cube, Journal of Interconnection Networks, 5(1):13-25. DAY, K. and Al-AYYOUB, A.E. 1997. Fault Diameter of k-ary n-cube Networks, IEEE Trans. on Parallel and Distributed Systems, 8(9): 903-907. ESFAHANIAN, A.H. 1989. Generalized Measures of Fault Tolerance with Application to n-Cube Networks, IEEE Trans. on Computers, 38(11): 1586-1591. LATIFI, S. Combinatorial Analysis of Fault-Diameter of the n-Cube, IEEE Trans. on Computers, 42(1): 27-33,1993. LATIFI, S., HEGDE, M. and NARAGHI-Pour, M. 1994. Conditional Connectivity Measures for large Multiprocessor Systems, IEEE Trans. on Computers, 43(2): 218-222. ROUSKOV, Y., LATIFI, S. and SRIMANI, P.K. 1996. Conditional Fault Diameter of Star Graph Networks, Journal of Parallel and Dist. Computing, 33: 91-97. TOUZENE, A. and DAY, K. 2005. Conditional Fault-Diameter of the Torus, to appear in SQU Journal for Science 10:53-63. WU, J. 1998. FAULT Tolerance Measures for m-Ary n-Dimensional Hypercube Based on Forbidden Faulty Sets, IEEE Trans. on Comp., 47(8): 888-893. Received 10 September 2004 Accepted 9 August 2005