giraph-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Avery Ching <ach...@apache.org>
Subject Re: Termination Conditions
Date Sat, 04 Aug 2012 17:49:09 GMT
I think it would be pretty straightforward to add an option to not 
re-activate a halted vertex on new messages.  Would that satisfy your 
issue Nick?

Avery

On 8/4/12 2:42 AM, Sebastian Schelter wrote:
> 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.west@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.west@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
>>
>>
>>
>>
>>


Mime
View raw message