A General Method for Maximizing the Error-Detecting Ability of Distributed Algorithms.
AbstractThe bound on component failures and their spatial distribution govern the fault tolerance of any candidate error-detecting algorithm. For distributed memory multiprocessors, the specific algorithm and the topology of the processor interconnection network define these bounds. This paper introduces the maximal fault index, derived from the system topology and local communication patterns, to demonstrate how a maximal number of simultaneous component failures can be tolerated for a particular interconnection network and error-detecting algorithm. The index is used to design a mapping of processes to processor groups such that the error-detecting ability of the algorithm is preserved for certain multiple simultaneous processor failures.
Introduction
In a fixed multi-processor topology, the number of permitted faults and their distribution
in the topology is restricted if we want to be able to detect all resulting errors. This
paper introduces the maximal fault index, derived from the system topology and local
communication patterns of an algorithm, to obtain a maximal number of simultaneous
(Byzantine) component failures and their distribution such that all errors can still be
detected. We will introduce a mapping for the individual processes to processor groups
such that the error-detecting abilities of algorithms are maximized. This fault-tolerant
process-to-processor mapping can be used for safety critical systems since it ensures that
the failure of certain combinations of multiple components does not go undetected, which
increases the dependability of the system.
We call the set of processors obtained from the local interprocess communications
of the algorithm a communication environment (Figure 1(a) shows the star pattern).
Given, as design parameters, the maximum number of faults that can be permitted in
each communication environment such that all errors can still be detected, the local
tolerance t l , and the topology of the entire system, we want to compute the global
tolerance t g which maximizes the number of permitted faults in the system while
maintaining the local fault tolerance condition.

Figure

1(b) shows a scenario where two simultaneously faulty components in the system
will not violate the local fault tolerance. By contrast, Figure 1c shows a syndrome of
faults which violates the local fault tolerance for at least one communication environment.
An optimal fault distribution yields a partitioning of processes into groups such that
all processes within a particular group can be simultaneously faulty and still all errors can
be detected. The processor groups are then mapped, disjointly, into the actual topology.
Thus, the failure of elements in any single processor group still allows for the detection
of all errors.
3,0 . 3,3
0,0 . 0,3
mapped to the same group
simultaneously faulty are
c) processes that may be
a) communication
environment for the
algorithm
0,0 . 0,3
3,0 . 3,3
conventional process-to-
processor mapping

Figure

