UNIVERSITY OF ATHENS
DEPARTMENT OF INFORMATICS & TELECOMMUNICATIONS

M 120. Distributed Systems

 Spring 2024: Friday 10:00-14:00

in Room St

Name

E-mail

Office

Office Hours

Instructor: Mema Roussopoulou

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

A 38

Tuesday, 13:00-14:00


 

Announcements

1) Please sign up on the Piazza class forum here. We will use the class forum to make important announcements as the semester proceeds. The first announcement concerns details on how to attend the online class sessions. You are required to read the class forum regularly.

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

3) 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 and Undergraduate Computer Networking are required. The course on Advanced Operating Systems is also highly recommended. If you plan to take Advanced Operating Systems (M 131), you should take it before you take this class!

 


Readings

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, Idranil Gupta, 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.


Assignments

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 before each class by email. Send these as a single email to the Instructor with "Review for Day/Month" in the subject line, where Day/Month is the current lecture date. If using English, please send reviews in plain ASCII text.

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 earn 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 me 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.


Grading

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

Date

Topic

Readings

Presenter

8/3

Course Overview

Fundamentals

Network Review

Naming

Birman: Introduction (pages xix-xxvii)

Birman: Chapter 1

T&VS: Sections 5.1-5.4.2

Roussopoulou


Roussopoulou
Roussopoulou
Roussopfoulou

15/3

Clouds
CAP Theorem

T&VS: Chapter 6

Roussopoulou

22/3

Time
2PC and 3PC

Birman: Chapter 14

Roussopoulou
Roussopoulou

29/3

Consensus
FLP Consensus Impossibility Result (FLP)
Paxos

Sections 24.1-24.5

Impossibility of Distributed Consensus with one Faulty Process

Paxos Made Simple

Roussopoulou

5/4

DHTs
Bittorrent

A Scalable Content Addressable Network

Chord

Incentive Build Robustness in Bit Torrent


Roussopoulou
Roussopoulou
Roussopoulou

12/4

Byzantine Agreement, State Machine Replication

The Byzantine General's Problem

Practical Byzantine Fault Tolerance


Roussopoulou

19/4

Consensus

In Search of an Understandable Consensus Algorithm

Roussopoulou

26/4

Consistency

T&VS: Chapter 7


Project proposals due. Present to classmates.
Roussopoulou

3/5-10/5

-- No topic (Easter break)--

--

--

17/5

Sybil Attacks, Blockchains

Bitcoin: A Peer-to-Peer Electronic Cash System (Must present this and next paper together)

The Sybil Attack

Blockstack: A Global Naming and Storage System Secured by Blockchains


Markella
Vasilis

24/5

HotStuff, Spanner

HotStuff: BFT Consensus in the Lens of Blockchain

Spanner: Google’s Globally-Distributed Database

__
Giorgos

31/5

Chardonnay, DynamoDB

Chardonnay: Fast and General Datacenter Transactions for On-Disk Databases

Amazon DynamoDB: A Scalable, Predictably Performant, and Fully Managed NoSQL Database Service


Angelos
Alexandros

7/6

Antipode
Grove

Antipode: Enforcing Cross-Service Causal Consistency in Distributed Applications

Grove: a Separation-Logic Library for Verifying Distributed Systems


Interim reports due. Present project status to classmates.
Prokopis
Nikos

15/7

--

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.