Ah, I think that could be reasonably
added as an option. Seems pretty reasonable (and fairly easy).
In fact, I think that was the behavior (a bug) for a little while
in the past. =)
Avery
On 8/14/12 2:08 PM, Nick West wrote:
Thank you all for the replies.
I think Kaushik has the easiest solution for me. I'll give
that a try.
Avery: I want to the vertices to re-activate when they
receive a new message, unless all vertices have voted to halt
that iteration. So not reactivating after voting to halt would
not solve this problem.
Thanks,
Nick
On Aug 4, 2012, at 1:49 PM, Avery Ching wrote:
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.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
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
|