Enabling Robust and Efficient Distributed Computation in Dynamic Peer-to-Peer Networks

When: Friday, October 2, 2015
Where: PGH 232
Time: 11:00 AM

Speaker: Prof. Gopal Pandurangan, University of Houston

Host: Prof. Ernst Leiss

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. In P2P networks, the topology changes at a rapid rate due to high churn (i.e., nodes joining and leaving the network continuously over time). Performing robust and efficient non-trivial distributed computation in such highly dynamic networks is very challenging.

Motivated by the above challenge, this work studies distributed protocols for constructing and maintaining dynamic network topologies with good expansion properties in P2P networks. The goal is to maintain a sparse (bounded degree) expander topology despite heavy churn. The churn is assumed to be controlled by an adversary that has complete knowledge and control of what nodes join and leave and at what time and has unlimited computational power, but is oblivious to the random choices made by the algorithm.

In this talk I will present a randomized distributed protocol that guarantees with high probability the maintenance of a {constant} degree graph with high expansion even under continuous high adversarial churn. The protocol can tolerate a churn rate of up to O(n/\polylog(n)) per round (where n is the stable network size). The protocol is efficient, lightweight, and scalable, and it incurs only O(\polylog(n)) overhead for topology maintenance: only polylogarithmic (in n) bits needs to be processed and sent by each node per round and any node's computation cost per round is also polylogarithmic. The given protocol is a fundamental ingredient that is needed for the design of efficient fully-distributed algorithms for solving fundamental distributed computing problems such as agreement, leader election, search, and storage in highly dynamic P2P networks and enables fast and scalable algorithms for these problems that can tolerate a large amount of churn.

This work will appear in the upcoming IEEE Symposium on the Foundations of Computer Science (FOCS), Oct. 2015.

Bio:

Prof. Gopal Pandurangan is an Associate Professor in the Department of Computer Science at the University of Houston. He received his Ph.D. in Computer Science from Brown University in 2002. He has held faculty and visiting positions at Nanyang Technological University in Singapore, Brown University, Purdue University, and Rutgers University. He is a Senior Member of the ACM and the IEEE. He has made fundamental research contributions to the theory of distributed computing and networks.

In particular, his work has led to new and uniform techniques for showing lower bounds for distributed algorithms, which has become standard in the field. He has also made several contributions to the design and analysis of distributed algorithms for fundamental distributed computing problems and to developing the distributed computing foundations of dynamic networks.

He has published more than 90 refereed research papers in the areas of theory and algorithms, distributed computing, networks, large-scale data, and computational biology. His work has appeared in JACM, SICOMP, ACM TALG, STOC, FOCS, SODA, PODC, SPAA, INFOCOM, and RECOMB. He has supervised and graduated three Ph.D. students and mentored and worked with several other Ph.D. students and postdoctoral fellows. His research has been supported by competitive research grants from the US National Science Foundation, US-Israeli Binational Science Foundation, and the Singapore Ministry of Education.