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:
- The full solution can be discretized.
- It is efficiently decomposable into subproblems that are similar in structure.
- Each subproblem is (more or less) independently soluble (i.e. without a large communication overhead required between the subproblems).
- 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.