º£½ÇÉçÇø

[Seminar] The Node Capacitated Clique: Models, Algorithms, and Extensions

Wednesday, June 1, 2022

11:00 am - 12:00 pm

Speaker

John Augustine
Associate Professor of Computer Science and Engineering
Indian Institute of Technology Madras

Location

Hybrid: or PGH 550

Abstract

Traditional distributed computing algorithms assume that the network is a fixed graph on the nodes of the network. The reality is more fluid because most communications are over the Internet where any two nodes can communicate if they know each others’ IP addresses. In this talk, we will introduce the node capacitated clique model that captures this situation better than the classical distributed computing models. In the most basic version of the model (the so-called NCC_1 model), we have n synchronously operating nodes identified by {1, 2, …, n}. Any node can communicate with any other node subject to the following constraints. Each node can (i) send at most O(log n) messages, (ii) receive at most O(log n) messages, and (iii) each message can comprise at most O(log n) bits. Under this basic model, we will show how to perform basic operations like aggregation and dissemination of information. Using these basic operations, we show how to solve the minimum spanning tree problem in polylog(n) rounds.

Time permitting, we will briefly discuss the NCC_0 model where nodes are unaware of each others’ IP addresses and the hybrid model that combines classical distributed computing models with NCC_1.

About the Speaker

Dr. John Augustine has been a faculty member in the Department of Computer Science & Eng., IIT Madras, since 2011. Prior to that he has held positions in academia (Colby College, USA, and Nanyang Tech Univ, Singapore) and industry (Tata Research, Pune, India). He holds a PhD from the Donald Bren School of Information and Computer Sciences, UC Irvine, USA. His research interest is in distributed network algorithms interpreted broadly to encompass algorithms for peer-to-peer networks, static and dynamic networks, distributed algorithms for mobile entities, and security aspects of network algorithm design (specifically, Byzantine fault tolerance). He has published extensively in several top-tier conferences like PODC, SODA, FOCS, SPAA, DISC, IPDPS, and ICDCS and prestigious journals like SICOMP, JCSS, Algorithmica, JPDC, TPDS, and TCS. He has served on the Program Committee for numerous conferences and as the Program Committee Co-Chair for ICDCN 2022. He is an associate editor at the Journal of Parallel and Distributed Computing (JPDC).