General Information

Information about the course

Course title: Principles of Distributed Computing
Cource code: CS486
Type of course: Elective
Level of course: Advanced Undergraduate (available for graduate students)
Course email address:

Information about the instructor

Name: Panagiota Fatourou, Assistant Professor
Office: K311
Office hours: Monday, 14:30 - 16:00
Telephone number: +30 2810 39 3549(CSD)
Email address:

Teaching Assistant

Name: Papagewrgiou Spyridon, MSc candidate
Email address:

 

Class Information

 

Course Summary

This course will focus on the study of basic distributed algorithms, including algorithms for multi-core shared memory systems, as well as message passing systems. The purpose of this course is to train students in the theoretical and practical aspects of design, analysis and implementation of algorithms in modern distributed systems. Students that complete the course successfully will have gained the basic background needed to work in any field touching upon distributed systems and applications.

We are well into the era of multi-core architectures and, as the applications' demands are still growing, we soon expect to see the first many-cores which will feature hundreds or even thousands of cores. Therefore, refactoring software in order to introduce parallelism is crucial, in order to take advantage of the massively parallel nature of current and future architectures. A major obstacle in this direction comes from the difficulty of developing distributed data structures and algorithms. This difficulty is inherent in achieving efficient synchronization and communication between processes that run concurrently. The first part of this course aims to alleviate this difficulty by introducing students to basic synchronization and communication mechanisms, as well as the design process of efficient distributed data structures and algorithms.

The proliferation of multi-core architectures is obviously a serious reason for studying concurrent and distributed programming but it is certainly not the only one. Distributed systems are nowadays widely used in all aspects of everyday life. Modern distributed applications should exhibit high performance and be highly fault-tolerant. The second part of this course aims to accustom students with the basic distributed algorithms and mechanisms, which are necessary in order to design correct software for distributed systems.

The two models on which this course focuses cover a wide range of distributed systems and effectively express the intricacies of modern (and probably future) architectures. On the basis of these two models, we will build a concrete collection of algorithms, which constitute the cornerstones of most distributed applications.

 

Major objectives

 

Course Contents

Subjects
                     PART I: Multiprocessor Algorithms

Topic 1: Introduction - Synchronization
  •   Difficulties encountered in achieving parallelism
  •   Amdhal's law
  •   Modeling a shared memory system
  •   Fundamental properties and parameters

    		•
    Topic 2: Mutual Exclusion & Locks
  •   Basic mutual exclusion algorithms
  •   Practice: Spin Locks and Contention
  •   Combining Techniques
  •   Hierarchical Approaches

    		•
    Topic 3: Atomic Objects:
  •   Linearizability
  •   Blocking and non-blocking progress conditions

    		•
    Topic 4: Concurrent Data Structures
  •   Concurrent Queues, Stacks, Lists
  •   Concurrent Hash Tables
  •   Concurrent Trees
  •   Garbage Collection, Safe memory reclamation

    		•
    Topic 5: Barriers
  •   Applications
  •   Barrier Implementations


    		•
                     PART II: Algorithms for Message-Passing Systems

    Topic 6: Introduction, Basic Network Algorithms
  •   Modeling a message-passing system
  •   Broadcast, convergecast and other collective communication algorithms
  •   Basic distributed graph algorithms

    • Topic 7: Leader Election
  •   Leader election in rings
  •   Leader election in general graphs

    		•
    Topic 8: Network Resource Allocation
  •   Mutual exclusion algorithms
  •   General resource allocation

    		•
    Topic 9: Logical Time and global states
  •   Adding logical time to distributed algorithms
  •   Consistent global snapshots

    		•
    Topic 10: Detection of properties on Distributed Executions
  •   Termination detection
  •   Deadlock detection
  •   Failure detection
    		•

     

    Language of instruction

    Language of instruction is ordinarily Greek; however, lectures are given in English when foreign students attend the course.

     

    Assignments and Marking

    Throughout the semester, two assignments dealing with the theoretical aspects of distributed computing and two programing projects have to be completed. The first project will deal with shared memory systems. The second project will deal with message passing systems. The two programming projects need to be implemented in C language using POSIX threads and the Message Passing Interface (MPI) respectively. The final grade will be calculated as follows:

    Assignments:40%
      Project:40%
      Final Exam: 20%

     

    Course Emailing-list & Electronic Account

    The course uses an emailing list for the efficient communication of the instructor and the TAs with the students. Subscription to the emailing list is performed by sending an email to the following address:

    with empty subject and the following line as the email body:

    Students should subscribe to the emailing list as soon as possible. The address of the emailing list is:

     

    Prerequisites

    Successful completion of CS-240 (Data structures) is a prerequisite for this course. Additionally, successful completion of CS-225 ( Computer Organization) and CS-345 (Operating Systems) is also recommended.

     

    Recommended Reading

    Main Textbooks

    Additional Books