Adaptive Asynchronous Parallelization of Graph Algorithms

CategoryPublications Publications 240

Authors: Wenfei Fan, Ping Lu, Jingbo Xu, Wenyuan Yu, Qiang Yin, Xiaojian Luo, Jingren Zhou, Ruochun Jin

Published in: ACM Transactions on Database Systems (TODS 2020)

Date of Publication: July 1, 2020


This article proposes an Adaptive Asynchronous Parallel (AAP) model for graph computations. As opposed to Bulk Synchronous Parallel (BSP) and Asynchronous Parallel (AP) models, AAP reduces both stragglers and stale computations by dynamically adjusting relative progress of workers. We show that BSP, AP, and Stale Synchronous Parallel model (SSP) are special cases of AAP. Better yet, AAP optimizes parallel processing by adaptively switching among these models at different stages of a single execution. Moreover, employing the programming model of GRAPE, AAP aims to parallelize existing sequential algorithms based on simultaneous fixpoint computation with partial and incremental evaluation. Under a monotone condition, AAP guarantees to converge at correct answers if the sequential algorithms are correct. Furthermore, we show that AAP can optimally simulate MapReduce, PRAM, BSP, AP, and SSP. Using real-life and synthetic graphs, we experimentally verify that AAP outperforms BSP, AP, and SSP for a variety of graph computations.

View Full Text

Keywords2020Distributed graph systemsTODSWenfei Fan Previous: Next: