Our earlier paper introduced a parallel scheduling problem where a directed acyclic graph modeling t tasks and their dependencies needs to be executed on n unreliable workers. Worker i executes task j correctly with probability pi,j. The goal is to find a regimen Σ, that dictates how workers get assigned to tasks (possibly in parallel and redundantly) throughout execution, to minimize the expected completion time. The paper provided a polynomial time algorithm for the problem restricted to the case when dag width and the number of workers are at most a constant, and showed necessity of these restrictions, unless P=NP. The current paper describes algorithm engineering approaches used to produce an efficient implementation of the algorithm, and experiments demonstrating how the algorithm scales.
['Grzegorz Malewicz']
Implementation and experiments with an algorithm for parallel scheduling of complex dags under uncertainty