Hi Nick, I think you are running into the issue that vertex activation/scheduling and data transfer are not separated in the Pregel/Giraph model. I ran into the same problem when trying to implement Adaptive PageRank on Giraph.
I think the problem comes from the vast generality of Pregel's BSP model: vertices can send any kind of message to any other vertex. However, in a lot of algorithms, vertices only send their state to their neighbors. Other platforms such as GraphLab separate activation/scheduling from messaging, in this system a vertex can only schedule its neighbors and once one of the neighbors is invoked, it can read the state of its direct neighbors. I think that the Pregel model is simply not suited for such algorithms (unfortunately), let me know if you find a clever workaround. Best, Sebastian 2012/8/3 Nick West <nick.w...@benchmarksolutions.com> > > 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: > > All vertices are halted after a given superstep > No messages were sent in that superstep > > Hope it helps. > > Alessandro > > From: Nick West <nick.w...@benchmarksolutions.com> > Reply-To: "user@giraph.apache.org" <user@giraph.apache.org> > Date: Friday, August 3, 2012 2:48 PM > To: "user@giraph.apache.org" <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 > <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 > > > > >
