mca Syllabus

Distributed Algorithms
Code: PGCS105H
Weekly Contact Hour: 3L
Credit: 3

Course Contents
Introduction, Types of concurrency, Characteristics of Distributed systems, Challenges posed by distribution, Importance of theoretical methods for distributed algorithms (2 generals problem), Basic of discrete mathematics - posets and lattices. Distributive property. Approaches to reasoning - MOdel driven, different types of models. Dimensions to classifying distributed algorithms - IPC method, timing, Failure models and Problems addressed. Synchronous vs Asynchronous distributed systems Synchronous
Algorithms - Ring only, Synchronous Models, proof methods, failure types etc, Leader election in synchronous ring – LCR algorithm, Hirshberg-Sinclair algorithm, Non-comparison algorithms - Time slice and Variable speeds, Lower bound discussion, Synchronous Algorithms - General Networks, Leader election in a general network - flooding algorithm, Reducing the complexity of complete flooding, MST algorithm Dealing with Link and process failures in consensus problems Asynchronous Shared Memory, Mutual Exclusion, Resource Allocation Async Network Algorithms, FIFO, Broadcast vs Multicast, Leader Election - Ring vs arbitrary network MST, Minimum Spanning Tree Algorithms Logical time, Vector clocks, Matrix clocks, DD clocks Global Global Snapshots, Chandy and Lamports algorithm Stable predicates or properties, Termination detection Self stabilization.

Books
1. Nancy A. Lynch, “Distributed Algorithms”, Morgan Kaufmann
2. Nicola Santoro, “Design and Analysis of Distributed Algorithms”, Wiley-Interscience
3. Gerard Tel, “Introduction to Distributed Algorithms 2nd ed”, Cambridge University Press
4. C. Xavier and S. S. Iyengar, “Introduction to Parallel Algorithms”, Wiley-Interscience