title: Completion Probabilities and Parallel Restart Strategies under an Imposed Deadline.
abstract: Let A be any fixed cut-off restart algorithm running in parallel on multiple processors. If the algorithm is only allowed to run for up to time D, then it is no longer guaranteed that a result can be found. In this case, the probability of finding a solution within the time D becomes a measure for the quality of the algorithm. In this paper we address this issue and provide upper and lower bounds for the probability of A finding a solution before a deadline passes under varying assumptions. We also show that the optimal restart times for a fixed cut-off algorithm running in parallel is identical for the optimal restart times for the algorithm running on a single processor. Finally, we conclude that the odds of finding a solution scale superlinearly in the number of processors.
authors.affiliation: Institut für Theoretische Informatik, Universität Ulm, 89069 Ulm, Germany.
authors.forename: Jan-Hendrik
authors.initials: JH
authors.lastname: Lorenz
mesh_terms: D000465:Algorithms; D003201:Computers; D016017:Odds Ratio; D011336:Probability; D013997:Time Factors