Title: Three Vignettes from the Distributed Trust Paradigm of Computing
Begin: Friday, 16 of December 2022 (2:00 PM)
Room: F0.231
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.