One, each core has to know about the other cores' search space and avoid it (to avoid duplicating effort) so you will contend on some sort of 'visited node' cache.
Just make the visited node cache public and immutable.
Two, the graph your building itself must be shared, obvs.
If the graph is immutable then there's zero problem with it being shared.
You can't make the cache immutable because then it will be empty at start and stays that way ;)
The cache has to mutate and be shared as that's the work completed list. As each thread completes a bit of work (visits a node) it needs to communicate it with the other threads.
:+= Returns A copy of this sequence with an element appended.
Meaning the cache is no longer shared as all threads end up having a thread local cache. You can't update shared changing state and have immutability at the same time.
Immutability is great when one can have it but sometimes its not possible. Shared changing state is something to be avoid as much as possible but sometimes we need it.
If it's public and immutable each core will get only its own cache, which would be pointless. I like your thinking, though; perhaps there can be a way to always pass the last 'visited node' cache around in a timely way.
Just make the visited node cache public and immutable.
Two, the graph your building itself must be shared, obvs.
If the graph is immutable then there's zero problem with it being shared.