The National Science Foundation (NSF) recently awarded UI computer science professor Sriram Pemmaraju $330,000 for his research project entitled "The Communication Cost of Distributed Computation". This collaborative (Medium) proposal, with collaborators Gopal Pandurangan (University of Houston) and Peter Robinson (Augusta University), is funded by the Algorithmic Foundations program at the NSF.

Distributed algorithms are ubiquitous. They underlie the operation of modern communication networks (e.g., the internet), peer-to-peer networks (which power blockchains), and wireless and sensor networks. 

In a distributed algorithm, each machine has access to only a small portion of the input and by strategically interleaving computation and communication, the machines collaborate to solve large-scale problems defined on the entire input. In many applications, communication is a costly resource, and needs to be used frugally. This project will develop distributed algorithms whose communication cost is as small as possible, while also investigating the inherent limits to how small the communication cost can be. 

The project will apply these approaches to classical problems in distributed computing (e.g., maximal independent set, leader election, spanners, etc.), as well as fundamental distributed graph optimization problems (e.g., minimum spanning tree, shortest paths, minimum vertex cover, etc.). Many of these problems have been studied extensively for decades and are widely used primitives in distributed applications, however focusing on their communication cost is expected to yield new insights into the design of efficient distributed algorithms for these problems.