Open AccessCompletion Probabilities and Parallel Restart Strategies under an Imposed Deadline
Author(s) -
Jan-Hendrik Lorenz
Publication year - 2016
Publication title -
plos one
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.99
H-Index - 332
ISSN - 1932-6203
DOI - 10.1371/journal.pone.0164605
Subject(s) - running time , computer science , odds , upper and lower bounds , scale (ratio) , parallel computing , algorithm , mathematical optimization , mathematics , mathematical analysis , logistic regression , physics , quantum mechanics , machine learning
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.