UNIVERSITY OF ATHENS
DEPARTMENT OF INFORMATICS & TELECOMMUNICATIONS

M 120. Distributed Systems

 Spring 2020: Wednesday 11:00-14:00 in Room E

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. 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, 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!

 


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


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

19/2

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
Roussopoulou

26/2

CAP + Clouds,

Time

T&VS: Chapter 6

Roussopoulou
Roussopoulou

4/3

2PC and 3PC
Bittorrent

Birman: Chapter 14

Incentive Build Robustness in Bit Torrent

Roussopoulou
Roussopoulou

11/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

18/3

Consistency

8) T&VS: Chapter 7


Roussopoulou

25/3

-- No topic (Greek Independence Day - holiday)--

--

--

1/4

DHTs
Key-value stores

A Scalable Content Addressable Network

Chord


Roussopoulou

8/4

Byzantine Agreement, State Machine Replication

MapReduce/Hadoop

The Byzantine General's Problem

Practical Byzantine Fault Tolerance


Team formation and (tentative) project choices due.

Marios


Giorgos K.

15/4-22/4

-- No topic (Easter break)--

--

--

29/4

Sybil Attacks, Blockchains

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

The Sybil Attack


Making Smart Contracts Smarter

Project proposals due. Present to classmates.
Elias

Sifis

6/5

Consensus
BFT Consensus & Blockchains

In Search of an Understandable Consensus Algorithm

HotStuff: BFT Consensus in the Lens of Blockchain

Nikos


Stefanos

13/5

CURP
Distributed Machine Learning

Exploiting Commutativity For Practical Fast Replication

TensorFlow: A System for Large-Scale Machine Learning

Ioannis Kalyvas
Panagiotis P.

20/5

Distributed Key-value Stores
Fine-grained RSMs

Millions of Tiny Databases

Fine-Grained Replicated State Machines for a Cluster Storage System


Interim report -- Present project status to classmates.
Andreas
Konstantinos A.

27/5

TBD

Near-Optimal Latency Versus Cost Tradeoffs in Geo-Distributed Storage

Flow-Join: Adaptive Skew Handling for Distributed Joins over High-Speed Networks

Scalog: Seamless Reconfiguration and Total Order in a Scalable Shared Log

XRD: Scalable Messaging System with Cryptographic Privacy

George P
George M
Christos P
TBD

2/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.