Distributed Algorithms — Lecture Notes and Course Materials
This page provides lecture notes and course materials for Distributed Algorithms. The course introduces fundamental models of distributed computation and algorithms for synchronous and asynchronous systems.
The material covers distributed network algorithms, shared-memory models, leader selection, breadth-first search, shortest paths, minimum spanning trees, and asynchronous distributed computation. Additional material may be added to cover advanced topics in the syllabus.
Course Information
Course: Distributed Algorithms
Programme: Master of Technology (Computer Science & Engineering)
Prerequisites
Course Description
Distributed Algorithms studies algorithms executed by multiple computing processes that communicate with one another or operate through shared memory. Unlike sequential algorithms, distributed algorithms must consider concurrency, communication, synchronization, timing assumptions, lack of global knowledge, and possible failures.
The course begins with models of synchronous and asynchronous distributed computation and develops basic algorithms for leader selection, breadth-first search, shortest paths, and minimum spanning trees. It also introduces asynchronous shared-memory computation and related distributed algorithms.
Learning Outcomes
- Understand the fundamental models of distributed computation.
- Distinguish between synchronous networks, asynchronous networks, and asynchronous shared-memory systems.
- Understand and analyse distributed leader-selection algorithms.
- Understand distributed breadth-first search, shortest-path, and minimum-spanning-tree algorithms.
- Understand the principles of asynchronous shared-memory computation.
- Recognize the challenges introduced by concurrency, communication delays, and failures in distributed systems.
- Understand the relationship between distributed network models and shared-memory models.
Lecture Notes
Module 1: Models of Distributed Computing
Topics Covered
Lecture 1It Introduces distributed algorithms: how they differ from uniprocess computing, their real-world applications, synchronous vs. asynchronous communication, network models, and complexity measures (time, message, bit, space).
Lecture 2It covers leader election: why and when it's needed, the ring network model, the LCR algorithm (pseudocode, worked example, O(n²) complexity), and the Bully algorithm with a step-by-step election example.
Module 2: Basic Algorithms for Distributed Networks
Topics Covered
Lecture 3:Introduces the theory of asynchronous distributed computing, covering both the message- passing and shared-memory models, where processors interact through communication objects like read/write registers. It formalizes the notions of runs, views, and full-information protocols to reason about what a processor can know at any point in an execution, and defines wait-free emulation as a way to compare the power of different models.
Lecture 4:- BFS spanning tree setup and algorithm
- Time/message complexity analysis
- Applications: broadcast, global computation, leader election, diameter computation
- Shortest paths via Bellman-Ford (with correctness/complexity)
- Minimum spanning tree strategy, with a simple diagram illustrating the component-merging step
Module 3: Asynchronous Shared-Memory Algorithms
Topics Covered
Lecture 5:- The asynchronous shared memory system, with the processes/ports/shared-variables
- The I/O automaton formalization (states, transitions, actions)
- The worked example (single shared variable, decide/access/init actions) with states and full transition table laid out clearly
- Agreement and validity properties