Replicated Process Allocation for Load Distribution in Fault-Tolerant Multicomputers.
AbstractIn this paper, we consider a load-balancing process allocation method for fault-tolerant multicomputer systems that balances the load before as well as after faults start to degrade the performance of the system. In order to be able to tolerate a single fault, each process (primary process) is duplicated (i.e., has a backup process). The backup process executes on a different processor from the primary, checkpointing the primary process and recovering the process if the primary process fails. In this paper, we formalize the problem of load-balancing process allocation and propose a new process allocation method and analyze the performance of the proposed method. Simulations are used to compare the proposed method with a process allocation method that does not take into account the different load characteristics of the primary and backup processes. While both methods perform well before the occurrence of a fault, only the proposed method maintains a balanced load after the occurrence of such a fault.
INTRODUCTION
PROCESS allocation in fault-tolerant multicomputer systems has
been studied by several researchers [1], [2], [3]. Nieuwenhuis [1]
studied transformation rules which transform an allocation of non-duplicated
processes into an allocation of duplicated processes.
The transformed allocation is proven optimal in terms of reliabil-
ity. Shatz and Wang [2] proposed a process allocation algorithm
which maximizes the reliability of nonhomogeneous systems.
Bannister and Trivedi [3] proposed a process allocation algorithm
which evenly distributes the load of the system to all nodes. A
common assumption of all of the above research works is that each
duplicated process is not only a complete replica of the original
process, but also has the same execution load as the original. This
kind of fault-tolerant process is called an active process replica [4].
The fault-tolerant computing process model considered in this
paper is the primary-backup process model, which is commonly
used in distributed experimental and commercial systems such as
Delta-4 and Tandem [5], [6], [7]. In this model, there is a backup
copy for each process in the system. However, only one process in
a pair is running actively at any one time. The active process is
called the primary process and the nonactive process is called the
backup (or secondary) process. The active process regularly
checkpoints its running state to the backup process. During normal
operation, the nonactive backup process is either waiting for a
checkpointing message or saving a received checkpointing mes-
sage. When the node in which the primary process is running becomes
faulty, the backup process takes over the role of the primary
process. Thus, in order to be able to tolerate faults, primary and
backup processes should not be executed on the same node. This
kind of fault-tolerant process is called a passive process replica [6].
The difference between the computing model considered here
and the models considered in other research is in the role of the
backup processes. In the previous research, it is assumed that
backup processes are exact copies of the primary process. Hence,
the load of the backup process is exactly the same as the primary
process, whereas the load of the backup process in our model is
much less than that of the primary process, i.e., percent of
the load of the primary process.
In this paper, we study the problem of static load-balancing
process allocation for fault-tolerant multicomputer systems. Process
allocation is called static when all processes are allocated at the
beginning by the system. Dynamic process allocation assumes that
processes are allocated as soon as they arrive. In the general computing
environment where the occurrence, load, and duration of
processes cannot be predicted in advance, dynamic process allocation
is more suitable than static process allocation since dynamic
process allocation allocates processes as they arrive, taking into
consideration the current load of each processor. Static process
allocation, on the other hand, can be used most effectively in those
systems in which the computational requirement of each process is
known beforehand. Examples of such systems include on-line
transaction processing and real-time systems, in which most processes
are running continuously or repeating in a periodic manner.
Very few works stressed the dynamic process allocation problem
in the passive replica computing environment with load bal-
ancing. In the distributed system Paralex [8], which supports the
fault-tolerance by passive replication, loads are balanced dynamically
by the "late binding" of primary processes. Such kind of dynamic
allocation is convenient when a system has no previous
information about arriving processes and their load information.
The previous static process allocation algorithms [1], [3], which
were proposed for the active replica computing environment, exhibit
poor performance in the passive replica computing environment
since they were designed either to have maximum reliability
or to run with the assumption that the load of the backup process
is exactly the same as the primary. To achieve load-balancing with
the given computing model, we have to consider the distribution
of primary and backup processes and the load increment to be
added to each nonfaulty node in the event of a fault.
This paper is organized as follows. The next section presents
mathematical formulations for the allocation problem and shows
that it is NP-hard. In Section 3, basic primitives for allocating processes
are addressed and a heuristic process allocation algorithm is
given to solve the problem defined in Section 2. Section 4 analyzes
the expected performance of the proposed allocation algorithm
and compares the performance of the algorithm with another allocation
method. Finally, in Section 5, we summarize and discuss the
significance of our results.
2.1 System Model
The fault-tolerant multicomputer system considered in this paper
consists of n nodes (processors). To tolerate a fault, each process is
replicated and executed as a pair, referred to as a primary-backup
process pair. In this paper, we shall consider the possibility of a
single node failure only. However, by using more backup proc-
esses, the model can be extended to allow more than one fault [9].
Primary processes can be allocated to any node. However, there is
one restriction on the placement of backup process. That is, the
primary and backup processes cannot be allocated to the same
node. It is assumed that there are m primary processes running in
. J. Kim and H. Lee are with the Department of Computer Science and Engineer-
ing, Pohang University of Science and Technology, San 31 Hyoja Dong, Pohang
790-784, Korea. E-mail: {jkim,heejo}@postech.ac.kr.
. S. Lee is with the Department of Electrical Engineering, Pohang University of
Science and Technology, San 31 Hyoja Dong, Pohang 790-784, Korea.
Manuscript received 31 Aug. 1995; revised
For information on obtaining reprints of this article, please send e-mail to:
transcom@computer.org, and reference IEEECS Log Number C96308.
the system and that the cpu loads of the primary and backup processes
are known in advance. This assumption about the load requirement
is not unrealistic since many on-line transaction systems
run the same processes continuously [5]. Fig. 1 shows a fault-tolerant
multicomputer system with processes running on the
system.
Fig. 1. Primary-backup processes running in the fault-tolerant multi-computer
system.
The primary-backup process model considered in this paper is
actually used in experimental and commercial systems [5], [6], [7]
such as the Tandem Nonstop system [5]. In the Nonstop system,
every process has an identical backup process which is allocated to a
different node. The backup process is not executed concurrently
with the primary process, but is in an inactive mode, prepared to
assume the function of the primary process in the event of a primary
process failure. To guarantee that the backup process has the information
necessary to execute the required function, the primary process
sends periodic checkpoint messages to its backup process. In the
fault-free situation, the cpu load of the backup processes is much less
than that of their respective primaries. The actual load of a backup
process is determined by the interval and number of checkpoint
messages sent by the primary process. Each backup process has a
different percentage of the primary process's cpu load. When a fault
occurs, the backup processes of the primary processes which were
running on the faulty node take over the role of the primary proc-
esses. The backup process is executed continuously starting from the
last point at which it received a valid checkpointing message from its
primary process. Therefore, the cpu load of the backup process becomes
the same as that of its primary.
Load-balancing is required to utilize system resources evenly,
thereby enhancing the performance of the system. It has been reported
that the approximation algorithm proposed by Bannister
and Trivedi [3] has a near-optimal load-balancing result if backup
processes have the same cpu load as their primaries. However, in
the situation where the cpu load of a backup process is different
before and after the occurrence of a fault, the system does not
maintain a balanced load after a fault as the cpu loads of the newly
activated backup processes increase.
The load-balancing process allocation problem considered here
is to find a static process allocation algorithm which balances the
cpu load of every node in the fault-free situation and also balances
the cpu load when there is a fault in the system. The algorithm
should consider the cpu load increment of each node in the event
of a fault. In general, it is impossible for all nodes to have exactly
the same cpu load. Thus, the quality of the load-balancing is
measured either by the deviation from the average of all proces-
sors' loads or by the load difference between the node with the
highest load and the node with the lightest load. As these parameters
approach zero, the system approaches a balanced load.
We consider a process allocation to be optimal (with respect to
load-balancing) if any change in the placement of processes leads
to a higher load-balancing measure.
2.2 Notation
The following notation is used to formulate the allocation problem.
n: number of nodes.
m: number of primary processes (m backup processes also exist).
load of primary process i.
load of backup process i.
primary process i is allocated to node j, 0 otherwise.
process i is allocated to node j, 0 otherwise.
node j has failed, 1 otherwise.
load increment to be added to node j when a fault occurs.
the kth group of backup processes of the primary processes
assigned to node j.
the sum of the load differences of the backup group B jk .
total load of node j.
set of processors' loads when node j has failed.
set of processors' loads with no faulty nodes.
set of processors' loads with one faulty node.
standard deviation of load set P.
difference between the maximum and the minimum load of
load set P.
Y: the objective cost function to be used.
2.3 Formal Problem Description
The load-balancing process allocation problem is represented as a
constrained optimization problem. Let us assume that there are n
nodes and m processes in the system. Because each primary process
has a backup process, the total number of primary and backup
processes is 2m. One prominent constraint is on the allocation of
primary-backup process pairs. To be able to tolerate a single fault
in a node, a primary process and its backup should not be allocated
to the same node. Thus,
, , . (2.1)
At this point, let us define a set $ with n
Each element A i (0 - i - n) is a processor status
vector of the form [a 1 a 2 - a n ], where a OE {0, 1} for all 1
is an all-one vector (all nodes are fault-free) and A k is the vector
with a (only node k is faulty).
The load increment to be added to node j in the event of a fault
in node k can be represented as
hThus, the total load increment for node j
t a
O
The load of node j, denoted as P(j), is the sum of the load before
the fault occurrence and the load increment (t ) to be incurred
upon the occurrence of a fault.
t. (2.3)
The commonly used metric for evaluating load-balance between
nodes is the standard deviation of the processor load [3].
The standard deviation (s) of the load when node k is faulty
can be represented as follows:
s a
a
a
O
where f represents the number of faulty nodes. The second term in
the bracket represents the average of P(j).
The number of backup processes becomes less than m when a
occurs. Therefore, the first and second expressions in (2.1) are
no longer valid when a fault occurs. In (2.4), the average load of
the live nodes is computed by dividing the total load by the number
of live nodes (n - f). Since we consider the possibility of only a
single fault, f is either 1 or 0.
Another metric that can be used in the load-balancing process
allocation problem is the load difference between the node with
the heaviest load and the node with the lightest load. The load
difference, denoted as F, for the given set of process loads P can be
represented as follows :
The set of process loads before a failure is represented as P non and the
set of process loads after any node failure is represented as P faulty .
In this paper, the load difference is used as the objective cost
function because of two reasons. First, the load difference reflects
the goal of load-balancing more closely than the standard devia-
tion. This is illustrated by the following two scenarios. In the first
scenario, one node has an exceptionally large load and all others
are slightly less loaded than the average of all nodes. In the second
scenario, some nodes are somewhat more loaded than the average
and other nodes are somewhat less loaded than the average. Suppose
that the standard deviations of both scenarios are the same,
while the load difference are different. In such a case, the latter
scenario is more preferable than the former, since there exists one
heavily overloaded node in the former scenario. The measurement
F will indicate that the latter scenario is better. The second reason
is that standard deviation requires more computation than load
difference.
The load-balancing process allocation problem is the problem
of finding values of x ij and y ij for all possible i and j which minimize
the multiple cost functions F(P non ) and F(P faulty ) with the
constraint given in (2.1). There are two main approaches to solving
an optimization problem that involves multiple objective functions
[10]. One approach is to solve the problem a number of times with
each objective in turn. When solving the problem using one of the
objective functions, the other objective functions are considered as
constraints. The other approach is to build a suitable linear combination
of all the objective functions and optimize the combination
function. In this case, it is necessary to attach a weight to each objective
function depending on its relative importance. In this pa-
per, the second approach is used to formulate the load-balancing
process allocation problem.
We define a new objective function Y as
are the relative weights of importance before and
after a fault occurrence, respectively. If we assume that the
weights have the same value, i.e., w the objective function
is
An optimal allocation is an assignment of processes that minimizes
the objective cost function Y.
2.4 Complexity of Optimal Allocation
Let us consider the following two set assignment problems, defined
as the k-grouping problem and the restricted grouping problem.
k-Grouping Problem Given m sets with k positively
weighted elements in each set, does there exist an assignment of
elements to k groups such that no two elements in the same set are
assigned to the same group, and each group has the same weight
sum?
Restricted Grouping Problem (RGP): Given n sets, A
a in }, a ii is assigned to the group G i , does there exist
an assignment of elements to n groups, G a a a
ng n
{ , , , }
1.n such that no two elements from the same set are assigned
to the same group and each group has the same weight sum?
THEOREM 1. k-GP is NP-Complete.
THEOREM 2. RGP is NP-Complete.
In this paper, the proofs for all theorems and lemmas have been
omitted due to lack of space. The interested reader can obtain the
proofs from [11].
The k-GP problem can be reduced to the fault-tolerant load-balancing
process allocation problem. Each of the m sets contains
one primary process and k - 1 backup processes, where the weight
of each element is the load of each process. Let us change the k-GP
problem by adding (n - sets and changing the grouping requirement
so that n groups are formed (recall that n is the number
of nodes). In each of the new (n - sets, the weight of the first
element is equal to the average of the k sets (the sum of the previous
mk element weights divided by k); the weights of the remaining
are assigned to 0. Then, if there is a solution to
this modified k-GP problem, there is a solution to the original k-GP
problem. Thus, since the modified k-GP problem can be shown to
be in NP, the modified k-GP problem is NP-complete. This modified
k-GP problem is equivalent to the load balancing problem
with processes. Thus, it follows that the problem of
minimizing F(P non ), is also NP-hard-which in turn implies that
the problem of minizing Y is NP-hard. Hence, we propose a heuristic
approximation algorithm which is cost-effective and results
in a well balanced processor load before and after the occurrence
of a fault.
In this section, we first present basic primitives for process allocation
which form the core of the algorithm. A heuristic algorithm is
presented with an example. Then the complexity of the proposed
algorithm is analyzed.
3.1 Basic Primitives of Process Allocation
In this section, it is assumed that processes are allocated one by
one, and, once allocated, processes are not reallocated to other
nodes. When we allocate processes one by one, there are three
questions we have to consider. First, is it better to assign a process
to a lightly loaded node rather than a heavily loaded node to
minimize F? Second, is it better to assign a process with less load
prior to a process with more load to minimize F? Third, when
there are two ordered sets with n elements and the two sets are
combined into one set by adding one element from each set, how
should the two sets be combined to minimize F? The following
lemmas will address these questions one by one.
LEMMA 1. If 0 -
that 1 < i - n.
Lemma 1 implies that a process should be allocated to a node
with the minimum load first to minimize F.
The function Alloc(P, x) represents the allocation of x to the
most lightly loaded node P(1) when P is an ordered set of n ele-
ments, i.e.,
Alloc(P,
LEMMA 2. For a given ordered set P of n elements and x # y # 0,
implies that processes with more load should be allocated
prior to processes with less load to minimize F.
LEMMA 3. Given two ordered sets of n elements, P 1 and P 2 , F is maximally
reduced when the two sets are merged by adding the element
with the largest weight from one set to the element with the smallest
weight from the other set, i.e., the merged unordered set P is
The above lemma implies that the merging of the two ordered
sets as proposed in the lemma does not increase the F of two ordered
sets.
3.2 Two-Stage Allocation
The proposed heuristic algorithm, which satisfies the allocation
primitives discussed above, works in two stages. In the first stage,
primary processes are allocated using a standard load balancing
algorithm. We used a greedy method which allocates the process
with the highest load to the node with the lowest load. As shown in
Lemmas 1 and 2, this method minimizes F. In the second stage,
backup processes are allocated considering the load increment to be
added to each node in the event of a fault. Let us assume that the
algorithm is currently working on node j. The backup processes
whose primary processes are assigned to node j are divided into
having approximately equal incremental load in the
event of a fault in node j. These (n - 1) groups of backup processes
are finally allocated to the (n - 1) nodes excluding the node j based
on the actual backup loads before the occurrence of a fault. This
allocation balances the total actual load of each node in the fault-free
situation. The grouping of backup processes according to the load
increment in the case of a fault balances the load if such a fault does
occur. The algorithm is formally described below.
Two-Stage Algorithm
Stage-l Allocate primary processes
primary processes in descending order of cpu load.
Allocate each primary process to the node with the minimum
load from the highest load to the lowest.
Allocate backup processes
Do the following steps for each node.
Compute the load difference between each primary process
and its backup process for all primary processes assigned to
the node.
Sort, in descending order, the backup processes using the
load difference.
Divide the backup processes into (n - 1) groups having approximately
equal incremental load by assigning each
backup process to the group with the smallest load, in the
order of the sorted list in the previous step.
Computer the actual backup process load of each group.
Do the following for the n(n - 1) backup groups which are generated
by the above steps.
groups using the actual loads in descending
order.
Sort the n nodes using their current loads in ascending order.
Allocate each backup group to the node with the minimum
load. However, if the backup group has a corresponding
primary processes in this node or if one of the backup
groups which are already allocated to this node comes from
the same node as the backup group to be allocated, choose
the node with the next-to-the-minimum load.
The allocation of backup processes is the most important part
of this algorithm. For each node, the backup processes are first
divided into (n - 1) groups using the load difference between each
primary process and its backup. This load difference is the amount
of load increment to be incurred upon the occurrence of a fault.
Next, the algorithm computes the actual load of each group using
the actual load of the backup processes. The total number of backup
groups is n(n - 1). Each group is assigned to nodes depending on its
actual load. When we allocate each backup group, we check whether
there is a pre-allocated backup group which comes from the same
node as the to-be allocated backup group. In such a case, we select
the node with the next-to-the-minimum load.
The purpose of dividing the backup processes into (n - 1) groups
for each node is to guarantee that each node has an approximately
equal amount of load increment. Hence, the system will have a
balanced load when a fault occurs. The purpose of computing the
actual load of each group and assigning groups based on their
actual loads is to guarantee that each processor's load is balanced
before the occurrence of a fault. Therefore, we can balance the
processor load before as well as after the occurrence of a fault.
The allocation of n(n - 1) backup process groups for load-balancing
is shown in Fig. 2. In this figure, B jk denotes one of the
groups of backup processes for the primary processes assigned to
node j. Hence, can be allocated to any node except
node j to tolerate a fault on the node j. The problem of allocating
grouped backup processes is the RGP problem which was
discussed in Section 2.4. Detailed example of running the two-stage
algorithm can be found in [12].
Fig. 2. Backup groups allocation problem.
3.3 Algorithm Complexity
The time complexity of each stage of our algorithm is analyzed as
follows.
. primary allocation
We can use a general sorting algorithm whose running time
is O(m log m) to sort m primary processes. Allocating m
primary processes to n nodes requires O(m log n) time. (This
is a process of updating the highest value m times in a priority
queue.)
. backup allocation
Let us consider the allocation with the worst execution time
in which most of the primary processes are assigned to one
node. Sorting the m backup processes takes O(m log m) time.
Dividing backup processes into (n - 1) groups having equal
incremental load and computing their actual loads takes
O(m log n m) time. The above grouping is repeated n
times, which requires O(n(m log
Sorting these n(n - 1) backup groups requires O(n 2 log n)
time. Sorting n nodes and finding the proper node to allocate
one of the n(n - 1) groups to requires O(n log n
time. Thus, allocating n(n-1) groups requires O(n(n - 1)
(n log n time. The time complexity of this stage is thus
Hence, the total time complexity of the two stage allocation algorithm
is
O(nm log nm
Assuming that the number of processes is much larger than the
number of nodes (m > n 2 ), the execution time is bounded by O(nm
log nm). This is a reasonable execution time for process allocation.
The time complexity obtained above is based on the worst case
scenario in which all primary processes are allocated to one node.
If we assume that all primary processes are evenly distributed, the
time complexity becomes O(m log m).
In this section, the performance of the two-stage algorithm is estimated
by analysis and compared with related work using simulation.
4.1 Expected Performance
The proposed allocation algorithm consists of three parts for load-
balancing. First, primary processes are allocated to nodes. Second,
the backup processes of each node are grouped on the basis of
their primary-backup load differences. Third, the backup process
groups are allocated to each node using their actual loads. The
following lemmas and theorems estimate the performance of the
proposed algorithm.
LEMMA 4. Given m primary processes with decreasing loads, the load
difference between the node with the heaviest load and the node
with the lightest load after the allocation of all primary processes
by the proposed algorithm is not more than the load of nth smallest
primary process, p m-n+1 .
LEMMA 5. The load difference between the node with the heaviest load
and the node with the lightest load in the allocation of backup
processes is bounded by
r
F
where r is the maximum ratio of a backup process load to its primary.
THEOREM 3. The expected performance of the proposed algorithm before
the occurrence of a fault is
non
F
F
r
r .
THEOREM 4. The objective cost function Y of the proposed algorithm is
F
F
c h
r
r
In the next subsection, we will show by comparison with
simulation that this bound can serve as a quick approximation to
the actual Y value.
4.2 Performance Comparison
In this subsection, we analyze the performance of the two-stage algorithm
using simulations. Note that there has been no previous
research on load-balancing with passive replicas. The closest re-search
of this kind is Bannister and Trivedi's work on load-balancing
with active replicas [3]. Thus, our algorithm will be compared to
Bannister and Trivedi's process allocation (BT) algorithm.
The BT algorithm in the active replica model works as follows.
For allocating n processes with r replication, sort all n processes in
descending order, and allocate the r replicas of each task to the r
least loaded nodes. Process allocation by the BT algorithm is
proven to be near-optimal under the assumption that backup
processes have exactly the same load as their primaries [3].
The BT algorithm is applied to the problem of load-balancing
with passive replicas as follows. First, all primary and backup
processes are sorted in descending order of their cpu load. Starting
from the highest load process, each process is allocated to the node
with the minimum load. When the node with the minimum load
in allocating a backup process is the node on which the primary
process has already been allocated, the backup process is allocated
to the node with the next smallest load.
The environment parameters used in the simulation are as fol-
lows. To keep the total load of each node below 100%, the load of
the primary processes are chosen randomly in the range of 0.2 to 2
times 100 # (n - 1)/m based on a uniform distribution. The load of
the backup processes are also chosen randomly between 5 , 10%
of the load of their primaries, also based on a uniform distribution.
Fig. 3 shows each node's load when processes are allocated using
the BT algorithm. It is assumed that the number of nodes (n) is eight.
The horizontal dotted line in the figure represents the average load
of a faulty system and the solid line represents the average load of a
fault-free system. The figure also shows the load difference of the
maximum and the minimum load when the number of primary
processes varies from 50 to 300. Fig. 4 shows the simulation results
using the two-stage allocation algorithm with the same parameters.
When the number of primary processes is 150, the load difference
between the maximum and the minimum load is approximately 2 ,
3% in Fig. 4. By contrast, Fig. 3 shows that the load difference between
the maximum and the minimum load is almost 25% of the
total load when the BT algorithm is used. The reason that the BT
algorithm shows such poor performance is that the allocation of
backup processes is done without considering the load variation
after the occurrence of a fault.
The load differences F between the minimum and the maximum
load before and after the occurrence of a fault is shown in Fig. 5 for
each algorithm. These results were obtained with nodes. The
upper two lines show F(P faulty ) for the two algorithms after a fault
has occurred in one node of the system and the lower two lines
show before the occurrence of the fault. It can be seen that
before the occurrence of a fault, F(P non ) using the two-stage allocation
algorithm is similar to that of the BT algorithm. However, after
the occurrence of a fault, F(P faulty ) using the two-stage allocation
algorithm is significantly less than that using the BT algorithm.
Next, we experimented with the effect of the number of nodes
in the system. The simulation was conducted by varying the number
of nodes while keeping the number of processes fixed. The
simulation results are shown in Fig. 6. In this and the following
figures, the simulation results before and after the fault occurrence
were combined and represented as Y, as shown in (2.6). The upper
two lines show the simulation results when the number of processes
is 200 and the lower two lines show the simulation results
when the number of processes is 400. Y increases as the number of
nodes increases. This result was expected since the number of
processes allocated to each node decreases as the number of nodes
increases when the number of processes is fixed. This figure again
shows that the two-stage allocation algorithm is significantly better
than the BT algorithm.
Fig. 7 shows the simulation results when the number of processes
is varied from 50 to 300 while the number of nodes is fixed at
eight. The upper line shows Y when the BT algorithm is used in
the simulation, the middle line is the upper bound of our algorithm
based on Theorem 4, and the lower line shows the simulated
result for the two-stage algorithm. As the number of processes
increases, Y decreases since the number of processes per node
increases. From this figure, we can confirm that it is easier to balance
the load of a system when there are many processes with
small loads rather than a few processes with large loads.
In the previous figures, we assumed that the backup processes
have 5 , 10% of the load of their primary processes. Next, we compare
the performance of the two algorithms by varying the load of
the backup processes from 10% to 100% of their primaries. For a
backup process load ratio r in Fig. 8, the load of the backup processes
was chosen randomly between 50r to 100r% of the primary
process load in order to provide some variance in the backup process
load. We tested for 200 processes with eight nodes, and for 400
processes with nodes. The two-stage allocation algorithm shows
better performance in Fig. 8. However, as the load of the backup
processes approaches 100% of the primary process load, both algorithms
have similar performance. In our simulation, 100% means
that a backup process has 50% , 100% of its primary process. This
Fig. 3. Minimum, maximum load using the BT algorithm.
Fig. 4. Minimum, maximum load using our algorithm.
Fig. 5. F before and after a fault occurrence.
Fig. 6. Y affected by the number of nodes.
Fig. 7. Y affected by the number of processes.
Fig. 8. Y affected by varying the load ratio r of backup processes.
result implies that the BT algorithm has better performance when a
backup process has the same load of its primary process.


AND CONCLUSION
A load-balancing static process allocation algorithm for fault-tolerant
multicomputer systems is proposed and analyzed. The fault-tolerant
process model considered in this paper is the passive process replica
model. The passive replica of a process is inactive during normal
operation and becomes active only when the main active process
becomes faulty or the node on which the active process was running
becomes faulty. The load of a passive replica varies before and after
the occurrence of a fault. The load-balancing problem with passive
replicas is formalized as a constrained optimization problem. Since
optimal process allocation is an NP-hard problem, a heuristic approximation
algorithm is proposed. The proposed algorithm is compared
with the load-balancing algorithm for active replicas proposed
by Bannister and Trivedi [3] using simulations. The simulation results
show that the proposed algorithm has significantly better performance
in the passive replica model. Also, it is shown that the
system has a better load balance if we can divide a "big load" process
into many "small load" processes.
The main contribution of this paper is the presentation and
analysis of a new static load-balancing algorithm for a passive
replica fault-tolerant process model. The proposed static process
allocation algorithm is applicable to on-line transaction processing
and real-time systems. We are currently working on extending this
algorithm to handle the dynamic situation. Also, we plan to study
the problem of finding an allocation algorithm which guarantees
optimal performance and reliability at the same time.

ACKNOWLEDGMENTS

This research was supported in part by KOSEF under Grant 941-
0900-055-2 and ETRI under Contract 94231. A preliminary version
of this paper was presented at the 25th FTCS.



--R

"Static Allocation of Process Replicas in Fault-Tolerant Computing Systems,"
"Task Allocation for Maximizing Reliability of Distributed Computer Systems,"
"Task Allocation in Fault-Tolerant Distributed Systems,"
"Active Replication in Delta-4,"
Reliable System Design: The Theory and Practice.
"Using Passive Replicates in Delta-4 to Provide Dependable Distributed Computing,"
"Transaction-Based Fault-Tolerant Computing in Distributed Systems,"
"Parallel Computing in Networks of Workstations with Paralex,"
"Fault-Tolerant Process Allocation with Load Balancing,"
Model Building in Mathematical Programming
"Load Balancing Process Allocation in Fault-Tolerant Multicomputers,"
"Process Allocation for Load Distribution in Fault-Tolerant Multicomputers,"
--TR

--CTR
J. Ray, Optimization of distributed, object-oriented systems, Addendum to the 2000 proceedings of the conference on Object-oriented programming, systems, languages, and applications (Addendum), p.153-154, January 2000, Minneapolis, Minnesota, United States
J. Ray , Luqi , Valdis Berzins, Optimizing systems by work schedules: (a stochastic approach), Proceedings of the 3rd international workshop on Software and performance, July 24-26, 2002, Rome, Italy
Sunggu Lee, Real-time wormhole channels, Journal of Parallel and Distributed Computing, v.63 n.3, p.299-311, March
fault-tolerant multicomputer;checkpointing;backup process;load balancing;process allocation