º£½ÇÉçÇø

[Tutorial] Byzantine Resilient Algorithms: Foundations and Applications

Tuesday, May 31, 2022

11:00 am - 1:00 pm

Speaker

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

Location

Hybrid: or PGH 550

Tutorial Description

The tutorial is aimed at a general audience with no prior knowledge of distributed computing.

Over forty years ago, Lamport, Pease and Shostak proposed the Byzantine Generals Problem. In its simplest form known as the Byzantine Agreement (BA) Problem, we have n nodes that propose bits individually and one of the proposed bits must be agreed upon globally despite the presence of a significant (but bounded) number of malicious nodes (a.k.a Byzantine nodes) that can behave arbitrarily (including colluding with each other). BA has had a profound impact on distributed computing and its applications and we will explore it in two parts with the first part focusing on the foundations while the second part focuses on cryptocurrencies and other modern applications.

The first part will focus on the foundations comprising the impossibilities that mark our boundaries and the algorithms that push to the limits within those boundaries. Specifically, we will show why BA can be solved iff the number of Byzantine nodes f is fewer than n/3 in a synchronous system without any cryptography. With digital signatures, we can do better wherein BA is solvable iff f < n/2. Without synchrony, the situation is more dire and we show that deterministic BA algorithms fail even with just one faulty node that doesn’t have to behave maliciously (other than potentially fail at an inopportune time).

Despite the many impossibilities and negative results, some ingenious developments have assured in some widely used applications that are based on BA. The flagship application is cryptocurrencies and the underlying blockchain technology that allow us to maintain distributed ledgers. In the second part of this tutorial, we will present how distributed ledgers can be maintained in two different settings. The first setting will be the case when the n nodes are known to each other – the so-called permissioned setting. The second setting is the one that primarily drives cryptocurrencies – the so-called permissionless setting in which any node can join or leave at any time without any permission from any central authority.

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).