A Graph Partitioning Approach to Sequential Diagnosis.
AbstractThis paper describes a generalized sequential diagnosis algorithm whose analysis leads to strong diagnosability results for a variety of multiprocessor interconnection topologies. The overall complexity of this algorithm in terms of total testing and syndrome decoding time is linear in the number of edges in the interconnection graph and the total number of iterations of diagnosis and repair needed by the algorithm is bounded by the diameter of the interconnection graph. The degree of diagnosability of this algorithm for a given interconnection graph is shown to be directly related to a graph parameter which we refer to as the partition number. We approximate this graph parameter for several interconnection topologies and thereby obtain lower bounds on degree of diagnosability achieved by our algorithm on these topologies. If we let N denote total number of vertices in the interconnection graph and  denote the maximum degree of any vertex in it, then our results may be summarized as follows. We show that a symmetric d-dimensional grid graph is sequentially $\Omega \left( {N^{{{d \over {d+1}}}}} \right)$-diagnosable for any fixed d. For hypercubes, symmeteric log N-dimensional grid graphs, it is shown that our algorithm leads to a surprising $\Omega \left( {{{{N\,{\rm log\,log}\,N} \over {log\,N}}}} \right)$ degree of diagnosability. Next we show that the degree of diagnosability of an arbitrary interconnection graph by our algorithm is $\Omega \left( {\sqrt {{{N \over \Delta }}}} \right).$ This bound translates to an $\Omega \left( {\sqrt N} \right)$ degree of diagnosability for cube-connected cycles and an $\Omega \left( {\sqrt {{{N \over k}}}} \right)$ degree of diagnosability for k-ary trees. Finally, we augment our algorithm with another algorithm to show that every topology is $\Omega \left( {N^{{{1 \over 3}}}} \right)$-diagnosable.
Introduction
The problem of identifying faulty processors in a multiprocessor system, known as system-level
diagnosis, has been extensively studied in the literature [1, 2, 3, 4, 5]. The foundations of
this area and the original diagnostic model were established in a classic paper by Preparata,
Metze and Chien [1]. This model, known as the PMC model, has been widely studied [1, 6,
7, 8, 9, 10, 11, 12, 13, 14, 15]. It assumes a system to be composed of units or processors
capable of testing each other along the available communication channels. Once a unit u 1
has tested another unit u 2 , it declares u 2 as fault-free or faulty. The outcome of the test
is considered reliable iff unit u 1 is fault-free. Only permanent faults are considered in this
model. In recent years, probabilistic fault models which allow intermittent faults have also
been actively studied [16, 17, 18].
The process of interpreting the test results so as to correctly determine the status of
various processors is known as syndrome-decoding. This can be done either by a central
observer [1, 6, 8, 4, 7, 9] or it can be done in a distributed manner [11, 12, 13, 14, 15]. While
the main criticism of the former approach is the bottleneck created by the central observer,
the weakness of the distributed approach lies in the amount of message traffic generated
and the global storage requirements for the diagnostic software and information. Motivated
by these observations, the notion of semi-distributed diagnosis was introduced [19], where
a group of processors is used to coordinate the diagnosis process. In this paper, we use
the PMC model and assume existence of a central observer to coordinate the diagnosis and
to process the outcomes of various tests. Furthermore, we assume that the set of faulty
processors does not change during the execution of the algorithm.
Preparata et al. also introduced the notions of one-step and sequential diagnosis [1].
In the first approach, called one-step diagnosis or diagnosis without repair, the objective is
to identify all the faulty units before any faulty unit is replaced or repaired. The latter
approach, known as sequential diagnosis or diagnosis with repair, on the other hand, aims
at iteratively identifying subsets of faulty units. At the end of each iteration, the identified
subset of faulty units is repaired or replaced before the next iteration is initiated. This
process is repeated until the system has been completely diagnosed and repaired. Given a
diagnosis algorithm A for a system S, one-step or sequential, the largest integer t such that
for any set of faults F with jF j  t, the system can be correctly diagnosed, is referred to
as the degree of diagnosability of A for S. A system is called one-step t-diagnosable if there
exists an algorithm to correctly locate all faulty processors whenever the total number of
faulty processors does not exceed t. Similarly, a system is called sequentially t-diagnosable if
there exists an algorithm to correctly locate at least one faulty processor provided the total
number of faulty processors does not exceed t. Hakimi and Amin gave a characterization of
one-step t-diagnosable systems [6]. Huang et al. presented a characterization theorem for
sequentially t-diagnosable systems [9].
A multiprocessor system S can be modeled as a graph G which we refer to as the inter-connection
graph. The vertices of G correspond to the processors and the edges correspond
to direct communication channels available between pairs of processors. The graph G will be
undirected as we assume the communication channels to be bi-directional. In our discussion,
we use the terms processor and vertex interchangeably.
A well-known result implies that the maximum diagnosability of a one-step diagnosis
algorithm for any system S, is bounded from above by the minimum vertex degree in its
interconnection graph [1]. This result has pessimistic implications for systems whose inter-connection
graphs have one or more vertices of small degree. However, a variety of commercial
multiprocessor systems are based on topologies which result in interconnection graphs
containing many vertices of small degree. Some examples of such topologies include multi-dimensional
grids (a special case is the hypercube 1 ), cube-connected cycles and trees. Thus
for example, in any tree interconnection graph, since there must exist a leaf vertex, there
does not exist a one-step diagnosis algorithm which can always correctly diagnose in the
presence of more than a single fault. This bound is independent of the total number of
processors in the system.
For such topologies, as we explore in this paper, sequential diagnosis appears to be a
significantly more powerful alternative. So far little previous work has been done in the area
of sequential diagnosis algorithms. Kavianpour and Kim have argued that a hypercube is
sequentially \Theta(
N log N) 2 -diagnosable where N is the total number of processors [10]. The
crux of their argument lies in the existence of a simple cycle in the hypercube which contains
a sufficiently small number of faulty units to be sequentially diagnosable using the results
of [1] on single-loop systems. However, it is not clear how one might identify such a cycle.
The authors of the present paper have also developed a sequential diagnosis algorithm
for the hypercube topology which achieves \Omega\Gamma
log N) degree of diagnosability [20]. The
algorithm has O(N) time complexity and requires O(log N) iterations of diagnosis and repair.
In this paper, we develop a generalized sequential diagnosis algorithm. The degree of
1 Throughout this paper, the word hypercube refers to a binary hypercube.
logarithms used in this paper have base 2.
diagnosability of this algorithm for any given interconnection topology, is directly related
to a graph parameter which we refer to as the partition number. Our approach yields
surprisingly high degree of diagnosability for several interconnection topologies. Specifically,
we show that a d-dimensional grid graph with each dimension of length Nd is sequentially
d
d+1 )-diagnosable for any constant d. For hypercubes, grid graphs in log N dimensions
where each dimension has length two, we prove an \Omega\Gamma N log log N
log N
degree of diagnosability. We
show that this algorithm has degree of diagnosability \Omega\Gamma
interconnection graph
with maximum vertex degree \Delta. This result implies that the degree of diagnosability of
a cube-connected cycles graph is \Omega\Gamma
N) and that a k-ary tree can be correctly diagnosed
in presence of
processors. However, a lower bound of \Omega\Gamma
) is not
effective when \Delta is large. To handle such graphs effectively, we augment this algorithm
to obtain an \Omega\Gamma N3 ) lower bound on the degree of diagnosability of any arbitrary graph.
The time complexity of the augmented version remains the same. The total time taken
by our algorithm in testing and syndrome decoding for any interconnection graph is linear
in the total number of edges in the graph. Lastly, the maximum number of iterations of
diagnosis and repair needed by the algorithm are shown to be bounded by the diameter of
the interconnection graph and one more than the diameter for the augmented version.
The remainder of this paper is organized as follows. Section II develops the essential
relationship between the partition numbers and degree of diagnosability of a graph. We
also design and analyze the complexity of the generalized sequential diagnosis algorithm.
This section is concluded with a sketch of the basic approach to derive lower bounds on the
degree of diagnosability achieved by our algorithm for various interconnection graphs. In
Sections III through VI, we estimate the partition numbers and derive diagnosability results
for the symmetric grid graphs in a fixed dimension, hypercubes, cube-connected cycles, k-ary
trees and arbitrary topologies, respectively. Section VII describes an approach to improve
the time complexity for dense interconnection graphs.
II. Graph Partitioning and Sequential Diagnosis
A. Notation
For a given undirected graph G, we use V (G) and E(G) to denote its set of vertices
and edges, respectively. D(G) denotes the diameter of the graph G and \Delta(G) denotes the
maximum degree of any vertex in G.
In order to concisely represent the performance characteristics of our algorithm for a
given interconnection graph, a 3-tuple notation of the form ht I i is used where t F is a
lower bound on the degree of diagnosability, t T is an upper bound on the total testing and
syndrome decoding time needed and t I denotes an upper bound on the number of iterations
of diagnosis and repair needed by the algorithm.
B. Partition Numbers and Sequential Diagnosability
Let G be a given interconnection graph. We will assume G to be a connected graph.
For each edge (x; y) 2 E(G), let processor x test y and vice versa. The outcomes of the
tests thus conducted can be abstracted into a labeled undirected graph called the
syndrome graph. If we let G S denote the syndrome graph, then V(G S
simply consists of the edges in E(G) with labels. An edge (x; y) is given label "pass" if x
declared y to be fault-free and vice versa. Similarly, we label an edge (x; y) as "fail" if x and
y declare each other to be faulty. Any other edges are labeled as "conflict". The following
simple lemma characterizes a useful property of this graph.
be the subgraph of the syndrome graph G S induced by the edges labeled
as "pass". Then in each connected component of G P , either all vertices are fault-free or all
of them are faulty. 2
An immediate corollary is as
Corollary 1 Let t be an upper bound on the total number of faulty processors in the system.
If the graph G P contains a connected component of size t + 1 or larger, then it must be the
case that all these vertices correspond to fault-free processors. 2
Corollary 1 forms the basis of our generalized sequential diagnosis algorithm. Our approach
is based on considering a certain parameter for the interconnection graph G which
we refer to as the partition number.
Given a connected graph G, we define the k-partition number of G as the
largest integer p such that for all p-element subsets S ' V (G), the subgraph of G induced by
the vertices in V (G) \Gamma S has a connected component of size k or larger. 2
The k-partition number of G is denoted by OE G (k) and in general for a given G, it will be
a function of k and jV(G)j. This function is undefined for k ? jV (G)j.
Suppose we allow a maximum of t faulty processors in our system. Let U be the set of
vertices in G corresponding to the fault-free processors and let EU be defined as below :
Observe that E(G P ) must contain all the edges in EU . Therefore, if the value t was chosen
such that OE G t, then the graph G P must have a component of size t + 1 or larger.
Moreover, by Corollary 1, any such component must consist solely of vertices corresponding
to fault-free processors.
C. The Generalized Sequential Diagnosis Algorithm
We now use the above observations to design a generalized sequential diagnosis algorithm,
referred to as the PARTITION algorithm. Let G be the interconnection graph for a given
system S and let t be a non-negative integer such that OE G t. Then we can use the
following algorithm to correctly diagnose all the faults in S provided there are no more than
t faulty processors in S. For a clear exposition, we describe the algorithm as composed of
two phases :
The objective of this phase is to identify a subset of fault-free processors. Each processor
is asked to test each one of its neighbors. The outcomes of these tests are used to
construct the syndrome graph G S . Let G P be the subgraph of G S induced by the edges
labeled "pass". We do a depth-first search to locate a connected component of size at
least . By our choice of t, we are guaranteed to find such a component and
by Corollary 1, all the processors in this component must be fault-free.
Iterative Diagnosis and Repair
This phase is aimed at iteratively diagnosing and repairing the faulty processors in the
system using the subset identified in phase 1. Select an arbitrary fault-free processor,
say u, from the component identified in phase 1 and construct a breadth-first search
tree of G rooted at this processor. Let h denote the height of breadth-first search tree
and let L i , 0  i  h denote the set of processors at distance i from u in this tree. We
now use the following iterative scheme. Initialize an index variable, say i, to 0. Use
the processors in set L i to test the processors in the set L i+1 . If any processors in L i+1
are identified as faulty then repair or replace them. Increment the index i by 1 and
repeat this till i equals h. Since in the i
th
iteration, all the processors in the set L i are
known to be fault-free, they always diagnose the processors in the set L i+1 correctly.
Now let us analyze the total testing and syndrome decoding time taken by the PARTITION
algorithm. Phase 1 is easily seen to be performed in O(jE(G)j) time. In phase 2,
the breadth-first search tree is constructed in O(jE(G)j) time. The total number of tests
conducted over all iterations is simply the number of edges in the breadth-first tree, that
is, Aggregating over all the iterations, the total time taken in testing and forwarding
this test information to the central observer for syndrome decoding, is O(jV (G)j).
Therefore, the overall complexity of this algorithm is O(jE(G)j). Finally, since the height of
the breadth-first search tree constructed in phase 2 above can be no more than D(G), the
algorithm needs at most so many iterations of diagnosis and repair.
For a given graph G, OE G (t) must be a monotonically non-increasing function of t. There-
fore, the optimal value of t for the PARTITION algorithm is the largest integer satisfying the
inequality OE G t. The following theorem summarizes the performance characteristics
of the PARTITION algorithm.
Theorem 1 For a given interconnection graph G, let t denote the largest integer such that
t. Then PARTITION is a
ht; O(jE(G)j); D(G)i
sequential diagnosis algorithm for G. 2
The PARTITION algorithm as described above, can be suitably modified to improve the
performance in practice. For instance, in phase 2 of the algorithm, one may use a collection
of breadth-first search trees which is constructed by doing a simultaneous breadth-first search
from all the fault-free processors identified in phase 1. However, such modifications leave
the asymptotic worst case performance of the algorithm unchanged.
D. Estimating the Degree of Diagnosability
We have not yet considered the issue of determining the function OE G (:) for a given graph
G. In general, it might be very hard to determine this function exactly. However, for our
application, it will be sufficient to closely approximate this function by another function
OE
G (k) such that for a given G and any non-negative integer k  jV (G)j, OE
G (k)  OE G (k). A
two-step approach is used to approximate the function OE G (k).
First, we concentrate on a closely related function /G (k) which we define as the smallest
integer p such that there exists a p-element set S ' V (G) so that the subgraph of G induced
by the vertices in V (G) \Gamma S has no connected component of size k or larger. The following
simple lemma relates the two functions.
Lemma 2 For any connected graph G and a non-negative integer k  V (G), OE G
As we will see, it is more convenient to estimate the function /G (k). We first approximate
/G (k) by /
G
(k) such that /
G
use Lemma 2 to obtain a candidate
solution for OE
G
(k). It is easily seen that the largest integer t   satisfying OE
G
always less than or equal to the largest integer t satisfying OE G t.
III. Symmetric Grid Graphs
A d-dimensional grid graph is defined as the graph obtained by P n 1
\Theta P n 2
\Theta ::: \Theta P n d
where \Theta
is the graph cartesian product operation, P n i
denotes a path on n vertices and n i , 1  i  d
denotes the length of dimension i. Let this graph be denoted by G d (n 1
graph can alternatively be viewed as a recursively constructed graph. More specifically, it
can be recursively defined as G d (n 1
simply a copy of P n 1
. It is easy to see that G d (n 1 contains \Pi d
vertices. A grid
graph is called symmetric if each dimension of the graph has the same length. A symmetric
d-dimensional grid graph with each dimension n units long, is denoted by G d (n).
In this section, we will derive diagnosability results for d-dimensional grid graphs when
d is a constant. The following lemma gives a useful property of subgraphs of such graphs.
Lemma 3 Let H be a subgraph of G d (n) where d is a constant. Then the vertex degree sum
of H is bounded from above by
Furthermore, this bound is exact if H is isomorphic to G d (p) for some integer p  2.
We prove by induction on d. The basis case with
Let k denote jV (H)j and let S(d; denote the maximum degree sum for any k-vertex
subgraph of a d-dimensional grid graph. Using the recursive definition, we know that the
graph G d (n) is composed of n copies of G
denote the set of all n-tuples ~
are non-negative integers and
k. Using this notation, we can write the following
recurrence to get an upper bound on S(d;
~
f
1in
The term
the maximum vertex degree sum contribution due
to the edges in H with each end-point inside a G i , 1  i  n. The expression 2
on the other hand, indicates the maximum possible contribution to the vertex
degree sum due to edges connecting vertices of G i with G To see this,
observe that the total number of such edges cannot exceed
is clearly bounded by
Using the induction hypothesis, we can rewrite the above inequality as below :
We only describe the analysis needed to get the upper bound on S(d; 2.
An essentially identical argument can be used to show that S(2;
k). Observe
that to get this upper bound when d ? 2, it is sufficient to solve the following minimization
problem
min
~
x
1in
A two-step approach is used to solve this minimization problem. Let
For a given value of x, we first determine the minimum value for the objective function in
equation 4. Next we minimize this value over all values of x. So our first step is to solve the
following minimization problem :
min
~
x
To determine the solution to this problem, we analyze the distribution of values which
must be satisfied by pairs of variables in the optimal solution. Let us consider any two
variables x i and x j . Suppose y. Now consider the function f(x i
in the interval [0; y], f(x i ) is concave over this
interval. Given that x i  x and x j  x, the minima for f(x i ) subject to this constraint occurs
uniquely at the boundary x y, the minimum value
is obtained by setting x Otherwise, the minimum value is obtained by setting
argument implies that if (x
n ) is the solution to the
minimization problem specified in equation 5, then there cannot exist 1
that
x. Thus the minimum occurs precisely when b k
x
c of the x 0
take the value
x and the remaining ones are set to zero except possibly one which takes the value
x
c.
So for a given value of x, the minimum value of the function in equation 4 is 2(d \Gamma
x
cx
x
c)
the function g(x) denote this minimum value for a
given x. It is rather easy to see that ( k
x c)x
x c)
if we define a function h(x) by
x
)x d\Gamma2
Relaxing the integrality constraint on x, we find that the function h(x) is minimized when
d and its minimum value is 2dk
d . Thus g(x) is bounded from below by this value.
The last step now simply involves substituting the lower bound on the value of g(x)
determined above in equation 3 to get an upper bound on S(d; k). This gives us the desired
result.
Finally, the bound determined above is verified to be exact when H is isomorphic to
G d (p) for p  2 by straightforward induction on d. 2
Lemma 4 For every non-negative integer t  N ,
d
denotes the total number of vertices in G d (n) and d is a constant.
Proof : The inequality in the statement trivially holds when We now use Lemma 3
to analyze the case when t ? 0. Let X t denote a set of vertices such that the graph induced
by V (G d contains no connected component with more than t vertices. Using the
convexity of the function
d ) for non-negative k, and an analysis similar to one
used in Lemma 3, it is not difficult to show that an upper bound on the sum of the degrees
of the vertices in the graph induced by V (G d
d )). Thus
must satisfy the following inequality :
The term 4djX t j gives an upper bound on the possible degree loss due to deletion of jX t j
vertices from G d (n).
Rearranging the terms, we get the following lower bound on jX
d
d
The lemma follows. 2
Theorem 2 For a symmetric d-dimensional grid graph with N vertices, the algorithm PARTITION
is a
d
sequential diagnosis algorithm if d is a constant.
Using Lemmas 2, 4, and Theorem 1, the degree of diagnosability is at least as
large as the largest integer t satisfying the following inequality :
d
For sufficiently large N , this inequality is satisfied by
d
d+1 for any non-negative
constant
Since degree of a vertex is bounded by d, total number of edges is O(N ). Hence t T is
O(N) by Theorem 1.
Finally, it is readily seen that in a symmetric grid graph, the total number of edges is
O(N) and the diameter is d(N 1
1). Substituting in Theorem 1, we get the stated result.IV. Hypercube Graphs
A d-dimensional hypercube, denoted by H d , is simply a symmetric grid graph with each
dimension of length 2. Thus if the hypercube has N nodes then it has log N dimensions.
The theorem in the previous section applies only to constant dimension symmteric grid
graphs. In this section we use a similar technique to analyze hypercubes.
Lemma 5 Let H be a subgraph of H d , jV (G)j  1. Then the vertex degree sum of H is
bounded from above by
Furthermore, this bound is exact if H is isomorphic H p for some non-negative integer p.
As before, we use induction on d. The basis case with
Let k denote jV (H)j and let S(d; denote the maximum degree sum for any k-vertex
subgraph of H d . Using an argument identical to the one in Lemma 3, we can write the
following recurrence for S(d; k).
then we are done by induction hypothesis. Otherwise, using the induction
hypothesis, we can rewrite equation 9 as follows.
fx log
in the interval [1; b kc], the
function f(x) is convex over this interval. Therefore the maximum occurs at the boundary
of this interval and is easily verified to be bounded by k log k.
Finally, it is trivial to verify that the bound is exact when H is isomorphic H p for some
non-negative integer p. 2
Lemma 6 For every positive integer t  N ,
log(N 2 =t)
is the total number of vertices in H d .
Proof : The proof is similar to that of Lemma 4. If X t denotes a set of vertices such
that the graph induced by V (H d contains no connected component with more than t
vertices, then applying Lemma 5, we get the following inequality :
Solving for jX t j, we get
log(N 2 =t)
Thus we get the desired result. 2
Finally, we now derive a lower bound on the degree of diagnosability of hypercubes using
the above lemma.
Theorem 3 For a hypercube graph with N vertices, PARTITION is a
log log N
log N
O(N log N); log Ni
sequential diagnosis algorithm.
Using Lemmas 2 and 6, and Theorem 1, the degree of diagnosability is at least
as large as the largest integer t which satisfies the following inequality :
log(N 2 =t)
For sufficiently large N , this inequality is satisfied by log log N
log N
for any non-negative
log log N
log N
The values of t T and t I follow in a straightforward manner from Theorem 1. 2
V. Cube-Connected Cycles and k-ary Trees
We first derive a general lower bound on the partition numbers of a graph G with a given
maximum vertex degree. For sake of clarity, we slightly abuse our notation in the present
and the next section; we use V and \Delta to denote V (G) and \Delta(G) respectively.
Lemma 7 For every non-negative integer t  jV j,
As before, we let X t denote a set of vertices such that the graph induced by
contains no connected component with more than t vertices. Since no vertex in
G has degree more than \Delta, we observe that deletion of a vertex from any subgraph of G
cannot create more than new components. Thus after we delete the vertices in set X t ,
the total number of connected components in the remaining subgraph can be no more than
j. By the pigeonhole principle, therefore, at least one component must have
at least
vertices. Thus X t must satisfy the following inequality :
Simplifying, we get jX t j  jV j\Gammat
. 2
The above lemma gives us the following general theorem.
Theorem 4 For any given interconnection graph G, the PARTITION algorithm is a
c; O(jEj); Di
sequential diagnosis algorithm.
Proof : It is sufficient to indicate how the value of t F is determined. Using Lemmas
2 and 7, and Theorem 1, like before, we get a quadratic inequality as below :
Solving for largest value of t gives us the result. 2
A. Cube-Connected Cycles
The cube-connected cycles topology for a given dimension d is obtained by replacing the
vertices of H d by cycles of length d each such that if nodes x and y were adjacent to each
other along dimension i in H d , then in the cube-connected cycles, we connect the i th vertex
of the cycle at vertex x to the i th vertex of the cycle at vertex y. Thus each vertex in this
topology, has two neighbors in the cycle containing it and one neighbor in another cycle.
A cube-connected cycles structure in dimension d is denoted by C d . The total number of
vertices in C d is d2 d . The following lemma bounds the diameter of C d ; the proof follows
from [21].
Lemma 8 The diameter of C d is bounded by b 5dc \Gamma 1. 2
Lemma 8 combined with Theorem 4 gives us the following result.
Theorem 5 For a cube-connected cycles graph with vertices, the PARTITION
algorithm is a
sequential diagnosis algorithm. 2
B. k-ary Trees
An interesting class of trees is the k-ary trees where each vertex has no more than k
children, k  2. Clearly, the maximum degree of any vertex in a k-ary tree is k + 1. Using
this observation with Theorem 4 implies that every k-ary tree is \Omega\Gamma
)-diagnosable by the
PARTITION algorithm. An important subclass of k-ary trees is the family of complete k-ary
trees. Every non-leaf vertex in a complete k-ary tree has exactly k children and depth of any
pair of leaves differs by at most one. It is a simple exercise to verify that the diameter of a
complete k-ary tree with N vertices is bounded by d2 log k (Nk using
Theorem 4, we have the following result for complete k-ary trees.
Theorem 6 For a complete k-ary tree with N vertices, the PARTITION algorithm is a
sequential diagnosis algorithm. 2
VI. Arbitrary Topologies
In this section, we derive a lower bound on the degree of diagnosability of any arbitrary
topology. The lower bound given by Theorem 4 is effective only when the maximum degree
of the interconnection graph G is not very large. To get better bounds for graphs with one
or more vertices of sufficiently large degree, we augment the PARTITION algorithm with
another algorithm which gives us better bounds on degree of diagnosability when G contains
one or more vertices of sufficiently large degree.
As before, let G be a given interconnection graph. Consider the following algorithm
which we call the MAX algorithm :
Diagnosing a Single Processor
Select a vertex of largest degree in G, say v. Let each of the neighbors of v test the
vertex v. Suppose precisely x of the neighbors declare v to be fault-free. If x+1
then v is determined to be fault-free else v is determined to be faulty.
Iterative Diagnosis and Repair
If vertex v is identified to be faulty in phase 1 then it is repaired or replaced. Now we
proceed in a manner identical to phase 2 of the PARTITION algorithm and hence we
omit details. However, we do notice that the total number of iterations of diagnosis
and repair are now bounded by D(G) + 1.
The issue now is to determine how many faulty processors can we allow such that any
vertex of maximum degree in G is correctly diagnosed in the phase 1 of the MAX algorithm.
Theorem 7 For any given interconnection graph G, the MAX algorithm is a
sequential diagnosis algorithm. 2
We only consider determination of t F . Let v be a vertex of maximum degree in
G. Suppose x neighbors of v declare it to be fault-free and the remaining declare it to be
faulty. If we assume v to be fault-free, then we must have at least \Delta \Gamma x faulty vertices in
G. On the other hand, if we assume v to be faulty, then we must have at least x
vertices in G. It is sufficient to choose t F such that
versa. Choosing t \Deltac achieves this objective. 2
The modified PARTITION algorithm can be stated as follows. If b \Deltac  b
c
then use the MAX algorithm for diagnosis else use the PARTITION algorithm.
This algorithm is referred to as the MAX PARTITION algorithm. It is easy to verify that
for any G, the maximum of the degree of diagnosabilities of the MAX and the PARTITION
algorithm is \Omega\Gamma jV (G)j 1
3 ). Thus we have the following theorem.
Theorem 8 For any given interconnection graph G, the MAX PARTITION algorithm is a
sequential diagnosis algorithm. 2
VII. Improving Time Complexity for Dense Graphs
As shown by our analysis in Sections II and VI, the time complexity of both PARTITION and
MAX PARTITION is directly proportional to the number of edges in the interconnection
graph. Many topologies of interest lead to sparse interconnection graphs, that is, graphs
with O(N) edges, and thus these algorithms are O(N) time algorithms for such topologies.
A significant exception to this is the hypercube topology which leads to interconnection
graphs with O(N log N) edges. In such cases when the interconnection graph is dense,
however, we may use the structural properties of the underlying topology to embed a suitable
spanning subgraph with relatively fewer edges, say f(N ), and treat this subgraph as the
interconnection graph of interest for the diagnosis algorithm. If this embedding can itself
be done in O(f(N)) time, then the time complexity of our algorithm is now O(f(N)).
Alternatively, the embedding may be simply regarded as a one time pre-processing step
after which the diagnosis will be performed several times. However, it is worthwhile to note
that it is not very likely that the embedded subgraph will have the same diagnosability
and diameter as the original graph. This process, therefore, highlights a potential trade-off
between the time complexity and the diagnosability and number of iterations of diagnosis
and repair needed by the algorithm. We illustrate our point for the hypercube topology.
It is well-known that multi-dimensional grids can be embedded in hypercubes [22]. Consider
a d-dimensional hypercube with d even and embed the graph G 2 (2 d
in the hyper-
cube. This embedding is based on a reflected Gray code sequence and can in fact be done in
O(log N) time. The embedding process simply involves each processor using its d-bit address
to compute the addresses of its neighbors in the embedded copy of G 2 (2 d
the PARTITION algorithm is executed, we only consider the hypercube edges which correspond
to the embedded copy of G 2 (2 d
Though the algorithm now takes O(N) time,
using Theorem 2, we only
3 ) as the degree of diagnosability. Quite interestingly,
even though the diameter of G 2 (2 d
2, we can use a simple scheme based on
the recursive definition of a hypercube to complete iterative diagnosis and repair in no more
than d iterations without altering the O(N) time complexity. The details of this can be
found in [20]. When d is odd, we can use a similar approach on its two (d \Gamma 1)-dimensional
subcubes and embed a copy of G 2 (2
in each of them. Again, we can now apply
Theorem 2 to
diagnosability.
In the above illustration, we embedded a two-dimensional grid graph to show
diagnosability can be achieved in linear time for hypercubes. This idea can be extended in
a straightforward manner to embed c-dimensional symmetric grid graphs in large enough
hypercubes to achieve \Omega\Gamma N
c
diagnosability in linear time for some constant c.
VIII. Conclusions
We presented a generalized sequential diagnosis algorithm and analyzed its degree of diagnosability
for several different topologies which included symmetric grid graphs, cube-connected
cycles and k-ary trees. Our results show that sequential diagnosis can be used to achieve
very high degree of diagnosability even when the vertex degrees are small in the interconnection
graph. It was also shown that an augmented version of this algorithm
diagnosability for any arbitrary interconnection graph with N vertices. The time complexity
of both algorithms was shown to be linear in the number of edges in the interconnection
graph.
One important problem not addressed in this work is the determination of good upper
bounds on the degree of sequential diagnosability for the specific topologies studied here. We
suspect that an analysis in the spirit of the graph partitioning approach of the PARTITION
algorithm may lead to determination of good upper bounds. Another interesting area of
investigation is development of an approach which is a hybrid of the one-step diagnosis and
sequential diagnosis strategies. More precisely, instead of exploring the diagnosability in the
extreme situations which either allow no repair or a linear number of iterations of diagnosis
and repair, study the diagnosability when the total number of iterations of diagnosis and
repair are required to be bounded by some function of the total number of processors.

Acknowledgements

The authors would like to express their sincere thanks to Edgar Ramos for a significant
discussion on Lemma 3, Ran Libeskind-Hadas for his helpful comments on an early version
of this paper, the anonymous referees for their careful review and suggestions, and Prof.
Doug Blough for providing reference [10].
This research was supported in part by the Department of the Navy and managed by the
Office of Naval Research under Grant N00014-91-J-1283, by the Semiconductor Research Corporation
under Contract 95-DP-109, and by the Joint Services Electronics Program (JSEP)
under grant N00014-96-1-0129.



--R

"On the connection assignment problem of diagnosable systems,"
"System-level fault diagnosis,"
"System diagnosis,"
"A generalized theory for system level diagnosis,"
"System-level diagnosis: A perspective for the third decade,"
"Characterization of connection assignment of diagnosable systems,"
"Fault diagnosis in a boolean n-cube array of micro- processors,"
"An O(n 2:5 ) fault identification algorithm for diagnosable systems,"
"Characterization and design of sequentially t- diagnosable systems,"
"A comparative evaluation of four basic system-level diagnosis strategies for hypercubes,"
"Distributed fault tolerance for large multiprocessor sys- tems,"
"A diagnosis algorithm for distributed computing systems with dynamic failure and repair,"
"An optimal algorithm for distributed system level di- agnosis,"
"An adaptive distributed system-level diagnosis algorithm and its implementation,"
"A distributed algorithm for system-level diagnosis in hypercubes,"
"Almost certain diagnosis for intermittently faulty systems,"
"Reliable diagnosis and repair in constant-degree multi-processor systems,"
"Probabilistic diagnosis algorithms tailored to system topology,"
"Performance of fault-tolerant diagnostics in the hypercube systems,"
"New algorithms for sequential diagnosis,"
"The cube-connected cycles: A versatile network for parallel computation,"
Parallel and Distributed Computation.
Throughout this paper
All logarithms used in this paper have base 2.
--TR

--CTR
T. Yamada , T. Ohtsuka , A. Watanabe , S. Ueno, On sequential diagnosis of multiprocessor systems, Discrete Applied Mathematics, v.146 n.3, p.311-342, 15 March 2005
Tao Dong, A linear time pessimistic one-step diagnosis algorithm for hypercube multicomputer systems, Parallel Computing, v.31 n.8+9, p.933-947, August 2005
Paolo Santi , Stefano Chessa, Reducing the Number of Sequential Diagnosis Iterations in Hypercubes, IEEE Transactions on Computers, v.53 n.1, p.89-92, January 2004
V. A. Vedeshenkov, A route-oriented self-diagnosis method for digital systems, Automation and Remote Control, v.66 n.3, p.479-491, March     2005
Antonio Caruso , Stefano Chessa , Piero Maestrini , Paolo Santi, Diagnosability of regular systems, Journal of Algorithms, v.45 n.2, p.126-143, November 2002
Toru Araki , Yukio Shibata, (t, k)-Diagnosable System: A Generalization of the PMC Models, IEEE Transactions on Computers, v.52 n.7, p.971-975, July
Antonio Caruso , Stefano Chessa , Piero Maestrini , Paolo Santi, Evaluation of a Diagnosis Algorithm for Regular Structures, IEEE Transactions on Computers, v.51 n.7, p.850-865, July 2002
Antonio Caruso , Stefano Chessa , Piero Maestrini , Paolo Santi, Fault-diagnosis of grid structures, Theoretical Computer Science, v.290 n.2, p.1149-1174, 2 January
Xiaofan Yang, A fast pessimistic one-step diagnosis algorithm for hypercube multicomputer systems, Journal of Parallel and Distributed Computing, v.64 n.4, p.546-553, April 2004
Yang , Xiaofan Yang, A fast diagnosis algorithm for locally twisted cube multiprocessor systems under the MM* model, Computers & Mathematics with Applications, v.53 n.6, p.918-926, March, 2007
Guey-Yun Chang , Gerard J. Chang , Gen-Huey Chen, Diagnosabilities of Regular Networks, IEEE Transactions on Parallel and Distributed Systems, v.16 n.4, p.314-323, April 2005
system-level diagnosis;analysis of algorithms;sequential diagnosis;graph partitioning;fault-tolerance;degree of diagnosability;multiprocessor systems