"What's wrong with an API which non-deterministically returns either A or B(Set(A, ...)?"

... which seems pretty much what the exception handling behavior of the parallel collections does.

If exceptions of type A occur, either an exception of type A or an exception of type B, wrapping multiple exceptions of A's, is observed.
Imho, this behavior is incredibly broken and so unintuitive, that even people writing tests don't handle it correctly. See files/run/t5375.scala.

Concerning “non-deterministic”:
How many exceptions are observed before the operation is aborted depends on the machine, the available cores and hyper-threading, the operating system, the threadpool implementation and configuration, the size of the collection and the runtime itself.

In fact, files/run/t5375.scala is failing on both jdk7u and Avian because of this issue.

After thinking about this, I propose just throwing the "first" exception which occurs.
This seems to be what C# and Java both do, too.

Even consistently returning CompositeThrowable doesn't make much sense (because we have fail-fast behaviour and don't wait until all tasks have finished or have thrown an exception).
Therefore, there is no useful semantic in having a CompositeThrowable which returns "some" exceptions. Either we gather and return all the exceptions or we just return one, instead of wrapping a non-deterministic number of exceptions into a completely unrelated wrapper type.

Considering that changing the parallel collection semantics in such a profound way is out of question, I propose the second option.

As soon as we are targeting Java > 7 we can use addSurpressed to add further exceptions which also occurred.

Mailing list thread: https://groups.google.com/d/topic/scala-internals/jlHg5NKruLU/discussion