1Supplementary File of the TPDS manuscript

Abstract—This supplementary file contains the supporting materials of the TPDS manuscript “Maiter: An Asynchronous Graph Processing Framework for Delta-based Accumulative Iterative Computation. ” It improves the completeness of the TPDS manuscript. F 1 ITERATIVE GRAPH PROCESSING The graph algorithm can be abstracted as the oper-ations on a graph G(V;E). Peoples usually exploit a vertex-centric model to solve the graph algorithms. Basically, the graph algorithm is described from a single vertex’s perspective and then applied to each vertex for a loosely coupled execution. Iterative graph algorithms perform the same operations on the graph vertices for several iterations. Each vertex j ∈ V maintains a vertex state vj that is updated iteratively. The key of a vertex-centric graph computation is the update function f performed on each vertex j: vkj = f(v k−1 1; v k−1 2; : : : ; v k−1 n); (1) where vkj represents vertex j’s state after the k th iteration, and v1; v2; : : : ; vn are the states of vertex j’s neighbors. The state values are passed between vertices through the edges. The iterative process con-tinues until the graph vertex state becomes stable, when the iterative algorithm converges. For example, the well-known PageRank algorithm iteratively updates all pages ’ ranking scores. Accord-ing to the vertex-centric graph processing model, in each iteration, we update the ranking score of each page j, Rj, as follows: Rkj = d