If the synchronous, predictable, single threaded version looks like:

Path* result = FindPath(data);
ai->UsePath( result );

Then the asynchronous, predictable, multi-core version usually looks like:

Future<Path*> result = FindPath(data);
... Do as much other work as possible ...
result->WaitUntilComplete();
ai->UsePath( result->GetData() );

The fact that multiple threads are used is an irrelevant detail from an external point of view. You can't have different clients returning results on different frames, because the wait statement synchronizes the threads within a single frame.

Internally, the FindPath function is pushing work into a queue that a thread pool consumes, the wait function stalls until that particular work item has been completed, and the get function fetches the return. Alive that was produced by the worker thread.

Well designed multi-core code of this kind should always behave exactly the same as the single-threaded implementation, with the only difference being that you get better performance if the user has more cores.