You are viewing a plain text version of this content. The canonical link for it is here.
Posted to user@giraph.apache.org by Nick West <ni...@benchmarksolutions.com> on 2012/08/03 15:48:37 UTC
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/>
[cid:image001.png@01CCA50E.43B4A860]
Re: Termination Conditions
Posted by KAUSHIK SARKAR <co...@gmail.com>.
Hi Nick,
I guess you can use MasterCompute together with BooleanAndAggregator to
solve your problem. Whenever a vertex decides to halt, it will notify the
MasterCompute with "true" value for the aggregator, otherwise it will send
"false". If all the vertices agree to halt at a superstep, then the value
of the BooleanAndAggregator at the MasterCompute will evaluate to "true",
and the masterCompute can then call the haltComputation() method to stop
computation. Any message sent at the last superstep will have no effect
(which you want in this case). Of course this solution assumes that you are
using Giraph-0.2, since older versions do not have the MasterCompute class
for centralized decision making of this type.
Hope this helps.
Regards,
Kaushik
On Fri, Aug 3, 2012 at 11:28 AM, Nick West <nick.west@benchmarksolutions.com
> wrote:
> 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 <ni...@benchmarksolutions.com>
> Reply-To: "user@giraph.apache.org" <us...@giraph.apache.org>
> Date: Friday, August 3, 2012 2:48 PM
> To: "user@giraph.apache.org" <us...@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/>
> ***
>
>
>
> *
> **
>
Re: Termination Conditions
Posted by Avery Ching <ac...@apache.org>.
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.west@benchmarksolutions.com
>>> <ma...@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
>>>> <ma...@benchmarksolutions.com>>
>>>> Reply-To: "user@giraph.apache.org <ma...@giraph.apache.org>"
>>>> <user@giraph.apache.org <ma...@giraph.apache.org>>
>>>> Date: Friday, August 3, 2012 2:48 PM
>>>> To: "user@giraph.apache.org <ma...@giraph.apache.org>"
>>>> <user@giraph.apache.org <ma...@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>
>>>>
>>>>
>>>>
>>>>
>>>>
>>
>
> *
> 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/>
> *
>
>
> *
>
Re: Termination Conditions
Posted by Nick West <ni...@benchmarksolutions.com>.
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 <ni...@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 <ni...@benchmarksolutions.com>>
Reply-To: "user@giraph.apache.org<ma...@giraph.apache.org>" <us...@giraph.apache.org>>
Date: Friday, August 3, 2012 2:48 PM
To: "user@giraph.apache.org<ma...@giraph.apache.org>" <us...@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>
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]
Re: Termination Conditions
Posted by Avery Ching <ac...@apache.org>.
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 <ni...@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 <ni...@benchmarksolutions.com>
>> Reply-To: "user@giraph.apache.org" <us...@giraph.apache.org>
>> Date: Friday, August 3, 2012 2:48 PM
>> To: "user@giraph.apache.org" <us...@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
>>
>>
>>
>>
>>
Re: Termination Conditions
Posted by Sebastian Schelter <ss...@apache.org>.
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 <ni...@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 <ni...@benchmarksolutions.com>
> Reply-To: "user@giraph.apache.org" <us...@giraph.apache.org>
> Date: Friday, August 3, 2012 2:48 PM
> To: "user@giraph.apache.org" <us...@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
>
>
>
>
>
Re: Termination Conditions
Posted by Nick West <ni...@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:
1. All vertices are halted after a given superstep
2. No messages were sent in that superstep
Hope it helps.
Alessandro
From: Nick West <ni...@benchmarksolutions.com>>
Reply-To: "user@giraph.apache.org<ma...@giraph.apache.org>" <us...@giraph.apache.org>>
Date: Friday, August 3, 2012 2:48 PM
To: "user@giraph.apache.org<ma...@giraph.apache.org>" <us...@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]
Re: Termination Conditions
Posted by Alessandro Presta <al...@fb.com>.
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 <ni...@benchmarksolutions.com>>
Reply-To: "user@giraph.apache.org<ma...@giraph.apache.org>" <us...@giraph.apache.org>>
Date: Friday, August 3, 2012 2:48 PM
To: "user@giraph.apache.org<ma...@giraph.apache.org>" <us...@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/>
[cid:image001.png@01CCA50E.43B4A860]