Two faculty from the Department of Computer Science at UIowa received a National Science Foundation (NSF) grant to research distributed random sampling. Dr. Sriram Pemmaraju and Dr. Sourya Roy will collaborate in designing efficient random sampling algorithms that run on a distributed collection of machines.
“Our project bridges two somewhat separate research communities in theoretical computer science, random sampling, and distributed computing,” explain Drs. Pemmaraju and Roy.
How to Efficiently Ensure that Random Choices are Unbiased
The challenge in distributed random sampling is to ensure that the computed random choices are unbiased, even when the task is scaled to run in parallel over multiple machines.
In an analogy, Dr. Pemmaraju explains: “Players starting a card game expect the deck to be ‘well shuffled,’ meaning they expect the sequence of cards to not be biased in favor of one type of sequence (e.g., lots of diamonds appearing early) over another. In other words, we expect the card shuffling process to randomly sample a card sequence such that every card sequence is equally likely to be sampled. Similarly, the starting point for many computational tasks is randomly sampling an object (e.g., a sequence of cards) from a very large set of objects (e.g., all possible card sequences).”
Random sampling from complex probability distributions is a fundamental task not just in computer science, but also in disciplines such as biology, epidemiology, mathematics, physics, and statistics. In fact, the most well-known class of methods in this area, called Markov chain Monte Carlo (MCMC) methods, were developed by physicists at the Los Alamos National Lab in 1953 for simulating the interaction of molecules on early supercomputers.
“There is now a rich body of literature spanning theoretical computer science, mathematics, and statistics on the design of efficient algorithms for random sampling from complex probability distributions. However, as the scale of sampling problems grows, algorithms that run on a single machine may not be scalable. Instead, we need algorithms that run in parallel on many cooperating machines. Going back to the analogy from earlier, imagine that we want to shuffle the deck of cards much faster by having all players shuffle parts of the deck in parallel while occasionally passing around cards. How can we ensure that this distributed shuffling process is extremely fast while being equally likely to produce every card sequence?” says Dr. Pemmaraju.
A Collaboration of Two Specializations in Theoretical Computer Science
Pemmaraju and Roy are both theoretical computer scientists who share a common technical language and a basic set of tools and techniques to use for their research. Pemmaraju's expertise in distributed computing will complement Roy's knowledge of areas such as graph expansion and spectral graph theory, which play a key role in the analysis of random sampling algorithms.
Dr. Pemmaraju says: "I have been working on the theoretical foundations of distributed computing for about 2 decades. I have never worked on random sampling problems, though I have found the area fascinating because of my interest in probability and randomization. This grant allows me to learn the latest techniques in random sampling and combine these with my knowledge of distributed computing to design efficient distributed random sampling algorithms. I also look forward to collaborating with Sourya Roy and the post-doctoral fellows and graduate students we hope to soon recruit for this project."
Dr. Sourya Roy explains that his research primarily focuses on understanding pseudo-randomness and its connections with other areas of theoretical computer science. “Topics such as graph expansion, spectral theory, and derandomization methods, which I regularly study in my research, also play a crucial role in both designing sequential sampling algorithms and developing efficient distributed algorithms for other tasks. This grant will allow me to explore how these tools can be leveraged to design efficient distributed sampling algorithms—an exciting new research direction.
“I began learning about distributed algorithms after I joined the University of Iowa and started collaborating with Sriram Pemmaraju. This project will further strengthen this collaboration and create new synergies among several research topics that Sriram and I are excited about."
The Department of Computer Science at the University of Iowa’s College of Liberal Arts and Sciences has a robust research program with a history of strong external funding, including from the NSF. The Department is honored to have faculty specializing in theoretical computer science who bring their expertise to solving real-world problems, such as distributed random sampling.