Distributed Algorithms for Networks with Heavy Churn
COM1 Level 2
SR8, COM1-02-08
John Augustine earned his PhD in theoretical computer science in 2006 from the Donald Bren School of Information and Computer Science, University of California, Irvine, USA. Since then, his career has spanned both academia and industry. In 2011, he joined IIT Madras as an assistant professor in the Department of Computer Science and Engineering. Prior to IIT Madras, he spent two years as a scientist at Tata Research Development and Design Centre, Pune, India and two years as research fellow at Nanyang Technological University, Singapore. His research interests are in theoretical computer science, particularly designing and analyzing algorithms.
In this talk, he will present an overview of results that have shaped our understanding of algorithms for dynamic networks with churn. These algorithms and models are inspired largely from peer-to-peer networks in which users are continuously joining and leaving. We will begin with a description of our dynamic network with churn (DNC) model and
present a couple of fundamental algorithmic tools, namely, information spreading and random walks, that have played foundational roles in many of our algorithms. These tools are robust in the sense that they work well despite adversarially controlled churn and network dynamism. As applications of these algorithmic tools, we will explore fully distributed algorithms for a wide range of distributed computing problems in the DNC model including agreement, leader election, storage and search, and expander maintenance.