FULL PRODUCT VERSION :
java version "1.8.0_05"
Java(TM) SE Runtime Environment (build 1.8.0_05-b13)
Java HotSpot(TM) 64-Bit Server VM (build 25.5-b02, mixed mode)

ADDITIONAL OS VERSION INFORMATION :
Microsoft Windows [Version 6.1.7601]

A DESCRIPTION OF THE PROBLEM :
I have found a case where CompletedFuture.exceptionally runs on the main thread instead of the thread on which the initial task was executed.

STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
Compile and execute the main method provided under "Test Case" and capture the output..

EXPECTED VERSUS ACTUAL BEHAVIOR :
EXPECTED -
The output in the second section should appear similar to this:

Sat Jun 07 23:01:38 BST 2014 - pool-1-thread-1: Begin Throwing an Exception
Sat Jun 07 23:01:38 BST 2014 - pool-1-thread-1: Begin Handling Exception
Sat Jun 07 23:01:38 BST 2014 - pool-1-thread-1: Done Handling Exception
Sat Jun 07 23:01:38 BST 2014 - pool-1-thread-1: Begin Safe Call
Sat Jun 07 23:01:38 BST 2014 - pool-1-thread-1: We failed due to java.lang.UnsupportedOperationException: You shouldn't really be calling this!
Sat Jun 07 23:01:38 BST 2014 - pool-1-thread-1: End Safe Call
Sat Jun 07 23:01:38 BST 2014 - main: An exception propogated to the main thread: java.lang.UnsupportedOperationException: You shouldn't really be calling this!

Sat Jun 07 23:01:38 BST 2014 - pool-1-thread-2: The safe example returned 0.0
ACTUAL -
The output in the second section appears like this:

Sat Jun 07 23:01:38 BST 2014 - pool-1-thread-1: Begin Throwing an Exception
Sat Jun 07 23:01:38 BST 2014 - main: Begin Handling Exception
Sat Jun 07 23:01:38 BST 2014 - main: Done Handling Exception
Sat Jun 07 23:01:38 BST 2014 - main: Begin Safe Call
Sat Jun 07 23:01:38 BST 2014 - main: We failed due to java.lang.UnsupportedOperationException: You shouldn't really be calling this!
Sat Jun 07 23:01:38 BST 2014 - main: End Safe Call
Sat Jun 07 23:01:38 BST 2014 - main: An exception propogated to the main thread: java.lang.UnsupportedOperationException: You shouldn't really be calling this!

Sat Jun 07 23:01:38 BST 2014 - pool-1-thread-2: The safe example returned 0.0

REPRODUCIBILITY :
This bug can be reproduced always.

---------- BEGIN SOURCE ----------
package java8examples;

import java.util.Date;
import java.util.List;
import java.util.concurrent.CompletableFuture;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.ScheduledThreadPoolExecutor;
import java.util.function.BiFunction;
import java.util.function.Function;
import java.util.function.Supplier;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class CompletableFutureExample {

public static void main (String[] args) throws InterruptedException, ExecutionException {
ExecutorService executor = new ScheduledThreadPoolExecutor(5);
CompletableFuture<List<Integer>> listFuture = CompletableFuture.supplyAsync(runWithLogging("Generating Numbers", () -> IntStream.range(0, (int) 1e3).mapToObj(n -> { return n; }).collect(Collectors.toList())), executor);

CompletableFuture<Long> sumFuture = listFuture.thenApply(runWithLogging("Calculating Sum", list -> list.stream().mapToLong(n -> n).sum()));
CompletableFuture<Long> sumSquareFuture = listFuture.thenApplyAsync(runWithLogging("Calculating Sum Square", list -> list.stream().mapToLong(n -> n*n).sum()));
CompletableFuture<Integer> countFuture = listFuture.thenApplyAsync(runWithLogging("Calculating Size", list -> list.size()), executor);
CompletableFuture<Double> avgFuture = sumFuture.thenCombine(countFuture, runWithLogging("Calculating Average", (sum, count) -> 1.0 * sum / count));
CompletableFuture<Double> stddevFuture = sumFuture.thenCombineAsync(sumSquareFuture, runWithLogging("Calculating Stddev", (sum, sumSq) -> (sumSq - 1.0*sum*sum/countFuture.join())/(countFuture.join()-1)), executor);
CompletableFuture<Double> medianFuture = listFuture.thenApplyAsync(runWithLogging("Calculating Median", CompletableFutureExample::calculateMedian), executor);

//Commenting this allOf statement appears to make this bug go away
CompletableFuture.allOf(avgFuture, stddevFuture, medianFuture).thenAccept(x -> {
try {
log("Average: " + avgFuture.get());
log("Median: " + medianFuture.get());
log("Standard Deviation: " + stddevFuture.get());
} catch (Exception e) {
throw new RuntimeException();
}
}).get();
System.out.println();

CompletableFuture<Double> throwFuture = listFuture.<Double>thenApplyAsync(runWithLogging("Throwing an Exception", list -> { throw new UnsupportedOperationException("You shouldn't really be calling this!"); }), executor);
CompletableFuture<Double> miracleFuture = throwFuture.thenApply(runWithLogging("Propogating", n -> n));
CompletableFuture<Double> handleFuture = throwFuture.exceptionally(sleepAndThen(500, runWithLogging("Handling Exception", exc -> 0.0)));
CompletableFuture<Double> safeFuture = throwFuture.handle(runWithLogging("Safe Call", (Double ok, Throwable exc) -> {
if (ok != null) {
log("We were successful and returned " + ok);
return ok;
} else {
log("We failed due to " + exc.getMessage());
return 0.0;
}
}));
try {
CompletableFuture.anyOf(miracleFuture, handleFuture).thenAccept(o -> {
log("We've finished the exception example and got " + o + " back");
}).get();
} catch (ExecutionException e) {
log("An exception propogated to the main thread: " + e.getMessage());
}
safeFuture.exceptionally(runWithLogging("Exceptional case which should not throw", exc -> 0.0))
.thenAcceptAsync(d -> log("The safe example returned " + d), executor);
System.out.println();

executor.shutdown();
}

private static void log (String s) {
System.out.println(new Date() + " - " + Thread.currentThread().getName() + ": " + s);
}

private static <T> Supplier<T> runWithLogging(String log, Supplier<T> method) {
return () -> {
log("Begin " + log);
T ret = method.get();
log("Done " + log);
return ret;
};
}

private static <T, R> Function<T, R> runWithLogging(String log, Function<T, R> function) {
return src -> {
log("Begin " + log);
R ret = function.apply(src);
log("Done " + log);
return ret;
};
}

private static <T, U, R> BiFunction<T, U, R> runWithLogging(String log, BiFunction<T, U, R> function) {
return (a, b) -> {
log("Begin " + log);
R ret = function.apply(a, b);
log("End " + log);
return ret;
};
}

private static double calculateMedian(List<Integer> list) {
List<Integer> sorted = list.stream().sorted().collect(Collectors.toList());
int mid = sorted.size() / 2;
double ret;
if (sorted.size() % 2 == 0)
ret = 1.0*(sorted.get(mid-1) + sorted.get(mid))/2;
else
ret = sorted.get(mid);
return ret;
}

private static <T, R> Function<T, R> sleepAndThen (int millis, Function<T, R> func) {
Function<T, T> sleepFunc = s -> {
try {
Thread.sleep(millis);
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
throw new RuntimeException(e);
}
return s;
};
return sleepFunc.andThen(func);
}
}
---------- END SOURCE ----------

CUSTOMER SUBMITTED WORKAROUND :
Commending the allOf statement shown in this code appears to resolve this issue.