{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,26]],"date-time":"2026-09-26T17:09:49Z","timestamp":1790442589793,"version":"4.1.0"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"9","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2015,5]]},"abstract":"<jats:p>The bulk synchronous parallel (BSP) model used by synchronous graph processing systems allows algorithms to be easily implemented and reasoned about. However, BSP can suffer from poor performance due to stale messages and frequent global synchronization barriers. Asynchronous computation models have been proposed to alleviate these overheads but existing asynchronous systems that implement such models have limited scalability or retain frequent global barriers, and do not always support graph mutations or algorithms with multiple computation phases. We propose barrierless asynchronous parallel (BAP), a new computation model that reduces both message staleness and global synchronization. This enables BAP to overcome the limitations of existing asynchronous models while retaining support for graph mutations and algorithms with multiple computation phases. We present GiraphUC, which implements our BAP model in the open source distributed graph processing system Giraph, and evaluate our system at scale with large real-world graphs on 64 EC2 machines. We show that GiraphUC provides across-the-board performance improvements of up to 5\u00d7 faster over synchronous systems and up to an order of magnitude faster than asynchronous systems. Our results demonstrate that the BAP model provides efficient and transparent asynchronous execution of algorithms that are programmed synchronously.<\/jats:p>","DOI":"10.14778\/2777598.2777604","type":"journal-article","created":{"date-parts":[[2015,5,15]],"date-time":"2015-05-15T12:09:36Z","timestamp":1431691776000},"page":"950-961","source":"Crossref","is-referenced-by-count":132,"title":["Giraph unchained"],"prefix":"10.14778","volume":"8","author":[{"given":"Minyang","family":"Han","sequence":"first","affiliation":[{"name":"University of Waterloo"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Khuzaima","family":"Daudjee","sequence":"additional","affiliation":[{"name":"University of Waterloo"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2015,5]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Apache Giraph. http:\/\/giraph.apache.org.  Apache Giraph. http:\/\/giraph.apache.org."},{"key":"e_1_2_1_2_1","unstructured":"Apache Hama. http:\/\/hama.apache.org.  Apache Hama. http:\/\/hama.apache.org."},{"key":"e_1_2_1_3_1","unstructured":"Okapi. http:\/\/grafos.ml\/okapi.  Okapi. http:\/\/grafos.ml\/okapi."},{"key":"e_1_2_1_4_1","unstructured":"GraphLab: Distributed Graph-Parallel API. http:\/\/docs.graphlab.org\/classgraphlab_1_1async__consistent__engine.html 2014.  GraphLab: Distributed Graph-Parallel API. http:\/\/docs.graphlab.org\/classgraphlab_1_1async__consistent__engine.html 2014."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2380718.2380723"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.587"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1963405.1963488"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/988672.988752"},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","unstructured":"P. Boldi and S. Vigna. Four Degrees of Separation Really. http:\/\/arxiv.org\/abs\/1205.5509 2012.  P. Boldi and S. Vigna. Four Degrees of Separation Really. http:\/\/arxiv.org\/abs\/1205.5509 2012.","DOI":"10.1109\/ASONAM.2012.211"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767921"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735471.2735477"},{"key":"e_1_2_1_12_1","unstructured":"A. Ching. Scaling Apache Giraph to a trillion edges. http:\/\/www.facebook.com\/10151617006153920 2013.  A. Ching. Scaling Apache Giraph to a trillion edges. http:\/\/www.facebook.com\/10151617006153920 2013."},{"key":"e_1_2_1_13_1","volume-title":"IPPS '96","author":"Chung S."},{"key":"e_1_2_1_14_1","unstructured":"T. H. Cormen C. E. Leiserson R. L. Rivest and C. Stein. Introduction to Algorithms. The MIT Press 3rd edition.   T. H. Cormen C. E. Leiserson R. L. Rivest and C. Stein. Introduction to Algorithms . The MIT Press 3rd edition."},{"key":"e_1_2_1_15_1","unstructured":"J. Edwards. 'Facebook Inc.' Actually Has 2.2 Billion Users Now. http:\/\/www.businessinsider.com\/facebook-inc-has-22-billion-users-2014-7 2014.  J. Edwards. 'Facebook Inc.' Actually Has 2.2 Billion Users Now. http:\/\/www.businessinsider.com\/facebook-inc-has-22-billion-users-2014-7 2014."},{"key":"e_1_2_1_16_1","volume-title":"OSDI '12","author":"Gonzalez J. E.","year":"2012"},{"key":"e_1_2_1_17_1","unstructured":"Google. How search works. http:\/\/www.google.com\/insidesearch\/howsearchworks\/thestory\/ 2014.  Google. How search works. http:\/\/www.google.com\/insidesearch\/howsearchworks\/thestory\/ 2014."},{"key":"e_1_2_1_18_1","first-page":"2","author":"Gurcan M.","year":"2009","journal-title":"Histopathological Image Analysis: A Review. IEEE Rev Biomed Eng"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732977.2732980"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2009.14"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2465351.2465369"},{"key":"e_1_2_1_23_1","first-page":"31","volume-title":"OSDI '12","author":"Kyrola A.","year":"2012"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.14778\/2212351.2212354"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807184"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1002\/bies.201000044"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASONAM.2012.254"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2484838.2484843"},{"key":"e_1_2_1_29_1","volume-title":"Stanford","author":"Salihoglu S.","year":"2013"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544855"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2467799"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1963405.1963491"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732232.2732238"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/79173.79181"},{"key":"e_1_2_1_35_1","volume-title":"CIDR '13","author":"Wang G.","year":"2013"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2484425.2484427"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.14778\/2733085.2733103"},{"key":"e_1_2_1_38_1","volume-title":"Spark: Cluster Computing with Working Sets. In HotCloud '10","author":"Zaharia M.","year":"2010"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2287036.2287041"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2777598.2777604","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T05:18:10Z","timestamp":1672204690000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2777598.2777604"}},"subtitle":["barrierless asynchronous parallel execution in pregel-like graph processing systems"],"short-title":[],"issued":{"date-parts":[[2015,5]]},"references-count":38,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2015,5]]}},"alternative-id":["10.14778\/2777598.2777604"],"URL":"https:\/\/doi.org\/10.14778\/2777598.2777604","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2015,5]]}}}