Task allocation in fault-tolerant distributed systems
Joseph A. Bannister1 and Kishor S. Trivedi2
| (1) | University of California, 90024 Los Angeles, CA, USA |
| (2) | Duke University, 27706 Durham, NC, USA |
Received: 13 May 1983
Summary This paper examines task allocation in fault-tolerant distributed systems. The problem is formulated as a constrained sum of squares minimization problem. The computational complexity of this problem prompts us to consider an efficient approximation algorithm. We show that the ratio of the performance of the approximation algorithm to that of the optimal solution is bounded by 9
m/(8
m–
r+1)), where
m is the number of processors to be allocated and
r is the number of times each task is to be replicated. Experience with the algorithm suggests that even better performance ratios can be expected.
List of Important Symbols
n
number of tasks to be assigned
-
m
number of processors to be allocated
-
x
ij
1 if taski is assigned to processorj
-
r
i
number of clones of taski
-
M
ij
units of memory space required by taski on processorj
-
B
j
units of memory space available on processorj
-
I
ij
number of instructions executed by taski per iteration on processorj
-
T
i
taski's period
-
R
j
speed of a processorj in instructions per second
-
u
ij
taski's utilization of processorj
-
f
i
scheduling constant (e.g. 1 or ln 2) for processorj
-
r
number of clones of a task assuming a fixed level of replication
-
q
j
utilization of processorj
-
q
j
*
utilization of processorj under an optimal assignment
- min-r
ther
th minimum of a sorted multiset
-
K
r
m
least upper bound on a family of series ratios
-
q
*(
t
)
used in computingK
r
*
This work was supported in part by the National Aeronautics and Space Administration under and by the National Science Foundation under Grant US NSF MCS-8302000
References secured to subscribers.