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:


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.
There is no formal answer for that question, as the notion of "embarrassingly parallel" is not a formal one; it is an informal and imprecise notion.  I understand it to basically mean that if you do the trivial and obvious thing to parallelize (whatever that may be), it works, and there's no need for sophisticated solutions.