# Embarrassingly Parallel: Formal Definition & Citation

I've been unable to find a good answer for this question: Formally, what makes a problem embarrassingly parallel? Intuitively, it would seem to me that an embarrassingly parallel problem is one where:

1. The full solution can be discretized.
2. It is efficiently decomposable into subproblems that are similar in structure.
3. Each subproblem is (more or less) independently soluble (i.e. without a large communication overhead required between the subproblems).
4. The solutions of each subproblem are independent such that there is an efficient method that can reassemble them into the larger solution.

I realize there's some overlap in the bullets above, hence the question – how is 'embarrassingly parallel' or its synonymous technical term clearly defined? Is there a reference in the literature where this definition was first formalized?

Note: I'm not trained in TCS (as you may have guessed) and am aware that my descriptions above may not be entirely correct or in keeping with established formalisms and terminology.

• Interesting question. As a first stab, I would say "embarrassingly parallel" is a property of a particular serial algorithm, not a problem, and roughly would say that if the algorithm takes t time then using k processors the algorithm can be implemented in O(t/k) time. This certainly captures the "parallel" part but not necessarily the "embarrassing" part of it. Feb 3, 2020 at 23:18
• @RyanWilliams Maybe it could be captured through a constraint on Amdahl's Law? First, given $S_{speedup} \le {1 \over{(1 - p) + p/s}}$, where $p$ is the proportion of the task to be parallelized and $s$ is the speed improvement for that proportion. Then, we say something like an embarrassingly parallel problem is one where $p \lesssim 1$. Note that I'm using $\lesssim$ here to convey 'less than and approximately equal to.' That said, this would be more of a practical definition and not quite the complexity theory one I had in mind. Feb 4, 2020 at 4:22