Designing Distributed Network Algorithms
Brief description of the course:
This course will train professionals and students to think algorithmically about distributed networks. The lectures will cover key algorithms and concepts and will be taught from a designer’s perspective rather than merely an implementor’s perspective. In other words, we strive for the ambitious outcome whereby the participants will be trained to design their own distributed network algorithms when their respective work context calls for it. We will anchor our algorithm design on correctness and efficiency. The correctness is aimed at ensuring that the goal is achieved as per specification while efficiency deals with ensuring that resources like time and bandwidth are not wasted. The course will include access to a simple distributed network algorithms simulator upon which students can implement their designs and evaluate their efficiency and correctness.
Course activities (assignments & assessments):
1. Programming assignments where participants implement algorithms on a simulator. (2*30 = 60%)
2. One technical writeup on a use case for some idea covered in the course. (30%)
3. Participation in class and in online forums. (10%)
Registration start date: May 05, 2022.
Registration end date: June 24, 2022.
Course starts in the month of July 2022.
Physical or Online – Depending on the Covid protocols
Duration : 4 weeks
Rs. 15,000 + GST for corporates and individuals
50% discount for students
The course will comprise four modules detailed below.
• Basic Python programming
A course on Algorithms is preferred.
• Self-taught is fine.
• Should be familiar with basic graph algorithms like breadth first search, minimum spanning tree, shortest paths, etc.
Module 1. Introduction: SynchronousDistributed Network algorithms
The synchronous message passing network; Tree algorithms like broadcast and convergecast with pipelining; Distributed breadth first search (DBFS); the Gallagher-Humblet-Spira minimum spanning tree (MST) algorithm; the Garay-Kutten-Peleg MST algorithm for low diameter networks; the distributed Bellman-Ford and the distance vector protocol. Leader election in rings, complete networks and arbitrary networks; Local symmetry breaking: maximal independent set and colouring problems.
Module 2. Fault Toleranceand Asynchrony
Fault Tolerance: Agreement under crash failures in synchronous networks. Impossibility of agreement under 1/3 or more Byzantine faults; Byzantine Agreement when common coins can be tossed; Castro-Liskov Practical Byzantine Fault Tolerance;
The asynchronous network model; Adapting synchronous algorithms to asynchronous networks;Mutual exclusion problem and the bakery algorithm; Fischer-Lynch-Paterson impossibility of (deterministic) consensus under crash failures and a randomized consensus algorithm.
Module 3. Blockchains and Distributed Trust Applications
Byzantine agreement in cryptocurrencies and distributed ledger technologies (DLTs) through proof-of-work and proof-of-stake mechanisms; Smart Contracts, Digital Assets, and Distributed Digital Markets; Deep dive into Hedera’s Hashgraph DLTand a primer for building smart contracts on Hedera.
Module 4. Distributed Computing by Mobile Entities
Modelling issues: continuous &discrete spaces, synchrony, and capabilities of robots like visual perception and communication; Fundamental problems: rendezvous, gathering,pattern formation, exploration, search and evacuation, patrolling, and network decontamination.
Dr. John Augustine, Dept. of Computer Science & Engg., IIT Madras, Chennai 600036.
Dr. John Augustine has been a faculty member in the Department of Computer Science & Engg., 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 is interested in building a theory of distributed trust that brings together ideas from disparate fields of study ranging from distributed computing (specifically, Byzantine fault tolerance), blockchains and smart contracts, secure multi-party computation, and multi-agent systems. The goal is to understand distributed and decentralized settings where multiple parties must collaboratively work together towards common goals despite security breaches that may have compromised some parties in an adversarial manner.
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).
He represents IIT Madras on the Hedera Governance Council.
Scope of the course:
The course will be pitched for a broad audience spanning students and professionals (including those from non-CS backgrounds). It will be useful for those who are interested in designing distributed networks and algorithms.Specifically, it will be useful to those who work on:
- Setting up IoT networks
- Networks for autonomous vehicles
- Blockchains, distributed ledgers, and smart contracts. (Note: we will deep dive into Hedera.)
- A curiosity about
- how multiple computing nodes can coordinate and work together towards common goals
- and how to achieve goals even if some nodes are faulty, malicious, or moving about.
The first half of the course will emphasize the foundations. The second half will focus more on applications like distributed ledger technologies and distributed aspects of mobile agents. Elementary programming skills will be assumed.