Limiting concurrent access to a field

Question

So in a program I'm writing I use a bi-directional breadth first search to search a graph. I do this by running 1 breadth first search in 1 thread, and one in another. Now the search is said to have found the optimal solution when it either an element from the other search is hit, or when the goal is found (which never really happens, but just in case it does for some reason..).

The problem I am running into, is that I need to save this optimal solution to a field, because I need to continue to find all of the solutions, but the field value is getting messed up because both threads hit it at the same time (I think).

Is there a way to block access to the thread who gets there last? I've tried using an AtomicReference and its compareAndSet method but that didn't do the trick. The value still gets messed up....

Btw I'm using java, and for the threads I'm using Callable objects.

Answer 1

Looks like you have a possible Livelock or Race condition that is occuring because of the random order of threads. I'd recommending taking a different approach. (otherwise at some point you will run into NP-Complete).

The problem I am running into, is that I need to save this optimal solution to a field. because I need to continue to find all of the solutions, but the field value is getting messed up because both threads hit it at the same time (I think).

There is a way to greatly increase your current technique. You shouldn't need to look at every solution, take a Greedy Approach and use a Paralleled version of Dijkstra's Shortest Path Algorithm.

Shortest Path (or in your case Optimal Solution)

Dijkstra's Algorithm is a graph search algorithm that solves the single-source shortest path problem for a graph with nonnegative edge path costs, producing a shortest path tree. This algorithm is often used in routing and as a subroutine in other graph algorithms.

Linear Implementation

The original algorithm Figure 1. (Source)

_{(source: iforce.co.nz)}

Java Implementations can be found Here, and Here

• I think these implementations are based on BSP Trees (but you should get the idea)

Parallel Implementation

The parallel algorithm Figure 2. (Source)

• There are additional ways to speed up the algorithm with recursion, if you want to get classy.

_{(source: iforce.co.nz)}

Another idea if you are still having problems, might be to use a different concurrent data structure like Map Reduce or Hadoop instead of using Threads to search through a Binary Tree, to fix your search.

Answer 2

Note: not an answer, just checking the validity of the algorithm

Does your algorithm actually yield the shortest path? Consider this graph:

 1A - 2A - 3A - 4A - 5A
  \             /     
   -- 2B -------  

And assume perfect interweaving (the threads each visit nodes at the exact same rate). Thread X starts at 1A and thread Y starts at 5A. The order would look like this:

X visits 1A +{2A, 2B}
Y visits 5A +{4A}
X visits 2A +{3A}
Y visits 4A +{3A, 2B}
X visits 2B +{4A}
Y visits 3A +{2A}
X visits 3A (overlap; shortest path is computed to be 4)

But we know from inspection that the shortest path is 3: 1A - 2B - 4A - 5A.

How does your approach prevent this case? No matter which approach you take for checking for duplicates, I always see 3A overlapping before 2B. Do you always finish out the "level" before making a decision on what the optimal path length is?