Calling a method in parallel which returns the future
An executor service will be able to do a invokeAll with a timeout and return a set of futures holding all the values or return when the timeout expires.

This means that your executeAsync should take a set of keys and build all the tasks from those at once and then submit the tasks as a batch:

@Override
public List&lt;Future&lt;DataResponse&gt;&gt; executeAsync(Collection&lt;DataKey&gt; keys,  long timeout, TimeUnit unit) {
    List&lt;Task&gt; tasks = new ArrayList&lt;&gt;(keys.size());
    for(DataKey key : keys){
        tasks.add(new Task(key, restTemplate));
    }

    return executor.invokeAll(tasks, timeout, unit);
}


@Override
public List&lt;DataResponse&gt; executeSync(DataKey key) {
    List&lt;DataResponse&gt; responseList = new ArrayList&lt;DataResponse&gt;();

    // make a List of DataKey using single key passed to this method.       
    List&lt;DataKey&gt; keys = new ArrayList&lt;DataKey&gt;();

    List&lt;Future&gt; futures = executeAsync(keys, 300, TimeUnit.MILLISECONDS);


    for (Future&lt;DataResponse&gt; future : futures) {
        try {
            if(future.isDone())
                responseList.add(future.get());
            //otherwise future didn't complete in the 300 milliseconds
        } catch (Exception e) {
            // do something
        }
    }
    return responseList;
}