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://listarchives.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