{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:08:10Z","timestamp":1750306090827,"version":"3.41.0"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2017,6,13]],"date-time":"2017-06-13T00:00:00Z","timestamp":1497312000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100002418","name":"Intel Corporation","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100002418","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Meas. Anal. Comput. Syst."],"published-print":{"date-parts":[[2017,6,13]]},"abstract":"<jats:p>Despite their widespread adoption, large-scale graph processing systems do not fully decouple computation and communication, often yielding suboptimal performance. Locally-sufficient computation-computation that relies only on the graph state local to a computing host-can mitigate the effects of this coupling. In this paper, we present Compute-Sync-Merge (CSM), a new programming abstraction that achieves efficient locally-sufficient computation. CSM enforces local sufficiency at the programming abstraction level and enables the activation of vertex-centric computation on all vertex replicas, thus supporting vertex-cut partitioning. We demonstrate the simplicity of expressing several fundamental graph algorithms in CSM. Hieroglyph-our implementation of a graph processing system with CSM support-outperforms state of the art by up to 53x, with a median speedup of 3.5x and an average speedup of 6x across a wide range of datasets.<\/jats:p>","DOI":"10.1145\/3084446","type":"journal-article","created":{"date-parts":[[2018,3,23]],"date-time":"2018-03-23T18:28:08Z","timestamp":1521829688000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Hieroglyph"],"prefix":"10.1145","volume":"1","author":[{"given":"Xiaoen","family":"Ju","sequence":"first","affiliation":[{"name":"University of Michigan, Ann Arbor, MI, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hani","family":"Jamjoom","sequence":"additional","affiliation":[{"name":"IBM T.J. Watson Research Center, Yorktown Heights, NY, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kang G.","family":"Shin","sequence":"additional","affiliation":[{"name":"University of Michigan, Ann Arbor, MI, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,6,13]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"http:\/\/giraph.apache.org. (2016). Retrieved","author":"Giraph Apache","year":"2017","unstructured":"Apache. 2016. Apache Giraph . http:\/\/giraph.apache.org. (2016). Retrieved in May 2017 . Apache. 2016. Apache Giraph. http:\/\/giraph.apache.org. (2016). Retrieved in May 2017."},{"doi-asserted-by":"publisher","key":"e_1_2_1_2_1","DOI":"10.1145\/1150402.1150412"},{"doi-asserted-by":"publisher","key":"e_1_2_1_3_1","DOI":"10.1145\/1963405.1963488"},{"doi-asserted-by":"publisher","key":"e_1_2_1_4_1","DOI":"10.1145\/988672.988752"},{"doi-asserted-by":"publisher","key":"e_1_2_1_5_1","DOI":"10.14778\/2735471.2735477"},{"doi-asserted-by":"publisher","key":"e_1_2_1_6_1","DOI":"10.1145\/2600212.2600233"},{"doi-asserted-by":"publisher","key":"e_1_2_1_7_1","DOI":"10.1145\/2741948.2741970"},{"doi-asserted-by":"publisher","key":"e_1_2_1_9_1","DOI":"10.5555\/2490483.2490505"},{"volume-title":"Proceedings of the 2014 USENIX Conference on USENIX Annual Technical Conference (USENIX ATC'14). USENIX Association","author":"Cui Henggang","unstructured":"Henggang Cui , James Cipar , Qirong Ho , Jin Kyu Kim , Seunghak Lee , Abhimanu Kumar , Jinliang Wei , Wei Dai , Gregory R. Ganger , Phillip B. Gibbons , Garth A. Gibson , and Eric P. Xing . 2014. Exploiting Bounded Staleness to Speed Up Big Data Analytics . In Proceedings of the 2014 USENIX Conference on USENIX Annual Technical Conference (USENIX ATC'14). USENIX Association , Berkeley, CA, USA, 37--48. http:\/\/dl.acm.org\/citation.cfm?id=2643634.2643639 Henggang Cui, James Cipar, Qirong Ho, Jin Kyu Kim, Seunghak Lee, Abhimanu Kumar, Jinliang Wei, Wei Dai, Gregory R. Ganger, Phillip B. Gibbons, Garth A. Gibson, and Eric P. Xing. 2014. Exploiting Bounded Staleness to Speed Up Big Data Analytics. In Proceedings of the 2014 USENIX Conference on USENIX Annual Technical Conference (USENIX ATC'14). USENIX Association, Berkeley, CA, USA, 37--48. http:\/\/dl.acm.org\/citation.cfm?id=2643634.2643639","key":"e_1_2_1_10_1"},{"volume-title":"9th DIMACS Implementation Challenge - Shortest Paths","author":"DIMACS.","unstructured":"DIMACS. 2010. 9th DIMACS Implementation Challenge - Shortest Paths . http:\/\/www.dis.uniroma1.it\/challenge9\/download.shtml. (2010). Retrieved in May 2017. DIMACS. 2010. 9th DIMACS Implementation Challenge - Shortest Paths. http:\/\/www.dis.uniroma1.it\/challenge9\/download.shtml. (2010). Retrieved in May 2017.","key":"e_1_2_1_11_1"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 10th USENIX Conference on Operating Systems Design and Implementation (OSDI'12)","author":"Gonzalez Joseph E.","year":"2012","unstructured":"Joseph E. Gonzalez , Yucheng Low , Haijie Gu , Danny Bickson , and Carlos Guestrin . 2012 . PowerGraph: Distributed Graph-parallel Computation on Natural Graphs . In Proceedings of the 10th USENIX Conference on Operating Systems Design and Implementation (OSDI'12) . USENIX Association, Berkeley, CA, USA, 17--30. http:\/\/dl.acm.org\/citation.cfm?id=2387880.2387883 Joseph E. Gonzalez, Yucheng Low, Haijie Gu, Danny Bickson, and Carlos Guestrin. 2012. PowerGraph: Distributed Graph-parallel Computation on Natural Graphs. In Proceedings of the 10th USENIX Conference on Operating Systems Design and Implementation (OSDI'12). USENIX Association, Berkeley, CA, USA, 17--30. http:\/\/dl.acm.org\/citation.cfm?id=2387880.2387883"},{"key":"e_1_2_1_13_1","volume-title":"11th USENIX Symposium on Operating Systems Design and Implementation (OSDI 14)","author":"Gonzalez Joseph E.","year":"2014","unstructured":"Joseph E. Gonzalez , Reynold S. Xin , Ankur Dave , Daniel Crankshaw , Michael J. Franklin , and Ion Stoica . 2014 . GraphX: Graph Processing in a Distributed Dataflow Framework . In 11th USENIX Symposium on Operating Systems Design and Implementation (OSDI 14) (OSDI '14). USENIX Association, Broomfield, CO, 599--613. Joseph E. Gonzalez, Reynold S. Xin, Ankur Dave, Daniel Crankshaw, Michael J. Franklin, and Ion Stoica. 2014. GraphX: Graph Processing in a Distributed Dataflow Framework. In 11th USENIX Symposium on Operating Systems Design and Implementation (OSDI 14) (OSDI '14). USENIX Association, Broomfield, CO, 599--613."},{"doi-asserted-by":"publisher","key":"e_1_2_1_14_1","DOI":"10.14778\/2777598.2777604"},{"volume-title":"Proceedings of the 2016 USENIX Conference on USENIX Annual Technical Conference (USENIX ATC'16). USENIX Association","author":"Ju Xiaoen","unstructured":"Xiaoen Ju , Dan Williams , Hani Jamjoom , and Kang G. Shin . 2016. Version Traveler: Fast and Memory Efficient Version Switching in Graph Processing Systems . In Proceedings of the 2016 USENIX Conference on USENIX Annual Technical Conference (USENIX ATC'16). USENIX Association , Berkeley, CA, USA, 523--536. Xiaoen Ju, Dan Williams, Hani Jamjoom, and Kang G. Shin. 2016. Version Traveler: Fast and Memory Efficient Version Switching in Graph Processing Systems. In Proceedings of the 2016 USENIX Conference on USENIX Annual Technical Conference (USENIX ATC'16). USENIX Association, Berkeley, CA, USA, 523--536.","key":"e_1_2_1_15_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_16_1","DOI":"10.1145\/2465351.2465369"},{"doi-asserted-by":"publisher","key":"e_1_2_1_17_1","DOI":"10.1145\/1772690.1772751"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 10th USENIX Conference on Operating Systems Design and Implementation (OSDI'12)","author":"Kyrola Aapo","year":"2012","unstructured":"Aapo Kyrola , Guy Blelloch , and Carlos Guestrin . 2012 . GraphChi: Large-scale Graph Computation on Just a PC . In Proceedings of the 10th USENIX Conference on Operating Systems Design and Implementation (OSDI'12) . USENIX Association, Berkeley, CA, USA, 31--46. http:\/\/dl.acm.org\/citation.cfm?id=2387880.2387884 Aapo Kyrola, Guy Blelloch, and Carlos Guestrin. 2012. GraphChi: Large-scale Graph Computation on Just a PC. In Proceedings of the 10th USENIX Conference on Operating Systems Design and Implementation (OSDI'12). USENIX Association, Berkeley, CA, USA, 31--46. http:\/\/dl.acm.org\/citation.cfm?id=2387880.2387884"},{"doi-asserted-by":"publisher","key":"e_1_2_1_19_1","DOI":"10.1080\/15427951.2009.10129177"},{"doi-asserted-by":"publisher","key":"e_1_2_1_20_1","DOI":"10.5555\/2685048.2685095"},{"doi-asserted-by":"publisher","key":"e_1_2_1_22_1","DOI":"10.14778\/2212351.2212354"},{"doi-asserted-by":"publisher","key":"e_1_2_1_23_1","DOI":"10.1145\/1807167.1807184"},{"doi-asserted-by":"publisher","key":"e_1_2_1_24_1","DOI":"10.1145\/2815400.2815408"},{"doi-asserted-by":"publisher","key":"e_1_2_1_25_1","DOI":"10.1145\/2517349.2522740"},{"doi-asserted-by":"publisher","key":"e_1_2_1_26_1","DOI":"10.1145\/2723372.2735353"},{"doi-asserted-by":"publisher","key":"e_1_2_1_27_1","DOI":"10.1145\/2484838.2484843"},{"doi-asserted-by":"publisher","key":"e_1_2_1_28_1","DOI":"10.1145\/2463676.2467799"},{"doi-asserted-by":"publisher","key":"e_1_2_1_29_1","DOI":"10.1145\/2442516.2442530"},{"doi-asserted-by":"publisher","key":"e_1_2_1_30_1","DOI":"10.14778\/2732232.2732238"},{"doi-asserted-by":"publisher","key":"e_1_2_1_31_1","DOI":"10.1145\/79173.79181"},{"key":"e_1_2_1_32_1","volume-title":"6th Biennial Conference on Innovative Data Systems Research (CIDR '13)","author":"Wang Guozhang","year":"2013","unstructured":"Guozhang Wang , Wenlei Xie , Alan J Demers , and Johannes Gehrke . 2013 . Asynchronous Large-Scale Graph Processing Made Easy .. In 6th Biennial Conference on Innovative Data Systems Research (CIDR '13) . Guozhang Wang, Wenlei Xie, Alan J Demers, and Johannes Gehrke. 2013. Asynchronous Large-Scale Graph Processing Made Easy.. In 6th Biennial Conference on Innovative Data Systems Research (CIDR '13)."},{"doi-asserted-by":"publisher","key":"e_1_2_1_33_1","DOI":"10.1145\/2806777.2806849"},{"doi-asserted-by":"publisher","key":"e_1_2_1_34_1","DOI":"10.1145\/2688500.2688508"},{"doi-asserted-by":"publisher","key":"e_1_2_1_35_1","DOI":"10.14778\/2556549.2556581"},{"doi-asserted-by":"publisher","key":"e_1_2_1_36_1","DOI":"10.14778\/2733085.2733103"},{"doi-asserted-by":"publisher","key":"e_1_2_1_37_1","DOI":"10.1145\/2736277.2741096"},{"doi-asserted-by":"publisher","key":"e_1_2_1_38_1","DOI":"10.14778\/2904483.2904488"},{"doi-asserted-by":"publisher","key":"e_1_2_1_39_1","DOI":"10.1109\/SC.2014.38"},{"key":"e_1_2_1_40_1","first-page":"58","article-title":"FlashGraph: Processing Billion-node Graphs on an Array of Commodity SSDs. In Proceedings of the 13th USENIX Conference on File and Storage Technologies (FAST'15). USENIX Association, Berkeley","volume":"45","author":"Zheng Da","year":"2015","unstructured":"Da Zheng , Disa Mhembere , Randal Burns , Joshua Vogelstein , Carey E. Priebe , and Alexander S. Szalay . 2015 . FlashGraph: Processing Billion-node Graphs on an Array of Commodity SSDs. In Proceedings of the 13th USENIX Conference on File and Storage Technologies (FAST'15). USENIX Association, Berkeley , CA, USA , 45 58 . http:\/\/dl.acm.org\/citation.cfm?id=2750482.275048 Da Zheng, Disa Mhembere, Randal Burns, Joshua Vogelstein, Carey E. Priebe, and Alexander S. Szalay. 2015. FlashGraph: Processing Billion-node Graphs on an Array of Commodity SSDs. In Proceedings of the 13th USENIX Conference on File and Storage Technologies (FAST'15). USENIX Association, Berkeley, CA, USA, 45 58. http:\/\/dl.acm.org\/citation.cfm?id=2750482.275048","journal-title":"CA, USA"}],"container-title":["Proceedings of the ACM on Measurement and Analysis of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3084446","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3084446","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:30:22Z","timestamp":1750217422000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3084446"}},"subtitle":["Locally-Sufficient Graph Processing via Compute-Sync-Merge"],"short-title":[],"issued":{"date-parts":[[2017,6,13]]},"references-count":38,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,6,13]]}},"alternative-id":["10.1145\/3084446"],"URL":"https:\/\/doi.org\/10.1145\/3084446","relation":{},"ISSN":["2476-1249"],"issn-type":[{"type":"electronic","value":"2476-1249"}],"subject":[],"published":{"date-parts":[[2017,6,13]]},"assertion":[{"value":"2017-06-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}