Completion Probabilities and Parallel Restart Strategies under an Imposed Deadline

Jan-Hendrik Lorenz

PLOS ONE, 2016, vol. 11, issue 10, 1-15

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.

Date: 2016
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0164605 (text/html)
https://journals.plos.org/plosone/article/file?id= ... 64605&type=printable (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:plo:pone00:0164605

DOI: 10.1371/journal.pone.0164605

Access Statistics for this article

More articles in PLOS ONE from Public Library of Science
Bibliographic data for series maintained by plosone ().