Computational Model

• A Graph is partitioned into a groups of Records.
• A Record consists of a Vertex and its outgoing Edges (An Edge is a Tuple consisting of the edge weight and the target vertex name).
• A User specifies a 'Compute' function that is applied to each Record.
• Computation on the graph happens in a sequence of incremental Super Steps.
• At each Super step, the Compute function is applied to all 'active' vertice of the graph.
• Vertices communicate with each other via Message Passing.
• The Compute function is provided with the Vertex record and all Messages sent to the Vertex in the previous SuperStep.
• A Compute funtion can
  • Mutate the value associated to a vertex
  • Add/Remove outgoing edges.
  • Mutate Edge weight
  • Send a Message to any other vertex in the graph.
  • Change state of the vertex from 'active' to 'hold'.
• At the begining of each SuperStep, if there are no more active vertices -and- if there are no messages to be sent to any vertex, the algorithm terminates.
• A User may additionally specify a 'MaxSteps' to stop the algorithm after a some number of super steps.
• A User may additionally specify a 'Combine' funtion that is applied to the all the Messages targetted at a Vertex before the Compute function is applied to it.