  We propose a new black-box complexity model for search algorithms evaluating
$\lambda$ search points in parallel. The parallel unary unbiased black-box
complexity gives lower bounds on the number of function evaluations every
parallel unary unbiased black-box algorithm needs to optimise a given problem.
It captures the inertia caused by offspring populations in evolutionary
algorithms and the total computational effort in parallel metaheuristics.
  We present complexity results for LeadingOnes and OneMax. Our main result is
a general performance limit: we prove that on every function every
$\lambda$-parallel unary unbiased algorithm needs at least
$\Omega(\frac{\lambda n}{\ln \lambda} + n \log n)$ evaluations to find any
desired target set of up to exponential size, with an overwhelming probability.
This yields lower bounds for the typical optimisation time on unimodal and
multimodal problems, for the time to find any local optimum, and for the time
to even get close to any optimum. The power and versatility of this approach is
shown for a wide range of illustrative problems from combinatorial
optimisation. Our performance limits can guide parameter choice and algorithm
design; we demonstrate the latter by presenting an optimal $\lambda$-parallel
algorithm for OneMax that uses parallelism most effectively.
