The GraphLab model is more asynchronous than BSP  They allow you to update
your neighbors rather than the BSP model of messaging per superstep.  Rather
than one massive barrier in BSP, they implement this with vertex locking.
 They also all a vertex to modify the state of its neighbors.  We could
certainly add something similar as an alternative computing model, perhaps
without locking.  Here's one idea:

1) No explicit supersteps (asynchronous)
2) All vertices execute compute() (and may or may not send messages)
3) Vertices can examine their neighbors or any vertex in the graph (issue
RPCs to get their state)
4) When messages are received by a vertex, compute() is executed on it (and
state is locally locked to compute only)
5) Vertices stlll vote to halt when done, indicating the end of the
6) Combiners can still be used to reduce the number of messages sent (and
the number of times compute is executed).

This could be fun.  And provide an interesting comparison platform barrier
based vs vertex based synchronization.

On Fri, Sep 9, 2011 at 6:36 AM, Jake Mannix <> wrote:

> On Fri, Sep 9, 2011 at 3:22 AM, Claudio Martella <
>> wrote:
>> One misunderstanding my side. Isn't it true that the messages have to be
>> buffered as they all have to be collected before they can be processed (by
>> definition of superstep)? So you cannot really process them as they come?
> This is the current implementation, yes, but I'm trying to see if an
> alternative is also possible in this framework, for Vertex implementations
> which are able to handle asynchronous updates.  In this model, a vertex
> would be required to be able to handle multiple calls to compute() in a
> single "superstep", and would instead signal that it's superstep
> computations are done at some (application specific) point.
> I know this goes outside of the concept of a "BSP" model, but I didn't want
> to get into too many details before I figure out how possible it was to
> implement some of this.
>    -jake

Reply via email to