Data-intensive, graph-based computations are pervasive in several scientific
applications, and are known to to be quite challenging to implement on
distributed memory systems. In this work, we explore the design space of
parallel algorithms for Breadth-First Search (BFS), a key subroutine in several
graph algorithms.