About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Performance Evaluation Review
Conference paper
Hieroglyph: Locally-Sufficient Graph Processing via Compute-Sync-Merge
Abstract
Mainstream graph processing systems (such as Pregel [3] and PowerGraph [1]) follow the bulk synchronous parallel model. This design leads to the tight coupling of computation and communication, where no vertex can proceed to the next iteration of computation until all vertices have been processed in the current iteration and graph states have been synchronized across all hosts. This coupling of computation and communication incurs significant performance penalty. Fully decoupling computation from communication requires (i) restricted access to only local state during computation and (ii) independence of inter-host communication from computation. We call the combination of both conditions local sufficiency. Local sufficiency is not efficiently supported by state of the art. Synchronous systems, by design, do not support local sufficiency due to their intrinsic computation-communication coupling. Even systems that implement asynchronous execution only partially achieve local sufficiency. For example, PowerGraph's asynchronous mode satisfies local sufficiency by distributed scheduling.