Parallelizing Sequential Graph Algorithms


This talk addresses two issues in connection with parallel graph computations. (1) Is it possible to simplify parallel programming, from think parallel to think sequential? That is, we want a parallel system such that we can plug in sequential graph algorithms and the system parallelizes computations across a cluster of processors, without degradation in performance or functionality of existing graph query engines. (2) Does there exist a parallel model that optimizes computation by adaptively switching among BSP (Bulk Synchronous Parallel), AP (Asynchronous Parallel) and SSP (Stale Synchronous Parallel) models? That is, the model retains the advantages of BSP, AP and SSP, while it reduces stragglers and redundant stale computations inherent to BSP, AP and SSP. We answer both questions in the affirmative.


Professor Wenfei Fan is the Chair of Web Data Management at the University of Edinburgh, UK, and the Chief Scientist of Beijing Advanced Innovation Center for Big Data and Brain Computing, China. He is a Fellow of the Royal Society, a Fellow of the Royal Society of Edinburgh, a Member of Academia Europaea, an ACM Fellow, a National Professor of the 1000-Talent Program and a Yangtze River Scholar, China. He received his PhD from the University of Pennsylvania (USA), and his MSc and BSc from Peking University (China). He is a recipient of ERC Advanced Fellowship in 2015, the Roger Needham Award in 2008 (UK), the Outstanding Overseas Young Scholar Award in 2003 (China), the Career Award in 2001 (USA), and several Test-of-Time and Best Paper Awards, including the Alberto O. Mendelzon Test-of-Time Award of ACM PODS 2015 and 2010, Best Paper Awards for SIGMOD 2017, VLDB 2010, ICDE 2007 and Computer Networks 2002. His current research interests include database theory and systems, in particular big data, data quality, data integration, distributed query processing, query languages, recommender systems, social networks and Web services.