Toward Maximizing the Quality of Results of Dependent Tasks Computed Unreliably

This paper studies the problem of maximizing the number of correct results of dependent tasks computed unreliably. We consider a distributed system composed of a reliable server that coordinates the computation of a massive number of unreliable workers. Any worker computes correctly with probability p < 1. Any incorrectly computed task corrupts all dependent tasks. The goal is to determine which tasks should be computed by the (reliable) server and which by the (unreliable) workers, and when, so as to maximize the expected number of correct results, under a constraint d on the computation time. This problem is motivated by distributed computing applications that persist partial results of computations for future use in other computations and that want to ensure that the persisted results are of high quality. We show that this optimization problem is NP-hard. Then we study optimal scheduling solutions for the mesh with the tightest deadline. We present combinatorial arguments that describe all optimal solutions for two ranges of values of worker reliability p, when p is close to zero and when p is close to one.