Re: [Boost-users] [PBGL] Results of distributed BFS on multiple processors vs. on a single processor

Subject: Re: [Boost-users] [PBGL] Results of distributed BFS on multiple processors vs. on a single processor
From: Cedric Laczny (cedric.laczny_at_[hidden])
Date: 2011-04-22 11:01:43

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