Invited Talk by Prof. Sriram V Pemmaraju on Designing Distributed Algorithms for the Congested Clique

Title: Designing Distributed Algorithms for the Congested Clique
Speaker: Prof. Sriram V Pemmaraju, University of Iowa
Host Faculty: Dr. Sathya Peri
Room No: Room 118 in academic block A.
Time: 14:30

Abstract:

The past few years have witnessed a flurry of research on the design of algorithms in a simple distributed model of computing now known as the Congested Clique model. As the name suggests, the underlying communication network is a clique with the restriction that in each round, each communication link can carry a single message of size O(log n) bits (in each direction). The motivation for studying problems and algorithms in the Congested Clique model is gain a better understanding of congestion as an obstacle to distributed computing. Many classical graph problems such as minimum spanning tree (MST), shortest paths, and graph coloring have been considered in the Congested Clique model. In this talk, I will use MST as an example to illustrate techniques such as random sampling and linear sketching for designing fast MST algorithms in the Congested Clique model. I will then make connections between Congested Clique model and well known models of parallel and distributed computing such as MapReduce and the BSP model, and the more recently introduced k-machine model.

Speaker’s Bio:

Sriram Pemmaraju is a professor in computer science at the University of Iowa, US and the director of graduate studies there. His research is on theoretical aspects of distributed algorithms, especially the role of randomization in the design of these algorithms and the use of communication complexity and information-theoretic techniques to prove distributed computing lower bounds. His research is supported by the National Science Foundation and National Institutes of Health and it has received several best paper awards. He has mentored 10 PhD students so far and has received several outstanding graduate mentor nominations.

Dates:
Wednesday, June 14, 2017 - 14:30