  We study distributed graph algorithms that adopt an iterative vertex-centric
framework for graph processing, popularized by the Google's Pregel system.
Since then, there are several attempts to implement many graph algorithms in a
vertex-centric framework, as well as efforts to design optimization techniques
for improving the efficiency. However, to the best of our knowledge, there has
not been any systematic study to compare these vertex-centric implementations
with their sequential counterparts. Our paper addresses this gap in two ways.
(1) We analyze the computational complexity of such implementations with the
notion of time-processor product, and benchmark several vertex-centric graph
algorithms whether they perform more work with respect to their best-known
sequential solutions. (2) Employing the concept of balanced practical Pregel
algorithms, we study if these implementations suffer from imbalanced workload
and large number of iterations. Our findings illustrate that with the exception
of Euler tour tree algorithm, all other algorithms either perform more work
than their best-known sequential approach, or suffer from imbalanced workload/
large number of iterations, or even both. We also emphasize on graph algorithms
that are fundamentally difficult to be expressed in vertex-centric frameworks,
and conclude by discussing the road ahead for distributed graph processing.
