Expected performance of parallel search

Abstract

Consideration is given to problem-solving systems where a problem to be solved is expressed as a set of alternative tasks such that if any of the tasks is completed successfully, then the problem is considered solved. Execution of the task system consists of a search for a task that can execute successfully for a given input. Each task can terminate a search successfully with some probability. Under the assumption that the running times of tasks are independent, identically distributed random variables, specific results are derived on expected speedup due to parallelism for three runtime distributions: constant, exponential, and uniform.