Seminar Series Autumn 22
Abstract
Byzantine fault tolerance has been studied extensively for over four decades. Much of the work is centered on Byzantine Agreement and related problems like State Machine Replication. These works have established mechanisms for trustworthy computation in distributed environments despite the presence of malicious nodes. Does this distributed trust paradigm make sense in broader contexts? In this talk, we will look at three vignettes from disparate domains that provide us with affirmative evidence.
We will begin with classical distributed graph computing in the congested clique model and show how we can approach the problem of connectivity despite the presence of Byzantine nodes. We will then present a fully decentralized mechanism to build sparse overlay networks that are resilient to Byzantine failures. We will conclude with techniques for rank aggregation wherein we obtain a global ranking by aggregating pair-wise comparisons of voters over a set of objects. Our approach provides reliable ranking as long as the proportion of Byzantine voters is strictly less than a half.
These are joint works with Soumyottam Chatterjee, Arnhav Datar, Anisur Rahaman Molla, Gopal Pandurangan, Arun Rajkumar and Yadu Vasudev. They have appeared in DISC, SPAA, and Neurips — all recently in 2022.
Speaker
Prof. John Augustine
John Augustine is a professor in the Department of Computer Science and Engineering (CSE) at the Indian Institute of Technology Madras. He holds a PhD from the Donald Bren School of Information and Computer Sciences at UC Irvine. His research interests are in distributed algorithms specifically focusing on distributed trust issues that emerge in settings where participants may behave maliciously. He has co-authored many refereed articles that have appeared in highly reputed conferences (SODA, FOCS, PODC, NEURIPS, DISC, SPAA, IPDPS, etc.) and journals (Algorithmica, SICOMP, TCS, JPDC, TPDS, etc). He was the chair of the distributed computing track at ICDCN 2022 and is currently serving as an associate editor at the Journal of Parallel and Distributed Computing. At IIT Madras, he is a founding member of the Cryptography, Cybersecurity, and Distributed Trust group (CCD) as well as the Blockchain Innovation Centre (BiC). He is also affiliated with the Theory group in CSE.