On Friday, 22. April 2011 16:31:20 Steven Watanabe wrote:
AMDG
On 04/22/2011 05:59 AM, Cedric Laczny wrote:
it recently came to my mind again that the distributed BFS in the PBGL seems to produce different results when applied to multiple processors as to when applied to a single processor (s. http://lists.boost.org/boost- users/2010/12/64783.php) If this is true, I really would like to know what the reasoning is behind this and it should be noted in the documentation of course to help prevent surprises as in the discussion above. Unfortunately, at that time, no definite answer was given and this question puzzled me again now... Any ideas on that?
Why would you expect the results to be exactly the same? Parallelism usually introduces a certain amount of non-determinism.
I agree with you on that, generally. And it is good to note this explicitly again. However, maybe I just got a weird kind of perception/expectation here, but especially for search-algorithms, I would expect parallel algorithms to return the same results as otherwise the question of correct interpretation of the parallel results arises to me. I mean, if you get different distance-results depending on the number of processors, what is then the use of distributed BFS, e.g. if you want to know the BFS-distance from source to a specific vertex x?
In Christ, Steven Watanabe
Best, Cedric