CSL7920: Distributed Algorithms (Autumn 2023)

Syllabus

• Introduction to Distributed Computing Models: Model of a distributed system: asynchronous message-passing model, Time and message complexity, Safety and liveness properties, Clock Synchronization
• Leader Election Logical Clocks and Causality: Leader election in rings, Asynchronous leader election with identities, Synchronous leader election by abusing the synchronous model, Logical clocks and vector clocks, Snapshots and synchronization
• Message Ordering and Group Communication: Termination Detection Algorithms and Reasoning with Knowledge
• Distributed Mutual Exclusion Algorithms: Lamport’s algorithm, Ricart–Agrawala algorithm, and Deadlock Detection Algorithms
• Global Predicate Detection: Modalities on predicates, Centralized algorithm for relational predicates, Conjunctive predicates, Distributed algorithms for conjunctive predicates
• Distributed Shared Memory: Memory consistency models, Shared memory mutual exclusion and Wait-freedom
• Checkpointing and Rollback Recovery: Checkpoint-based recovery and Log-based rollback recovery
• Consensus and Agreement: Agreement in a failure-free system (synchronous or asynchronous), Agreement in (message-passing) synchronous systems with Failures, Agreement in asynchronous message-passing systems with failures, Wait-free shared memory consensus in asynchronous systems
• Distributed Programming Environments: Communication primitives, selected case studies

Learning Materials

Textbook

Reference Books

• N. LYNCH, (1996), Distributed Algorithms, Morgan Kaufmann, 1st Edition.
• G. TEL, (2000), Introduction to Distributed Algorithms, Cambridge University Press, 2nd Edition.

Attendance Requirement

As per the notification from academics 100% attendance is mandatory. If you have genuine reason please take leave approval as per academics rule.

Grading Policy

Research Paper Demonstration/ Presentation

Students have to read recent research articles from a good venue. Prepare a presentation or demonstration for the whole class. The following venues can be considered:

• Conferences
  • ACM Symposium on Principles of Distributed Computing
  • International Symposium on Distributed Computing
  • IEEE International Conference on Distributed Computing Systems
  • IEEE International Parallel and Distributed Processing Symposium
  • ACM International Symposium on High Performance Distributed Computing
  • ACM International Conference on Distributed Event-Based Systems
• Journals
  • IEEE Transactions on Parallel and Distributed Systems
  • Journal of Parallel and Distributed Computing
  • International Journal of Distributed Systems and Technologies
  • Distributed Computing, Springer

Note that the topics must be related to the course content.

Class Quizzes (Slido)

• There will be 3-5 questions in every class.
• Topic related to the same class or the last class.
• Questions will be at the understanding level.
• 75% scores will be considered towards the grading

Coding/Analytical Assignments (Moodle)

• There will be 2 to 3 assignments mix of coding and analytical
• Expected to cover 10-12 lectures

Mini-Project

Students have to work on a mini project. Students can work in a team, however, max 2 members can be in a team. Project topics must be decided before Minor 2 and submission will be one week before the last date of class. Evaluation process will be decided later. This may include report, presentation or demonstration. Some project ideas are:

• Scenario Simulation with Comparative Study

• New Protocol Development

• Changing the assumptions of existing protocol and demonstrate the change in outcome

• There will be one special assignment for which one may need to read papers and implement the code.