M 123. Distributed Systems

 Spring 2017: Wednesday 9:00-13:00 in Room D.




Office Hours

Instructor: Mema Roussopoulou

mema -at* di *dot- uoa -dot* gr

A 38

Wednesdays, 13:00-14:00



1) Please sign up on the Piazza class forum here. We will use the class forum to make important announcements as the semester proceeds. You a re required to read the class forum regularly.

2) Please send via email three days on which you would like to present papers.  The sooner you send, the more likely you will get your first choice.

3) Information on how to write a review and a sample review are posted below.

4) Information on the final project required in this class is posted below.

Course Description

Essentially all modern computer systems distribute state and computation across network elements. This course aims to familiarize CS graduate students with the fundamental problems arising in the design, development, deployment and management of distributed software systems.

Topics covered in this course may include: interprocess communication and remote invocation, distributed naming, synchronization, time and event ordering, fundamental algorithms such as vector clocks, coordination and agreement, election, termination detection, distributed transaction mechanisms, replication of data and computation, web caching, fault tolerance, distributed shared memory, distributed object frameworks, distributed file systems, cryptographic security, case studies of real-world distributed systems.

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

Class attendance is required. You will be allowed to miss at most two classes throughout the semester.

Prerequisites: Undergraduate Operating Systems, Undergraduate Computer Networking, AND Advanced Operating Systems are required. Students who have not passed all three of these courses, particularly the Advanced Operating Systems course, have not faired well in this class in the past. If you plan to take Advanced Operating Systems (M 122), you should take it before you take this class!



Textbook: Reliable Distributed Systems, Kenneth Birman Publisher: Springer, Year: 2005.

Textbook: Distributed Systems: Principles and Paradigms, by Andrew S. Tanenbaum and Maarten Van Steen, Publisher: Prentice Hall, 2nd edition, Year: 2006.

Note: the lecture slides for this class are based on material in books and slides provided by Ken Birman, Andrew S. Tanenbaum, and Maarten Van Steen. Many thanks to these authors!

Readings will also include papers.  Links to papers are included in the class schedule below.


This course will involve listening to lectures, reading papers, writing reviews for papers, participating in class discussions, presenting papers and leading class discussions, and a final project.

Students will be required to write reviews for papers they read. Look here to get information on how to write a review. Reviews are due in class and are to be handed in via hardcopy to the instructor. Each review must be labeled with the Day/Month where the Day/Month is the current lecture date. A sample review for a small workshop paper can be found here

Students will actively participate in class discussions on textbook chapters and papers we read. For each paper, we will study the contribution of the paper, place this contribution in context of previous literature, critique the methodology used and the evaluation presented. Be prepared to come to class having read each paper carefully and ready to discuss questions or comments you have in detail. Class participation is a portion of the overall grade, and an easy way for you to gain points in the class.

In addition, students will present papers on one or more days and lead the discussion in the class. The instructor will help you lead the discussion.

Note: You must have access to a printer so you may download, print copies of the papers (available below), and bring them to class for the discussions. I recommend you scribble directly on a paper any notes or questions that arise as you are reading. In fact, taking detailed notes on the paper and then reading through them before writing your review and before coming to class is a good idea. You are also welcome to send any questions about the paper to the staff before class if you feel shy asking about a particular detail in the paper. There are no dumb questions!!

Finally, students will be required to undertake a final project. Students are to work in groups of two or three (two preferred) and are expected to design, document, and demonstrate a substantial distributed system. The system is to be developed in a modular way. Students will choose a project topic from a list of projects we provide or may propose their own topic. At the end of the course, students will present their work with a short demo/presentation. More info on the final project can be found here.


Reviews: 10% (These will be graded out of a total of 12 and must be submitted ON TIME . Late reviews will not be accepted.)

Class Participation: 10%
Paper presentations: 20%
Final Project: 60%

Syllabus & Schedule (slides and schedule will be updated as needed)
^M ^M ^M ^M ^M






Course Overview


1) Birman: Introduction (pages xix-xxvii)




Basic Communication



2) Birman: Chapter 1

3) T&VS: Sections 5.1-5.4.2



CAP + Clouds,


4) Birman: Section 5.1-5.2 and Chapter 4
4b) T&VS: Chapter 6



2PC and 3PC,

Content Distribution Networks

5) Birman: Chapter 5

6) Birman: Sections 24.1-24.5

7) Birman: Section 14.5




A Scalable Content Addressable Network


Liza S.
Theodore M.



8) T&VS: Chapter 7

Team formation and project choices due.


Event ordering


Kronos: the design and implementation of an event ordering service

Vuzuvela Scalable Private Messaging Resistant to Traffic Analysis

Project proposals due.
Vasiliki M.
Marios L.


-- No topic (Easter break)--




Distributed Transactions

No compromises: distributed transactions with consistency, availability, and performance

Building Consistent Transactions with Inconsistent Replication

Dimitris S.
Konstantinos G.


Secure P2P Digital Preservation
Incremental Consistency

Preserving Peer Replicas by Rate-Limited Sampled Voting

Incremental Consistency Guarantees for Replicated Objects

Rizart D.
Thanos G.


Byzantine Fault Tolerance, Consensus

Practical Byzantine Fault Tolerance

In Search of an Understandable Consensus Algorithm

Interim reports due.

Lydia Z.
Dimitris M.


MapReduce, State Machine Replication

MapReduce:  Simplified Data Processing on Large Clusters

Paxos Made Transparent

Theodoros P.
Themis B.


Distributed Graph Processing

Existential Consistency: Measuring and Understanding Consistency at Facebook

Arabesque: A System for Distributed Graph Mining

Ioannis T.
Iosif A.


Facebook Consistency, Google Auto-Sharding

Starfish: A Self-tuning System for Big Data Analytics

Slicer: Auto-Sharding for Datacenter Applications

Dimitris Z.
Xristos K.



Final projects, write-ups, and demos/presentations due.


Class Paper Bibliography

The papers read in this class are from top-tier systems and networking conferences:  USENIX Symposium on Networked Systems Design and Implementation (NSDI), USENIX Symposium on Operating Systems Design and Implementation (OSDI), ACM SIGCOMM, ACM Symposium on Operating Systems Principles (SOSP), and ACM EuroSys. The links above include bibliographic information such as author names, venue, and year.