Optimal Restart Times for Moments of Completion Times.pdf

Optimal Restart Times for Moments of Completion Time Aad van Moorsel1 and Katinka Wolter2 1 Go?lerstra?e 11, 12161 Berlin, Germany conferences@ 2 Humboldt-Universita?t zu Berlin, Institut fu?r Informatik, Unter den Linden 6, 10099 Berlin, Germany wolter@informatik.hu-berlin.de Abstract. Restart is an application-level technique that speeds up com- pletion for jobs with highly variable completion times. In this paper, we present an efficient iterative algorithm to determine the optimal restart strategy if there are a finite number of restarts, and if one is interested in minimising higher moments of the completion time. We demonstrate its computational efficiency in comparison with alternative algorithms. We also discuss fast approximations to determine close to optimal restart times for limiting cases. 1 Introduction The work in this paper applies to various forms of ‘restart,’ which simply implies that a task is retried after some time threshold has passed. Restart finds its application in areas ranging from randomised algorithms [2] to distributed data base queries [6], Internet agents [3] and software rejuvenation [1]. Probably the most commonly experienced restart mechanism is clicking the reload button of the web browser when a download takes too long. The basic form of restart can be conveniently modelled assuming that (1) successive downloads are statistically independent and identically distributed, and (2) new tries abort previous tries. Such model assumptions have been found realistic for Internet applications [3, 5]. Under these assumptions, we provide in this paper an efficient algorithm to determine the optimal time instances at which to initiate restarts, so that higher moments of completion time are minimised. As we showed in [4], the optimal restart strategy for unbounded number of restarts can be determined in straightforward manner, as can that for a finite number of restarts and the first moment. However, the combination of higher moments and fin