2: Logical adjacency in the algorithm and physical mapping.
An example for a fault-tolerant mapping is given in Figure 2. The communication
environment used (the square) is described in Figure 2(a). The conventional process-to-
processor mapping is shown in 2(b) and the fault-tolerant mapping can be seen in 2(c).
Details of the mapping algorithm are given in Section 4.
In Section 2, we provide definitions for different collections of processors based on
their faulty or non-faulty status. Section 3 gives a graph coloring algorithm for determining
the distribution of faulty processors within the topology. Section 4 shows that
the characterization of an optimal fault distribution is NP-complete and that of finding
the maximal fault index is NP-hard for arbitrary topologies and communication patterns.
Section 4 also gives an algorithm for determining a process to processor group partitioning
based on the optimal fault distribution. In Section 5 we show that the maximal fault
index for several specific communication patterns and regular topologies can be found
in polynomial time, and we also give partitionings based on their optimal fault distribu-
tions. Section 6 provides an example of how this form of assessment can be used in an
error-detecting matrix relaxation algorithm.
2 Terminology for MPS Topologies
In this paper we examine fixed-topology multiprocessor systems as discussed in [4], [8],
[11], [17]. In contrast to [6] we do not examine whether an algorithm can detect all
combinations of up to k faults, where k is a specified bound, but we assume that the
algorithm has been designed with a certain local fault tolerance t l , for each communication
environment [13]. The analysis in [6] can determine whether every combination of up to
l faults can be detected, and it provides the minimum number of simultaneous faults for
which this condition does not hold any more. In contrast to that, we want to determine
the maximum number of faults, t g and their distribution in the topology for which all
errors can still be detected. However, we do not claim that all combinations of up to t g
faults can be tolerated.
The underlying topology of a multiprocessor system (MPS) is described by a graph
G(V; E), where the set of vertices V represents the processors in the network and the set
of edges E determines the direct communication links between pairs of processors. The
network topology of an MPS does not have to be regular, such as a hypercube or mesh,
but can be an arbitrary connected graph.
For simplification, we will focus only on processor failures, since a processor failure
can be described by the failure of all its links, and a link failure can be described by
indicating a processor failure [15]. We assume the worst-case fault model of Byzantine
(malicious) behavior where a faulty process can lose or modify messages. We can check for
lost messages as well as inconsistency of the data by sending multiple copies of the same
message through node-disjoint paths. Since we allow only a (relatively) small number of
simultaneous faults, we can assume that there always exists at least one path between
communicating processes that does not contain any faulty components, which makes the
detection of inconsistencies possible.
In an MPS interconnection network, the interactions between processors are described
by communication patterns. Frequently, algorithms restrict interprocessor communication
to adjacent processors to improve efficiency. However, new routing technologies, such
as wormhole routing, make the delivery of messages to processors that are a distance of
more than one away almost as efficient as direct communication [3]. We allow for both
types of interactions in the communication environment.
Definition 2.1 The communication environment (CE) of a processor P i is the set of
processors from which P i will receive information during the execution of a program.
This set includes P i as well. The communication environment of a specific processor is
a subset of the set of all n processors in the network, i.e., CE(P i g. 1
Definition 2.2 A fault group of a processor P i of fault tolerance t l , denoted by FG(P i ),
is the collection of faulty processors in CE(P i ). To guarantee error detection for all errors
caused by these faults, we require that
Communication environments usually intersect since P i requests data from other processors and
other processors request data from P i . We need to relate independent failures in different CEs such that
the local fault tolerance, t l , in each environment is not violated.
Definition 2.3 A collection of processors that must be non-faulty to guarantee detection
of all errors induced by the set of faulty processors P is called the non-fault group of P,
denoted by NFG(P). It is the set that contains all elements in the CEs in which the
elements of P are members and in which t l has been reached.
For the algorithm to detect all errors, the following must invariantly hold
are faulty -
Depending on the value of t l , many different non-fault groups exist. The NFG for a set of
processors P determines on which processors P j , outside NFG(P), the failure of P
will have no effect. Failures of these components can be tolerated. For an error-detecting
algorithm we need to ensure that there will be no conflicts between the faulty processors
and their respective NFGs. This means that if a processor fails, it must not be in the
NFG of any other failed processor so that detection of all errors induced by the set of
faulty processors can be guaranteed.
Coloring Faulty MPS Topologies
In this section we discuss how we can find and evaluate the non-fault groups in an
interconnection network, based on the individual communication environments.
An augmentation of the problem graph represented in the MPS interconnection net-work
adds additional symbolic edges (no augmentation is made to the actual topology)
so that the elements located in each CE are adjacent to each other in the augmented
problem graph. Thus, each CE forms a completely connected subgraph. The augmented
edges correspond to fault dependencies between processors in a CE. Since, at any time,
there must be no more than t l faulty components in each CE, there can be at most t l
faulty vertices adjacent to each non-faulty vertex in the augmented graph, and at most
components adjacent to a faulty component.
Algorithmically, to determine the NFG of an individual processor P i , we can mark
adjacent nodes in the augmented graph and permit at most
of them to be faulty. For t must
be non-faulty, together with all processors
i.e., all processors that are in a CE with P i . With t l ? 1 there will be many different
possibilities to place up to t l faulty components into each CE.
We use a coloring algorithm to color the graph, indicating faultiness or non-faultiness
of components, when determining the NFG of an individually faulty processor. We first
describe how the coloring is done for one fault in each CE (t l = 1), and then extend
the algorithm for t l ? 1 to multi-coloring, where each vertex has a chromaticity of t l ,
to obtain the NFGs. Finally, this algorithm is used to obtain a possible distribution of
component failures for the whole MPS.

Figure

3 describes how to find the NFG for t using an algorithm which colors
the faulty components in one color and the components that must be non-faulty in a
for i:=1 to n /* n is the total # of processors */
color
color all processors which are in a CE with P i as non-faulty;
save NFG(P i ); reset colors;
end for

Figure

3: An algorithm to determine the NFGs for individually faulty processors (t l = 1).
different one. This coloring scheme works for arbitrary communication patterns as long
as the CEs of all processors are known.
Theorem 3.1 The time complexity of the coloring algorithm is O(n 3 ).
Proof: Step 2 in the algorithm evaluates at most (n \Gamma 1) processors and their CEs,
taking O(n 2 ) steps; the process will be performed a total of n times in the loop. Hence
we have a time complexity of O(n 3 ).
To extend the algorithm to obtain the NFGs for a larger number of faults per CE,
we perform a multi-coloring where each vertex has a chromaticity of t l . The coloring
for a processor P j is stored in the array If at least one of the colors
indicates faultiness then P j is considered faulty. If all colors show "non-faulty" then P j
must be non-faulty. In any other case we have a "don't care'' state since there still exist
possibilities to change the fault status of the component. The multi-color algorithm is
given in Figure 4.
Theorem 3.2 The time complexity of the multi-coloring algorithm for finding one NFG
for an arbitrary P is O(n 2 ).
Proof: The loop in the first part of the algorithm examines at most n processors in
P. Coloring all adjacent vertices in the augmented graph takes at most n steps, giving
for the first part of the algorithm, not considering the time it takes
to set up the augmented graph. The second part takes at most n \Delta t l steps for determining
the fault status. Thus, the overall complexity of the algorithm is O(n
not considering the time to generate the augmented graph.
To determine a permissible fault distribution for the entire network, we can use the
first part of the algorithm given in Figure 4; we select an arbitrary processor to become
faulty, and keep labeling the NFGs, selecting new faulty components, until there are no
undefined labels left for any processor P j . The fault distribution is
obtained by determining faulty and non-faulty processors according to the second part
of the algorithm in 4.

Figure

5 shows an example for a 2-coloring, i.e., t l = 2. The dashed lines show the
augmentation of each CE. The other edges are the actual links in the network and are
not of importance at this stage. The CEs for the processors are as follows: CE(1)=1,2,3,
CE(2)=1,2, CE(3)=1,2,3, CE(4)=3,4,5, CE(5)=3,5,7, CE(6)=3,4,5,6, and CE(7)=3,5,7.
Selecting 1 to be faulty in the first pass will cause 2 and 3 to be labeled non-faulty since
for i:=1 to jPj /* examine the set of faulty processors P */
is the ith element in P */
color P j as faulty in color(j,i);
all processors which are in a CE with P j are adjacent in the augmented graph */
adjacent to P j in augmented graph)(color P k as non-faulty in color(k,i));
end for
/* determine the fault status of each processor */
for j:=1 to n
for i:=1 to t l
end for
end for

Figure

4: An algorithm to determine the NFG of a set P of faulty processors and arbitrary
t l .
they are adjacent to 1 in the augmented graph (dashed lines). Then arbitrarily node 5
is chosen to be faulty, forcing 4, 6 and 7 to become non-faulty. Note that, although 5
is adjacent to a faulty node 1 in the original graph, it is not adjacent in the augmented
graph since 1 and 5 don't communicate.
When all color(j,1) labels for all processors j have been filled, in a second pass an
arbitrary node is considered faulty. This time node 3 is selected. Because all vertices
are adjacent to 3 in the augmented graph, all of them must be colored non-faulty in
color(j,2). This provides a total of three faulty processors, 1, 3 and 5 with at most 2
faulty components in each CE. Components 2, 4, 6 and 7 are non-faulty.
Theorem 3.3 The time complexity for finding a possible fault distribution using the
multi-coloring algorithm is O(t l \Delta n 3 ).
Proof: From Theorem 3.1 it takes O(n 2 ) steps to find the NFG of one faulty processor.
When determining a fault distribution for the whole topology, the vertices are colored
until all variables color(j,i) have values assigned to them. In the first round, one node is
arbitrarily selected to be faulty and its NFG is colored. Next an unmarked processor is
colored faulty, then we find its NFG and mark it correspondingly. This process is repeated
until all variables have been assigned values. Thus it takes O(n 3 ) steps to fill one set of
variables color(j,i), where 1 . The coloring process is performed t l times until
all are colored. The determination of the fault status of each processor
is done according to the second part of the multi-coloring algorithm with complexity
O(n Thus, the complexity of finding a possible fault distribution is O(t l \Delta n 3 ).
We now present the NFGs of the processors such that they help in determining the
maximal fault index of an MPS. There are only three different processor states for each
F/N
F/N

Figure

5: A multi-coloring for t in an augmented graph.
processor with respect to a specific NFG: faulty, non-faulty, or don't care. We will use a
matrix representation.
Definition 3.1 A fault matrix of an MPS gives, for all sets of faulty processors P, all
processors that must be non-faulty (indicated by the logical value F in the matrix) if the
elements in P are faulty. The faulty processors are marked by T, the processors outside
the non-fault group are marked by "-". A fault matrix corresponds to a collection of NFGs
for a specific t l .
For exists only one NFG per processor. For t l ? 1 several different NFGs
may be found since up to t l processors can be faulty in each CE and many combinations
exist. The representation in Figure 6 shows the setup of the fault matrix for a 5x5
torus-connected mesh, where all adjacent processors communicate, i.e., the star pattern
introduced in Section 1. The mesh is labeled row by row from left to right, starting with
node 1 at the top left corner, ending at node 25 at the bottom right.
Providing Maximal Fault Tolerance
Determining the CEs and NFGs of the different processors finds the largest collection of
component failures within a topology such that the algorithm can still detect all errors
induced by these failures. We stated earlier that we examine algorithms with a local fault
tolerance of t l . We now define the minimum and maximum number of faults that can be
tolerated simultaneously in an arbitrary topology using an error-detecting algorithm.
Trivially, the minimal fault index of a topology with respect to an algorithm that is
able to tolerate t l local faults is t l , the local fault tolerance.

Figure

Fault matrices for a 5x5 torus-connected mesh and the star communication
pattern.
Definition 4.1 The maximal fault index (MFI) of a topology with respect to an algorithm
that is able to tolerate t l local faults is the number of failures t g that can occur such
that
is maximal
Definition 4.2 The fault tolerance decision problem (FTD) determines if a total of t g
faults can be tolerated. It specifically checks the assignments for the different processors
to give an answer to the following question:
For a given t l and t g , does there exist an assignment of FGs such that
The solution of the FTD depends on the network topology as well as the communication
patterns. As in the matrix representation, we use a logical representation for
faulty and non-faulty processors. Each row in the fault matrix represents a logical expression
where "faulty" is T, "non-faulty" is F, and the "don't care'' terms are not
mentioned. Thus, for example, the first row in Figure 6, which provides NFG(P 1 ) in a
5x5 torus-connected mesh for t l = 1, corresponds to
This statement must be true if we know that P 1 is faulty and we have t l = 1 to guarantee
that an error-detecting algorithm can detect all errors caused by the faulty processor.
To solve the FTD of an arbitrary topology for a fixed t l and t g , we essentially want to
determine if there exists a set of t l terms represented by the rows of the fault matrix that
can be true simultaneously. In the example given above for the 5x5 mesh and t l = 1, if
possibly faulty processor could for example be P 8 , since the entry
in the row that indicates NFG(P 1 ) is a "don't care''. In the next step we then evaluate
how the faultiness of P 8 influences where other faulty processors may be located.
To determine if the assignments of truth values to the processor states permits the
detection of all errors, we examine whether the NFGs of all faulty processors match, i.e.,
the conjunction of all processor states as indicated in the corresponding rows of the fault
matrix must be true for the rows of all sets of faulty processors P. We therefore check
the rows in the appropriate fault matrix where
The time needed to determine if this is possible, for a specific assignment of logical
values, is O(n 2 ), i.e. polynomial. To then solve the FTD we check all possible 2 n
assignments and evaluate each one of them to select the one(s) which permit the number
of simultaneously faulty processors to be t g .
A non-deterministic algorithm can guess a correct assignment if we need to determine
whether the FTD of a certain topology is equal to t g for a fixed t l .
Lemma 4.1 The FTD problem is in NP.
Proof: Using a non-deterministic algorithm we can find an assignment to the processors
in polynomial time (see Theorem 3.3) that can tell if the FTD provides a result such
that the MFI is equal to some value t g . Thus FTD is in NP.
Lemma 4.2 A variant of the 0,1 integer programming problem in which all components
of ~y are required to be in 0,1, called 0,1-integer programming, which is NP-complete, even
if all components of each ~x, b and all components of ~c are required to be in 0,1 [5], can
be reduced to the FTD problem in polynomial time.
The proof for Lemma 4.2 is given in [18]. Basically, for our case, ~y provides the entries
in the fault matrix, b indicates the number of faults that can be tolerated for each CE
(this value may vary for each CE but frequently l for all entries), and ~c gives the
solution vector for the rows in the fault matrix which can all be satisfied simultaneously.
In the solution, ~c has a 1-entry for each processor that has been selected for the optimal
fault distribution.
Theorem 4.1 The FTD problem is NP-complete.
Proof: The proof follows directly from Lemmas 4.1 and 4.2.
Corollary 4.1 The MFI problem is NP-hard.
Proof: To determine the maximalpossible value of faulty components, we need to solve
the 0,1-integer programming problem which is described by the FTD. This determines
whether there exists a number of faulty processors - t g , where t g is an arbitrary integer
are t g 1-entries in the solution vector ~c. We can thus solve the
FTD at most (n-t l ) times to find the maximal value since t l is the minimal fault index,
and n is the theoretical maximum. Thus, MFI can be obtained from the FTD through a
polynomial number of steps and is therefore NP-hard.
Definition 4.3 A processor group, K, describes a collection of processes whose simultaneous
failure still permits all errors caused by their failure to be detected. Processor
groups can be mapped disjointly onto the actual processor topology.
Corollary 4.2 Partitioning of the individual processes onto processor groups based on
an optimal fault distribution can be obtained in polynomial time from the solution of the
MFI.
Proof: Instead of equating each process with its own processor, we now consider each
process individually and try to partition all n processes onto a smaller number of m
processor groups. We use the solution of the MFI which provides an optimal distribution
of processor faults by providing the solution vector ~c for the fault matrix, indicating
which processes may simultaneously be faulty. The NFG of each process indicates which
other processes may not be located together on the same processor. The algorithm of

Figure

7 provides a partitioning of the processes P i to the processor groups K j . This
process is clearly polynomial.
An example for the mapping is given in Section 5.1.2 for the star pattern.
5 Finding The Maximal Fault Index For Fixed Topologie

Although determining an optimal distribution of faults is NP-hard for arbitrary graphs,
this is not necessarily true for certain regular topologies and regular communication pat-
terns. For example, in nearest neighbor algorithms, each processor and its neighbors form
a communication environment. In some cases, it is possible to determine the maximal
NFG overlap by inspection.
The topologies evaluated in this section are 2-dimensional torus-connected meshes and
binary hypercubes to provide the underlying interconnection network for error-detecting
algorithms using regular communication patterns and t l = 1. We will use compass
coordinates to describe adjacency of processes.
5.1 MFI for Meshes
Because of the symmetry of the topology, we examine only torus-connected meshes. The
distribution of faulty components for meshes without wrap-around connections is similar
but less restrictive since the wrap-around connections don't have to be considered.
/* All K i are processor groups to which the individual processes are mapped.
The 1-entries in the solution vector ~c of the MFI are mapped to K 0 ,
all remaining processes are mapped onto the other K
do
if c[i]=1 then
end for
Now distribute the remaining processes onto other processor groups: We cannot
map a process into a group where it would be in the NFG of one of the other elements
that are already mapped there. If no such group exists, a new one is created. */
l :=
K l :=;
for mapped
Km
else
l
K l := j;
end for
end for

Figure

7: An algorithm to provide a mapping from the results of the FTD.
5.1.1 Square Pattern
The first communication pattern evaluated is communication in a "square". The communication
environment for P is the set of processors PE , P S , and P SE (see Figure 8, left
part).
We can see from the augmented graph that P is also part of CE(PNW
CE(PN ) due to adjacency. The pattern containing all processors in these CEs is, thus, a
3x3 processor group in which P is located at the center (see Figure 8, center). For t
and P faulty, this is determined by the coloring algorithm of Section 3 as NFG(P ).
The maximal fault index places as many faulty processors as possible into the mesh.
It is apparent, that for meshes smaller than 3x3 the MFI will be t l . For an arbitrary
torus-connected mesh, with t l = 1, the MFI can be determined by
which gives the maximal possible number of faulty processors dependent on the number of
rows and columns in the mesh. From Figure 8 one can see that all faulty processors must
x
x
x
x
x
x
x
x
x

Figure

8: The "square" communication pattern, its NFG, and an optimal fault distribution
in a torus-connected mesh (wrap-around not shown).
be at least a distance of two away from a known faulty processor. Since P is, optimally,
exactly two away from the closest faulty neighbor, we can place up to div(m; 2) into
every other row and up to div(n; 2) into every other column, which will give the result
indicated above. A particular distribution is given in Figure 8 (right). Of course, if a
larger number of processors is available, the processes on the 4 processors can be divided
and placed onto the additional processors.
Partitioning the individual processes onto a smaller set of processors for the square
pattern has already been shown as an example in Section 1, Figure 2. The minimum
number of processors required is 4, and the partitioning is obtained by placing non-overlapping
CEs over the set of all processes, as described in Figure 2(c).
5.1.2 Star Pattern
Communication with all neighbors is another common communication pattern. In this
case, a processor P communicates with PE , PW , PN , and P S . The augmented CE is
shown in Figure 9 (top left). We will discuss this pattern again in Section 6 for the
evaluation of a relaxation algorithm.
As before, the goal is to permit as many faulty components as possible in the mesh
but guaranteeing at the same time that each communication environment contains at
most t l faulty processors. To determine the NFG for each individually faulty processor
we will again use the augmented graph and the coloring algorithm for finding the MFI.
We examine the case t l = 1, where at most one fault can be tolerated in each CE. In
this case the NFG for a faulty P as provided by the coloring algorithm on the augmented
graph will result in a "star" pattern (Figure 9, top right). For P faulty and t l = 1, none
of these processors must be faulty.
In the ideal case we obtain a distribution of faulty processors that is identical to the
perfect 1-adjacency placement of resources, where each non-resource node is adjacent to
exactly one resource [16], which in our case is a faulty component. [16] show that the
number of resource nodes in a k-ary n-cube for perfect 1-adjacency is
4,0 . 4,4
x
x
x
x
x
0,0 . 0,4
0,4 1,1 2,3
0,2 1,4 2,1
0,3 1,0 2,2

Figure

9: The "star" communication pattern, its NFG, an optimal fault distribution, in
a torus-connected mesh (wrap-around not shown), and the fault-tolerant mapping.
which must be an integer. From this expression one can see that perfect 1-adjacency
does not always exist, but there is a bound on the number of faulty processors that can
be permitted. A torus-connected mesh is a k-ary 2-cube, if we can guarantee that we
have only k \Theta k meshes. In this case the expression above becomes
which allows for up to 5 faulty components in a 5x5 torus-connected mesh. A possible
distribution for this example is shown in Figure 9 (bottom left).
A fault-tolerant mapping for this particular communication pattern is given in Figure
9 (bottom right). Based on an optimal distribution of faults obtained earlier, the
processes are placed such that only non-interfering processes are placed onto the same
processor. The solution vector, ~c, that was obtained from solving for the optimal fault
distribution for this particular problem is [1,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,1,0],
i.e., vertices (0,0), (1,2), (2,4), (3,1), and (4,3) in the problem graph can be simultaneously
faulty.
5.2 MFI for Binary Hypercubes
For binary hypercubes we are also frequently interested in communication patterns that
communicate with adjacent processors only, i.e., into all dimensions of the hypercube.
To determine the maximal fault index for this topology we use a similar approach as
in Section 5.1. The problem becomes harder since the patterns formed by the NFGs
are multi-dimensional and are therefore difficult to place by inspection, especially for
high-dimensional hypercubes.
To obtain a star-like pattern, as described in Section 5.1.2, the faulty processors in the
mesh as well as in the hypercube have to be at least a distance of three away from each
other. In order to find a set of processors in the hypercube which all have this property,
we can label the vertices of an n-dimensional hypercube in a binary gray code and then
use Hamming codes to find the number of processors B(n; d) which are a distance of d
apart from each other. Specifically, for
according to [7]. This provides an upper bound for the maximal fault index. An example
for a 3-cube where a set of two faulty nodes which do not interfere with each others'
computations and communications are marked is given in Figure 10 (left). A fault-tolerant
mapping of the nodes onto a smaller set of processors is given in Figure 10
(right).
6 A Specific Example of an Error-Detecting Algorith

Error-detecting algorithms work by checking, at run time, for hardware, communication
[10], and software errors [14]. These algorithms can be generated by using executable
a) optimal fault distribution b) fault-tolerant mapping
based on the distribution

Figure

10: MFI and fault-tolerant mapping for nearest neighbor communication in a
3-cube.
assertions for error detection [12], [1]. Assertions can, for example, be obtained from
program verification. A properly chosen set of assertions guarantees that, when operationally
evaluated, such as in Changeling [12], the program meets its specifications or
an error will be flagged. In general, we add executable assertions after each statement,
which then verify that the previous statement was executed correctly. In case of an error,
the assertions can force the program to halt execution to indicate the faulty condition.
For a specific problem and interconnection network, an error-detecting algorithm is
able to handle a bounded number and particular distribution of failures. If this bound
is exceeded or the distribution of faults is violated, the executable assertions may not be
able to correctly detect all errors since multiple faults can mask each other.
In this section we discuss how the concepts described in the previous sections can be
used to assess the fault tolerance of an error-detecting algorithm for matrix relaxation.
6.1 Iterative Relaxation
Iterative relaxation is one of the fundamental computation methods. Relaxation can
be used in such diverse problem ranging from relaxation labeling [9] in distributed scene
analysis to computational partial differential equation solvers [14]. We present the general
problem as approximating a solution to a large sparse system of linear equations
is the solution vector for perfect square. The method of
Gauss-Seidel Relaxation is an iterative technique used to obtain an approximate solution,
is the final iteration, to this system. The desired topology
of the interconnection network for this computation is a two-dimensional mesh. The data
exchange pattern for this algorithm corresponds to a communication with all adjacent
processors in the mesh, which we described in Section 5.1.2 as the star pattern.
6.2 Error-Detecting Matrix Relaxation
Using Changeling [12], a program verification proof outline based on axiomatic semantics
2 is used to construct an error-detecting matrix relaxation.
For the purposes of this paper, we choose to concentrate on only one assertion from the
matrix relaxation algorithm, which shows that at some final iteration step K, we have actually
solved the original problem and found a solution. Simply put, this (post)assertion
appears as
which ensures that the result obtained has converged on all nodes to within the desired
tolerance ffl. If the problem was solved correctly then the post assertion must hold;
otherwise an error occurred which must be flagged.
The distributed program runs in two phases: in the first phase an iterative algorithm
converges to a possible solution. Then a second phase, the verification of the solution,
is used to check whether the post assertion is satisfied for all processes, i.e., whether the
solution meets the desired specifications. If it does not, then we know that a fault must
have occurred during the computation or during the verification process, indicating that
the result cannot be trusted.
At the end of the final iteration K of the relaxation algorithm, the final result u (K)
must satisfy the following relation:
For
a i;j u (K)
To verify the post assertion, each process will send its last computed value of u (K)
j to the
other members of its CE using message diffusion 3 [2].
By checking the different versions that arrive on these paths [12], each processor
in the CE must receive identical versions of a sent message or will detect an error if
inconsistencies between messages from the same sender are discovered.
The system of equations to be solved by the relaxation algorithm has a unique so-
lution. If two faulty processors in the same CE cooperate to fool the other processors
then a spurious solution may be introduced which does not provide a correct solution
to the problem but which cannot be detected. For example, consider solving
the Laplace equation @u 2
solution for this can be obtained by solving
which corresponds to the rows in a sparse matrix.
What we actually verify in the postcondition is that for each CE the following relation
between the local values of its components will be satisfied:
For example,
satisfies this condition when locally tested in the CE. It is easy to see that a single
statements about the effect of executing a program. Assertions
are made about program variables before, during and after program execution.
3 Message diffusion uses node-disjoint paths for sending at least two messages to the same destination,
which can then be compared for consistency.

Figure

11: The Star Pattern with 2 cooperating errors in the same CE.
x
x
x
x

Figure

12: The communication pattern for message diffusion and a possible fault distribution

component with a faulty value that violates the bound can always be detected. However,
two faulty components can be faulty such that their errors add up without violating the
bound (for example, 2:5), or they could cooperate by switching
their values. If the components are not forced to use the same value in the verification
round for all CEs in which they participate, then they could provide a correct value for
the CEs in which they are the only faulty component and cooperate with another faulty
component in the ones in which more than one is faulty. The CE for this example is
shown in Figure 11. Thus, the verification round of the algorithm allows for t l = 1, i.e.
every single error in a CE can be detected.
The actual communication pattern used in this matrix relaxation is an extended form
of the star pattern to allow for message diffusion by providing node-disjoint paths from
P to the components in the corners (Figure 12). Since the assertions can reliably detect
up to one fault in each CE (t l = 1), the upper bound on the number of faults that are
permitted, the MFI, in a Q \Theta Q mesh can be calculated as Q 2 =9. Note that many different
distributions of the faulty components are possible, as long as the condition of at most
one faulty component per CE is not violated.
A possible fault-tolerant mapping is very similar to the one described in Section 1
as an example. We have 9 processor groups and map the individual processes according
to (using an x-y coordinate system): Process i;j maps into group K l;m if i mod
assuming that we have no wrap-around connections.
7 Conclusion
In this paper, the maximal fault index was introduced to demonstrate how a maximal
number of simultaneous component failures can be tolerated by an error-detecting algo-
rithm, based on specific distributions of the faults within the interconnection network.
Depending on individual or sets of component failures, the non-fault groups of these
components indicate where non-faulty components have to be located for the system to
be able to detect all errors.
Although solving the maximal fault index problem for an arbitrary network topology
and communication pattern is NP-hard, bounds are given in this paper for specific,
frequently used communication patterns and topologies.
Based on the "optimal" distribution of faults, a partitioning technique can be used
to assign processes to the processor groups in the system such that processes that may
become faulty simultaneously, without their errors being able to mask one another, are
located in the same processor group. These groups can then be mapped, disjointly, into
the actual processor topology. Thus, the failure of a single processor will still allow for
the detection of all errors.
The assessment of an error-detecting algorithm based on the concept of its minimal
and maximal fault index can be used for safety critical systems, especially with respect
to the fault-tolerant process-to-processor mapping that can be obtained from it. It will
ensure that the failure of a single component does not go undetected, which increases the
dependability of the system.



--R

Using executable assertions for testing and fault tolerance.
Atomic broadcast: From simple message diffusion to byzantine agreement.
The torus routing chip.
Graceful degradable processor arrays.
Computers and Intractability: A Guide to the Theory of NP-Completeness
Determining performance measures of algorithm-based fault-tolerant systems
detecting and error correcting codes.
A graph model for fault-tolerant computing systems
On the foundations of relaxation labeling processes.



Reliable parallel processing: The application-oriented paradigm
Executable assertion development for the distributed parallel environment.
Reliable distributed sorting through the application-oriented fault tolerance paradigm
Resource placement in k-ary n-cubes
The diogenes approach to testable fault-tolerant arrays of processors
A general method for maximizing the error-detecting ability of distributed algorithms
--TR
error detection;architecture;fault tolerance;mapping;fault-tolerant algorithms;multicomputers