CAREER:Foundation of Communication-Efficient Distributed Computation and Monitoring

Indiana University, Bloomington IN

Investigators

Abstract

Through the massive use of mobile devices, data clouds, and the rise of the Internet of Things, large amounts of data have been generated, digitized, and analyzed for the benefit of society. As data are often collected and maintained at different sites, communication has become necessary for nearly every computational task. Moreover, decision makers naturally want to maintain a centralized view of all the data in a timely manner, which requires frequent queries on the distributed data and, in the extreme, continuous monitoring of the query output. The cost of communication has naturally become the bottleneck for such applications. This project aims to develop communication-efficient solutions for distributed computation and monitoring. The products will be integrated into a trilogy of courses in the foundations of data science. The project will involve training students at all levels, with an emphasis on gender diversity and participation of underrepresented groups. This project targets three fundamental aspects of distributed computation: (1) the tradeoffs between the communication cost and the number of rounds of the computation in distributed one-shot computation, (2) the power of data partitioning, and (3) the connections between distributed one-shot computation and continuous monitoring. The PI will approach these directions via the study of fundamental algorithmic problems in databases, data mining, networking, and machine learning. A systematic theory of communication-efficient computation and monitoring has the potential to impact a wide range of rapidly developing areas in theoretical foundations of big data, including streaming algorithms, sketching algorithms, and parallel and distributed computing. It will also deepen our understanding of communication complexity and information theory in theoretical computer science and mathematics. 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.