Collaborative Research: AF: Small: Efficient Massively Parallel Algorithms

Modern computing systems have moved beyond single-coresingle-processor devices to more modern multicore processors operatingin networked systems and available in warehouse-scale cloudspopularized by companies such as Amazon or Google. Future advances incomputing power will likely come not mainly from faster devices, butby processing in inherently parallel and distributed environments, andby understanding how to exploit the parallelism inherent in manyalgorithmic problems. Simultaneously, the world has entered the era of``big data'' with large data sets on which previously unthinkablesized problems with great economic and social impact need to besolved. This new parallel, interconnected, big-data world speciallyrequires fundamental research on their algorithms, which are bothparallel and distributed.The algorithms in this project address thisimportant research challenge by building and developing new generalframeworks for massively parallel computation.As the main thrust of this project, the investigators will designfundamental and efficient algorithms for core massively parallelcomputations especially in the practical Massively ParallelComputation (MPC) framework. In particular, they will consider methodsfor reducing the number of rounds in the MPC model as well astradeoffs between rounds, memory, number of machines, andcommunication time. They seek to find new MPC algorithms for basicgraph problems such as connectivity, matching, vertex cover, maximalindependent set, as well as other basic string matching problems suchas suffix trees, edit distance, and longest commonsubsequence. Another focus is dynamic algorithms for massivelyparallel computation, which modify the output efficiently in aparallel/distributed setting based on frequent modifications of theinput and with direct applications in evolving social networks, theWorld Wide Web, road networks, scheduling systems among others. Theinvestigators will augmenting current parallelenvironments/architectures with better data structures andabstractions to allow simplified and fast implementations of thecurrent fundamental algorithms that can be used in practicevia open-source codes. The discoveries in this project will beintegrated into existing and new courses and books about parallelalgorithms, distributed algorithms, and foundations of big data. Thewealth of attractive open problems in these areas will provide bothchallenging research topics and intuitive accessible problems toinspire students to enter research in computer science andmathematics. In particular the project will involve Ph.D. students andpost-docs, undergraduate students, and even high-school students(especially students among minorities and women), many of whom willcontinue their research at other academic institutions and researchcenters, further broadening the impact of this research.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.