MailboxProtocol

public protocol MailboxProtocol

Represents the per-vertex communication abstraction for vertex-parallel algorithms.

Vertex-parallel algorithms execute as a series of super-steps, where in each step, a vertex can (1) perform vertex-local computation, (2) receive messages from the previous step, and (3) send messages to any other vertex (that will be received in the next step).

As a simplification and performance optimization, we require that all messages can be merged, such verticies receive at most one message per step. Messages are merged in parallel, which reduces memory and bandwidth pressures. This does not cause a loss in generality of the algorithms that can be expressed, as it is trivial to write an “envelope” type that is an array of the underlying messages.

This abstraction is inspired by:

Pregel: A System for Large-Scale Graph Processing (2010) Grzegorz Malewicz, Matthew H. Austern, Aart J. C. Bik, James C. Dehnert, Ilan Horn, Naty Leiser, and Grzegorz Czajkowski