2013 · 36 citations · 25 references
ComputingCloud ComputingComputer ScienceCloud InfrastructureDistributed SystemsParallel ComputingCompute Resource ManagementDistributed ComputingGraph AlgorithmsGraph AnalyticsResource SchedulingWorkload SchedulingBulk Synchronous Parallel AlgorithmsBulk Synchronous Parallel ModelBulk Synchronous ParallelismDistributed Graph ProcessingGraph PartitioningGraph ProcessingScalabilityVertex Processing
Large-scale graph analytics is a central tool in many fields, and exemplifies the size and complexity of Big Data applications. Recent distributed graph processing frameworks utilize the venerable Bulk Synchronous Parallel (BSP) model and promise scalability for large graph analytics. This has been made popular by Google's Pregel, which provides an architecture design for BSP graph processing. Public clouds offer democratized access to medium-sized compute infrastructure with the promise of rapid provisioning with no capital investment. Evaluating BSP graph frameworks on cloud platforms with their unique constraints is less explored. Here, we present optimizations and analyses for computationally complex graph analysis algorithms such as betweenness-centrality and all-pairs shortest paths on a native BSP framework we have developed for the Microsoft Azure Cloud, modeled on the Pregel graph processing model. We propose novel heuristics for scheduling graph vertex processing in swaths to maximize resource utilization on cloud VMs that lead to a 3.5x performance improvement. We explore the effects of graph partitioning in the context of BSP, and show that even a well partitioned graph may not lead to performance improvements due to BSP's barrier synchronization. We end with a discussion on leveraging cloud elasticity for dynamically scaling the number of BSP workers to achieve a better performance than a static deployment, and at a significantly lower cost.
25
Collective dynamics of ‘small-world’ networks
Duncan J. Watts, Steven H. Strogatz · Nature · 1998 · 43.2K citations
Sanjay Ghemawat · Communications of the ACM · 2008 · 18.5K citations · Full text
The PageRank Citation Ranking : Bringing Order to the Web
Lawrence M. Page, Sergey Brin, Rajeev Motwani et al. · 1999 · 12.7K citations
Michael Armbrust, Armando Fox, Rean Griffith et al. · Communications of the ACM · 2010 · 9K citations · Full text