General Information

Information about the course

Course title: Distributed Computing
Cource code: CS586
Type of course: Elective
Level of course: Postgraduate
Course email address:

Information about the instructor

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

 

Class Information

 

Course Summary

We have entered 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, introducing as much parallelism as possible into software applications has become ever so urgent. 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 proliferation of multicore 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 design of efficient, fault-tolerant, concurrent distributed algorithms plays a vital role in simplifying the task of programming of a distributed system, but designing such algorithms is notoriously difficult, and therefore it is a task with which none but a few experts can cope.

This course focuses on the design and analysis of distributed algorithms for current multi-cores in which communication occurs via shared memory and future many-cores which are expected to feature several islands providing cache-coherence only between the cores of the same island but not across cores residing in different islands (so explicit communication via message-passing may be needed to achieve communication across islands). The course studies appropriate models of distributed computing to capture the subtleties of modern architectures, as well as major techniques for the design and analysis of distributed data structures and algorithms. The biggest part of the course is devoted to synchronization and communication mechanisms. The course aims at providing 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 current multi-core and future many-core systems.

This class is geared toward graduate students at all levels as well as advanced undergraduates.

 

Major objectives

 

Program

Week Subject
1st Introduction - Synchronization: Characteristics of concurrent algorithms, Difficulties encountered in achieving parallelism, The harsh realities of parallelization, Amdhal’s law, Modeling issues for shared memory and message-passing systems.
2nd 1) Mutual Exclusion: Mutual Exclusion using read/write registers, Algorithms for two processes, Tournament algorithms.
2) Mutual Exclusion
: The Bakery algorithm, The Black-White algorithm, A tight space lower bound, The one-bit mutual exclusion algorithm.
3rd Practice: Spin locks, contention: Test-and-Set Locks, Exponential Backoff, Queue Locks.
4th 1) 9/3: Presentation of paper: , , : Lock cohorting: a general technique for designing NUMA locks. PPOPP : 247-256
2) Barriers
5th 1) 16/3: Presentation of paper: D, , , : Flat combining and the synchronization-parallelism tradeoff. SPAA : 355-364
2) Concurrent objects - Correctness, progress and efficiency
: Concurrency and Correctness, Linearizability and sequential consistency, Progress conditions. Foundations of Shared Memory: Snapshot objects
6th 1) 23/3: Presentation of paper: , : Revisiting the combining synchronization technique. PPOPP : 257-266
2) The relative power of primitive synchronization operations: The consensus object, Consensus numbers, Wait-free implementations of arbitrary objects, Universality of consensus, A lock-free universal construction, A wait-free universal construction.
7th 1) 30/3: Presentation of paper:
2) Concurrent Queues
: A bounded partial queue, An unbounded total queue, An unbounded lock-free queue,
8th 1) 20/4: Presentation of paper: , , , : High-performance RMA-based broadcast on the intel SCC. SPAA : 121-130
2)  Concurrent Stacks & Elimination: An unbounded lock-free stack, The elimination BackOff stack.
9th 1) 27/4: Presentation of paper: 1) Mike Burrows, The Chubby lock service for loosely-coupled distributed systems, Proceedings of the 7th Symposium on Operating systems design and implementation (OSDI'06), pp. 335-350, 2006. & 2) Leslie Lamport, Paxos Made Simple
2)
Linked Lists
10th 1) 4/5: Presentation of topic: Query Processing, decomposition and data localization. Sources for Reading:

a)  Ozsu and Valduriez, Principles of Distributed Database Systems, Prentice Hall International,
              Inc., 2nd Edition, 1999 (Chapters 7 and 8)

b) Yu and Meng, Principles of Database Query Processing for Advanced Applications, 
            (Chapters 3 and 5)

c) Relevant published papers
2)
Linked Lists

11th 1) 11/5: Presentation of topic: Parallel Sorting, Parallel processing of selections and projections, Parallel processing of joins, etc.

a)  Ozsu and Valduriez, Principles of Distributed Database Systems, Prentice Hall International,
              Inc., 2nd Edition, 1999 (Chapter 9)

b) Yu and Meng, Principles of Database Query Processing for Advanced Applications, 
            (Chapter 5)

c) Relevant  published papers
2) 
Trees

12th 1) 18/5: Presentation of topic: Optimization of Distributed Queries

a)  Ozsu and Valduriez, Principles of Distributed Database Systems, Prentice Hall International,
              Inc., 2nd Edition, 1999 (Chapter 9)

b) Relevant published papers
2) Distributed Data Structures & Multidimensional Search Structures

 

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, a set of presentations will be asked by the students and a project will be handed out. For the presentations' section, the students will have to study two papers each week and be ready to present them in class and initiate a discussion on them.

The project involves studying the literature on a specific topic, selecting and reading a few (usually two or three) research papers on this topic, summarizing and critically reviewing the work in these papers, and suggesting some directions for future work relevant to the papers.  Each student will have to prepare a report for his/her project where s/he will address all the issues mentioned above, as well as s/he will have to give a one hour presentation in class to summarize the results of his project and the future research directions that could be followed. It is important, during or after the presentation, to initiate a discussion with the other students attending the class on the ideas a student has studied in his/her project. 

The final grade will be derived based on the attendance of the student in class and his/her participation to the discussions, the performance at the presentations' section and the performance of the student to the project, as follows:

Attendance & Participation to discussions: 15%
Presentations: 40%
Project: 45%

 

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

 

Prerequisities

Successful completion of CS380 (Algorithms and Complexity) is a prerequisite of this course.

 

Recommended Reading

Books

 

Published papers on the following conferences:

 

Published papers on the following journals:

 

How to review a paper in Theoretical Computer Science