Intructor: John Augustine. Contact Details
Teaching Assistants:
Shashank Rahul Mishra (cs20m058)
Sukanya Sinha (cs20m066)
Shivam Cholin (cs20m061)
(Note: you can construct the TAs’ emails by concatenating their respective roll numbers with @smail.iitm.ac.in.)
Slot: “E”. On average, there will be three lectures per week followed by one tutorial.
Google Meet Link: https://meet.google.com/fua-wawj-swj (Note: instructions to join class may change. Stay tuned for updates.)
Miro Board Links
(For now, these boards are password protected. Note that the collaboration board can be edited by anyone with the password. If you wish to protect your stuff, maintain a copy in a personal board.)
Please see my note on academic honesty. You are required to read it carefully and abide by it both in letter and spirit.
Distributed Network Algorithms by Gopal Pandurangan. Freely available online.
Notes on Theory of Distributed Systems by James Aspnes. Freely available online.
Principles of Distributed Computing (lecture collection) from ETH Zurich by Roger Wattenhofer and Mohsen Ghaffari. Freely available online.
Distributed Computing: Fundamentals, Simulations and Advanced Topics, 2nd edition, by Jennifer Welch and Hagit Attiya.
Please fill this google form to report errors that you spot as you read the textbooks/references or in the Miro lecture board.
The world around us is highly interconnected in many ways. Our brain is a massive network of neurons. Our society is made up of people who form friendships leading to social networks. And of course, computers are interconnected to form computer networks, peer-to-peer networks (such as Bitcoin) and of course the ubiquitous Internet. Such networks have three essential ingredients:
Decision making entities (that we call nodes),
Connections between these entities (that we call edges or links), and
Communication mechanisms (typically by passing messages).
It is quite natural now to view the network as a graph with some computational capabilities. Each individual node performs its actions based on inputs that it receives from its environment, and messages it receives over time from its neighbours. These actions performed by these individual nodes are expected to produce some outcome that is globally relevant. Our ability to think is one such outcome of individual neurons firing away at appropriate times and in some innately coordinated manner. The outcomes we will consider will be more modest and concrete. An illustrative example – one that we will consider in some depth – is to construct a minimum spanning tree of the network graph. The behaviour of such a distributed system of nodes, links and communication mechanisms is dictated by the algorithm executed by each node in the system. Such algorithms are said to be distributed because each individual node executes a copy of the algorithm.
We will study the design and analysis of such distributed algorithms. Our main focus will be on algorithms pertaining to computer networks. We will also touch upon how we can design algorithms that are secure despite the presence of malicious nodes.
The course will comprise three modules. The first two modules will focus on core distributed algorithms topics. Specifically, we will study algorithms in the CONGEST model in the first module. The second module will cover other non-faulty computing models. The third module will focus on fault tolerance, i.e., how to design algorithms that can cope when a subset of the nodes are faulty. We will consider two types of faults: crash failures where faulty nodes just stop sending messages and Byzantine failures where faulty nodes become malicious.
There will be three modules with each module accounting for about 30 marks. The first module is likely to be worth a bit more because it will be longer.
Each module will comprise assignment(s) (~ 10 marks), one recall test (~ 5 marks) and one module test ( 15 marks).
You are expected to actively participate in online discussions on tutorials, assignment problems, and class project. We will use element for online discussions. Class participation (including online discussions) will count for ~10 marks.