Projects per year
Abstract / Description of output
This paper 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 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.
Original language | English |
---|---|
Title of host publication | Proceedings of the 2018 International Conference on Management of Data (SIGMOD'18) |
Place of Publication | Texas, USA |
Publisher | ACM |
Pages | 1141-1156 |
Number of pages | 16 |
ISBN (Electronic) | 978-1-4503-4703-7 |
DOIs | |
Publication status | Published - 27 May 2018 |
Event | 2018 ACM SIGMOD/PODS International Conference on Management of Data - Houston, United States Duration: 10 Jun 2018 → 15 Jun 2018 https://sigmod2018.org/ |
Publication series
Name | International Conference on Management of Data |
---|---|
Publisher | ACM |
ISSN (Electronic) | 0730-8078 |
Conference
Conference | 2018 ACM SIGMOD/PODS International Conference on Management of Data |
---|---|
Abbreviated title | SIGMOD'18 |
Country/Territory | United States |
City | Houston |
Period | 10/06/18 → 15/06/18 |
Internet address |
Keywords / Materials (for Non-textual outputs)
- parallel model
- parallelisation
- graph computations
- Church-Rosser
Fingerprint
Dive into the research topics of 'Adaptive Asynchronous Parallelization of Graph Algorithms'. Together they form a unique fingerprint.Projects
- 2 Finished
-
-
VADA: Value Added Data Systems: Principles and Architecture
Libkin, L., Buneman, P., Fan, W. & Pieris, A.
1/04/15 → 30/09/20
Project: Research
Profiles
-
Wenfei Fan
- School of Informatics - Personal Chair in Web Data Management
- Laboratory for Foundations of Computer Science
- Foundations of Computation
Person: Academic: Research Active