giraph-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Nick West <nick.w...@benchmarksolutions.com>
Subject Re: Termination Conditions
Date Fri, 03 Aug 2012 18:28:55 GMT
Thanks for the reply.

Is there an easy modification that I can make to remove condition 2?  Can you point me to
the code that addresses this?

The problem I am facing is the following:  At every iteration a non-halted vertex needs messages
from all of its neighbors.  When deciding to send messages, a given vertex doesn't know if
its neighbors will vote-to-halt in the current superstep, thus it must send a message to each
of its neighbors.  In the case that all vertices have voted to stop, the sending of a messages
by any vertex will cause the algorithm to continue, yet in this situation it is desirable
to terminate.

I have worked out a few solutions that involve either increasing the amount of data a vertex
saves each iteration or augmenting the messages sent with additional information, but I think
it would be beneficial, and more general, to allow this type of termination instead.

Do you have any thoughts on this?

Thanks,
Nick


On Aug 3, 2012, at 10:14 AM, Alessandro Presta wrote:

Hi Nick,

You are pretty much correct, except that not all vertices need to vote to halt at the same
time: some vertices might have voted to halt at a previous superstep and never received any
messages after then, in which case they are never reactivated.

In other words, I think you can rephrase that as:

  1.  All vertices are halted after a given superstep
  2.  No messages were sent in that superstep

Hope it helps.

Alessandro

From: Nick West <nick.west@benchmarksolutions.com<mailto:nick.west@benchmarksolutions.com>>
Reply-To: "user@giraph.apache.org<mailto:user@giraph.apache.org>" <user@giraph.apache.org<mailto:user@giraph.apache.org>>
Date: Friday, August 3, 2012 2:48 PM
To: "user@giraph.apache.org<mailto:user@giraph.apache.org>" <user@giraph.apache.org<mailto:user@giraph.apache.org>>
Subject: Termination Conditions

Excuse me if this is stated somewhere obvious, but I haven't been unable to find it.  What
are the exact termination criteria for the global algorithm?

Reading the documentation on voteToHalt, looking at the Shortest Path Example code, and looking
at the results of my own application, these two conditions must both hold for the global BSP
algorithm to terminate:

1) All vertices vote to halt in a given superstep
2) No messages are sent in that supersetp

Is that correct?

Thanks,
Nick West

Benchmark Solutions
101 Park Avenue - 7th Floor
New York, NY 10178
Tel +1.212.220.4739 | Mobile +1.646.267.4324
www.benchmarksolutions.com <http://www.benchmarksolutions.com/>
<image001.png>





<image001.png>


Nick West

Benchmark Solutions
101 Park Avenue - 7th Floor
New York, NY 10178
Tel +1.212.220.4739 | Mobile +1.646.267.4324
www.benchmarksolutions.com <http://www.benchmarksolutions.com/>
[cid:image001.png@01CCA50E.43B4A860]






Mime
View raw message