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
- Lectures: Monday, 12:00-14:00, class H208, and Wednesday, 12:00-14:00, class H208.
- Tutorial: Thursday, 14:00-16:00, class H208.
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
- Understanding the major tools and techniques that allow programmers to effectively program the parts of the code that require substantial communication and synchronization;
- Studying the core ideas behind modern coordination and communication paradigms and distributed data structures;
- Introduce a variety of methodologies and approaches for reasoning about concurrent and distributed programs;
- Realizing not only the basic principles but also the best practice engineering techniques of concurrent and distributed computing;
- Presenting techniques to formally study the safety and progress properties of concurrent and distributed algorithms;
- Analyzing the performance of current multi-core and future many-core systems.
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:
David Dice,
Virendra J. Marathe,
Nir Shavit:
Lock cohorting: a
general technique for designing NUMA locks.
PPOPP 2012:
247-256 2) Barriers |
5th | 1) 16/3: Presentation of paper:
Danny
Hendler,
Itai Incze,
Nir Shavit,
Moran Tzafrir:
Flat combining and the
synchronization-parallelism tradeoff.
SPAA 2010:
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:
Panagiota Fatourou,
Nikolaos D. Kallimanis:
Revisiting the combining synchronization technique.
PPOPP 2012:
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:
Darko Petrovic,
Omid Shahmirzadi,
Thomas Ropars,
André Schiper:
High-performance
RMA-based broadcast on the intel SCC.
SPAA 2012:
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, b) Yu and Meng, Principles of
Database Query Processing for Advanced Applications,
c) Relevant published papers |
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, b) Yu and Meng, Principles of
Database Query Processing for Advanced Applications,
c) Relevant published papers |
12th |
1) 18/5: Presentation of topic:
Optimization of Distributed Queries
a)
Ozsu and Valduriez, Principles of Distributed
Database Systems, Prentice Hall International,
b) Relevant published papers |
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
- H. Attiya & J. Welch, Distributed Computing: Fundamentals, Simulations and Advanced Topics, Morgan Kaufmann, 1998.
- G. Taubenfeld, Synchronization Algorithms and Concurrent Programming, Pearson / Prentice Hall, 2006.
- M. Herlihy and N. Shavit, The Art of Multiprocessor Programming, Morgan Kauffman, 2008.
- N. Lynch, Distributed Algorithms, Morgan Kaufmann, 1996.
Published papers on the following conferences:
- ACM Symposium on Principles of Distributed Computing (PODC)
- International Symposium on DIStributed Computing (DISC)
- ACM Symposium on Theory of Computing (STOC)
- ACM/IEEE Symposium on the Foundations of Theoretical Computer Science (FOCS)
- IEEE International Parallel & Distributed Processing Symposium (IPDPS)
Published papers on the following journals:
- Journal of the ACM
- SIAM Journal on Computing
- Distributed Computing
- Information and Computation
- IEEE Transactions on Parallel and Distributed Systems
- ACM Transactions on Programming Languages and Systems
- ACM Transactions on Computer Systems
- Journal of Parallel and Distributed Computing
How to review a paper in Theoretical Computer Science
- Ian Parbery, A Guide for new Referees in Theoretical Computer Science
- A manual for authors of mathematical papers by American Mathematical Society
- Indicative Review Form for Research Papers in Theoretical Computer Science