Seminar - Summer 2014

Distributed Algorithmic Foundations of Dynamic Networks

When: Wednesday, June 4, 2014
Where: PGH 550
Time: 11:00 AM

Speaker: Prof. Gopal Pandurangan, Brown University and Nanyang Technological University

Host: Prof. Rakesh Verma

Many of today's real-world communication networks are highly dynamic, i.e., their network topology changes continuously over time. Examples include Peer-to-Peer (P2P) networks, distributed grid networks, and ad hoc wireless and sensor networks. Such networks are now widely used in various applications, including sharing data and resources, search and storage, high performance computing, Internet telephony, environment monitoring and management. In P2P networks (e.g., Skype, BitTorrent), the topology changes at a rapid rate due to continuous joining and leaving of nodes; in PC-based grid computing, nodes can join and leave (or fail) the grid continuously; in ad hoc sensor and vehicular networks, the topology changes dynamically due to failure or mobility of the nodes. Performing robust and efficient non-trivial distributed computation in such highly dynamic networks is challenging. In this talk, I will give an overview of our recent results that make progress towards developing an algorithmic theory of dynamic networks. First, I will present a rigorous theoretical framework for studying dynamic networks. Then I will present efficient techniques and algorithms for solving the fundamental agreement problem in dynamic networks. I will also present efficient algorithms for key problems such as information spreading, Byzantine agreement, search, and storage. To complement our algorithms, I will also present almost tight lower bounds for agreement and information spreading.

Bio:

Prof. Gopal Pandurangan is affiliated with the Theoretical Computer Science research group in the Mathematical Sciences Division at Nanyang Technological University. He is currently a research fellow at the Institute of Experimental and Computational Research in Mathematics (ICERM) at Brown University and also a visiting faculty in the Computer Science Department at Brown University. He received his Ph.D. from Brown University (2002), Masters from SUNY Albany, and B.Tech. from IIT Madras, all in Computer Science. He is a senior member of the ACM and the IEEE. His research interests are in the design and analysis of algorithms, distributed computing, large-scale data processing, communication networks, real-world networks, and computational biology.