Task allocation in fault-tolerant distributed systems

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. © 1983 Springer-Verlag.

Duke Scholars

Author Kishor S. Trivedi Electrical and Computer Engineering