Risky Search with Increasing Complexity by a Desktop Grid

A common problem solved by high-performance computing is a search problem, when the unique object needs to be found among other objects. With a huge number of objects to examine and computationally hard examination of each, the search problem requires a lot of computing resources. However, the problem becomes even harder if an examination might give the wrong results with some probability. Such problem appears in unreliable high-throughput computing environments like Desktop Grids. In this paper, we present a mathematical model of such search problems, derive the optimal strategy of task assignment that minimizes the expected cost of examinations and thus reduces consumption of computing resources. We show that in a rather general case the optimal strategy is the “no-replication” one, i.e., all objects should be examined once, then for the second time if no target has been obtained, etc. We reveal the cases when this strategy is not optimal. Also, the expected costs of finding the target are obtained for a practical case of object-dependent cost.