Redundant task-allocation in multicomputer systems

Author

Cherkassky, Vladimir ; Chen, Chien-In Henry

Author_Institution

Dept. of Electr. Eng., Minnesota Univ., Minneapolis, MN, USA

Volume

41

Issue

3

fYear

1992

fDate

9/1/1992 12:00:00 AM

Firstpage

336

Lastpage

342

Abstract

A simple yet effective method for improving multicomputer multiprocessor system reliability via redundant allocation of tasks to computers (processors) is described. Given any known (nonredundant) scheduling strategy, tasks are allocated to processors statically and redundantly using a k-circular shifting (KCS) algorithm. so that if some processors fail during the execution. all tasks can be completed on the remaining processors (but at a longer time). Redundant allocation of independent tasks to identical processors (computers), subject to real-time constraints on total execution time, is discussed in detail, and analytic reliability estimates are derived. The longest processing time scheduling is given as an example of nonredundant deterministic scheduling of independent tasks. Processor utilization for redundant task-allocation is discussed and compared with standby redundancy: the authors´ KCS algorithm achieves much higher processor utilization than standby redundancy

Keywords

fault tolerant computing; multiprocessing systems; redundancy; scheduling; KCS algorithm; analytic reliability estimates; fault tolerant systems; k-circular shifting; longest processing time scheduling; multicomputer multiprocessor system reliability; nonredundant deterministic scheduling; real-time constraints; redundant task-allocation; scheduling strategy; standby redundancy; total execution time; Degradation; Fault tolerant systems; Hardware; Multiprocessing systems; Parallel processing; Processor scheduling; Redundancy; Reliability; Scheduling algorithm; Throughput;

fLanguage

English

Journal_Title

Reliability, IEEE Transactions on

Publisher

ieee

ISSN

0018-9529

Type

jour

DOI

10.1109/24.159795

Filename

159795