CSL7920: Distributed Algorithms (Autumn 2023)

Table of Contents

Logistics

  • Credits L-T-P [C]: 3-0-0 [3]
  • Expectation from 7000 level course:
    • 1 Contact Hr + 3 Non-Contact Hr
    • Learn by Experiment/Research/Project
  • Where: Room 102 CSE
  • Slot: G (Tuesday 3:00PM - 3:50PM, Wednesday and Friday 2:00PM - 2:50PM)
  • LMS: Moodle
    • Credential: Internet ID/Password
    • Easy Enrollment Code: d6m5vj

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.

If attendance falls below 75%, one should get at least C grade to pass the course. Otherwise F grade will be assigned.

Grading Policy

Research Paper Demonstration/ Presentation Class Quizzes (Slido) Mini-Project
15% 10% 10%
Coding/Analytical Assignments Minors Major
20% 10% + 10% 25%

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.

Plagiarism tolerance is 7% from single source and 15% cumulative, anything more will reduce your marks as follows:

  • Any logical/conceptual/formulation plagiarism: zero marks
  • Other form of plagiarism (above 50%): zero marks
  • Otherwise: Percentage of plagiarism will be deducted from the obtained mark