CS586 - Distributed Computing

General Information

General

Teacher: Panagiota Fatourou
Office: 215 (White Building 1st floor)
Office hours: Wendesday: 11:00 - 13:00, Thursday: 15:00 - 17:00
Email address:
Telephone number: +30 2810 393549
TA: Eleftherios Kosmas
TA's office: Graduates' lab, White building sub level
TA's office hours: Tuesday, 19:00-20:00
Course email address:

Class Information

Tuesday, 17:00-19:00, class PA201. Thursday, 17:00-19:00, class PA201.

Course Summary

We have recently entered the era of multi-core architectures (in which several processors reside on each chip to achieve better performance), and we are now in the position to see multiprocessors sitting in every computer, from desktops to laptops and soon even to cellular phones. Thus, introducing as much parallelism as possible into software applications has become ever so urgent since this is the only way to take advantage of the new regime of multi-core machines. A major obstacle in this direction comes from the difficulty of developing concurrent data structures and algorithms. This difficulty is inherent in achieving synchronization between processes that run concurrently. Despite the hardness of concurrent programming, all modern distributed applications must rely on multithreading to enhance performance.

The proliferation of multicore architectures is obviously a serious motivation for studying concurrent programming but it is certainly not the only one. Distributed systems are nowadays widely used in all aspects of everyday life (by the organizations and the companies, the universities and the schools, the government, at home, etc.) Distributed algorithms arise in a wide spectrum of applications, including telecommunications, distributed information processing, scientific computing, real time process control, etc. Global information systems, telephone networks, banking applications, reservation systems, weather prediction, aircraft and nuclear power plant control, sensor networks, and many others, employ distributed computations and depend critically on the use of distributed algorithms, which should therefore be correct and efficient. Modern distributed applications should also exhibit high performance and be highly fault-tolerant. The design of efficient, fault-tolerant, concurrent distributed algorithms plays a vital role in simplifying the task of programming a distributed system. However, designing such algorithms is not an easy task.

This course focuses on the design and analysis of distributed algorithms. It studies fundamental models of distributed computing (to capture the needs of modern distributed applications), as well as major techniques for the design and analysis of distributed data structures and algorithms. Special emphasis is given on fundamental mechanisms for proving upper and lower bounds in distributed computing. A part of the course is devoted to synchronization mechanisms and several different techniques are studied for achieving it. Several distributed implementations have been presented in the literature in a very informal way and without any proof of their correctness. As a result, the behavior of many of these algorithms is simply unpredictable. This course aims at providing the required theoretical foundations, without which it is impossible to design correct distributed algorithms, check the correctness of current distributed implementations, capture all the details of their performance, discover their inherent limitations and establish optimality results, or determine whether any design tradeoffs are indeed fundamental or simply artifacts of certain environments. The main objective of the course is to supply the students with all the required dexterities for a rigorous and complete theoretical study of modern distributed systems.

The course can be attended by graduate students, as well as by undergraduates that are in a late stage of their studies. The requirements include homework assignments, paper reviews and a project chosen by the students with the guidance of the instructor (and the TA).

Program

Week Subject
1st Introduction - Synchronization
2nd Mutual Exclusion
3rd Practice: Spin locks, contention & other performance issues
4th Practice: Cache-friendly synchronization algorithms
5th Covering Arguments: A technique for proving lower bounds in distributed computing
6th Concurrent objects - Correctness, progress and efficiency
7th Foundations of Shared Memory: Wait-free Simulations of complex shared objects from simpler objects
8th Foundations of Shared Memory: Snapshot objects
9th The relative power of primitive synchronization operations
10th Common shared data structures (linked lists, queues, etc.)
11th Counting and Sorting
12th Adaptive algorithms - Measuring contention
13th Software transactional memory (STM)

Assignments and Marking

Throughout the semester, a set of theoretical assignments and two projects (a preliminary and a final project) will be handed out. Students will be given the chance to improve their theoretical assignments based on feedback provided by the instructor and the TA. Some of the assignments may ask the students to review one or more papers. A review consists of a two page report containing a summary of the main points of the paper, a discussion explaining why the results are new/interesting/significant and how they relate to the topic(s) discussed in class, and the student’s critique of the paper. Periodically, students will be asked to work in teams to accomplish short assignments given by the instructor in class.

Each project involves reading three research papers from the literature, summarizing and critically reviewing the work, and suggesting some directions for future work relevant to the papers. It also includes a short presentation of the main points of the papers. The preliminary project aims at providing the students with valuable feedback for the preparation of the final project. The preliminary project is obligatory but it is not graded. All comments of the instructor and the TA on the preliminary project should be seriously taken under consideration when preparing the final project.p

The final grade will be derived based on the student performance at the homework assignments, the paper reviews, the projects and the work in class.

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 are obliged to subscribe to the emailing list by the October 10, 2008. The address of the emailing list is:

All emails sent to this address will be forwarded to all members (students, instructor, TAs) of the list. It is a strong recommendation to the students to read email regularly (e.g., once a day).

The address of the electronic account of the course is the following:

Students may send any questions concerning the course to this address.

Prerequisities

CS380 (Algorithms and Complexity) is prerequisite course for this course. Students that have failed on the course mentioned above, do not to have the required background to attend this course.

Related Bibliography