John Augustine: Robust and Efficient Computation in Dynamic Networks with Heavy Churn

Abstract: 
Peer-to-Peer (P2P) networks — typically overlays on top of the Internet — pose some unique challenges to algorithm designers. The difficulty comes primarily from constant churn owing to the short life span of most nodes in the network. In order to maintain a well-connected overlay network despite churn at this level, the overlay must be dynamically maintained. This makes the overlay network graph an evolving graph that exhibits both edge dynamism and node churn. In this talk, we will discuss the somewhat surprising line of work in which we show how to design fast algorithms that are robust against heavy churn.

We will begin with a discussion on how to create an overlay network that has good expansion despite adversarial churn. Subsequently, assuming such an overlay network with good expansion, we will present a few basic techniques like fast information dissemination, random walks, and support estimation. Finally, we show how to use these techniques to design algorithms to solve fundamental problems like agreement, leader election, storing and retrieving data items.

Bio: John Augustine is an Associate Professor in the Department of Computer Science and Engineering at IIT Madras. He received his Ph.D. in Computer Science from the University of California at Irvine in 2006. Prior to IIT Madras, he worked as a scientist at Tata Research Development and Design Centre and also as a Research Fellow at Nanyang Technological University. He has a wide array of research interests ranging from distributed network algorithms (esp., dynamic network algorithms), online algorithms, computational geometry, combinatorial optimization, and also applied algorithms, esp., in the context of inexact computing.