Rework propagation in the case of linear dependency chains, which are the only cases in which these kinds of StackOverflowErrors occur. By re-packing actions while processing dependent completions, we can isolate tail-recursive cases and loopify them. This generally works out better than moving them across lists, because doing so can reduce opportunities for other threads to help process them.
Already checked into the 166 CVS:
http://gee.cs.oswego.edu/cgi-bin/viewcvs.cgi/jsr166/src/main/java/util/concurrent/CompletableFuture.java?view=log
For further information, see the discussion on concurrency-interest mailing list:
http://cs.oswego.edu/pipermail/concurrency-interest/2014-April/012501.html