Discrete Mathematics & Theoretical Computer Science, Vol 14, No 1 (2012)

Font Size:  Small  Medium  Large

Optimal Computer Crash Performance Precaution

Efraim Laksman, Håkan Lennerstad, Lars Lundberg


For a parallel computer system with m identical computers, we study optimal performance precaution for one possible computer crash. We want to calculate the cost of crash precaution in the case of no crash. We thus define a tolerance level r meaning that we only tolerate that the completion time of a parallel program after a crash is at most a factor r + 1 larger than if we use optimal allocation on m - 1 computers. This is an r-dependent restriction of the set of allocations of a program. Then, what is the worst-case ratio of the optimal r-dependent completion time in the case of no crash and the unrestricted optimal completion time of the same parallel program? We denote the maximal ratio of completion times f(r,m) - i.e., the ratio for worst-case programs. In the paper we establish upper and lower bounds of the worst-case cost function f(r,m) and characterize worst-case programs.

Full Text: PDF PostScript