TASK AND FILE ALLOCATION IN FAULT-TOLERANT DISTRIBUTED SYSTEMS.

Task and file allocation are examined in two classes of fault-tolerant distributed systems. The task allocation problem arises in software-implemented fault tolerance (SIFT)-like systems, while the file allocation problem arises in Ethernet-like systems. Both problems may be formulated as a constrained sum of squares minimization problem. The computational complexity of these problems prompts us to consider an efficient approximation algorithm that does not always yield optimal answers. It is shown that the ratio of the approximate to the optimal solution is bounded by 9m/8(m minus r plus 1), where m is the number of processors (file servers) to be allocated and r is the number of times each task (file) is to be replicated. Experience with the algorithm suggests that ever better performance ratios can be expected.