Download a PDF Version of the syllabus.

Overview

Title: Distributed Systems

Units: 12

Pre-requisites: A grade of "C" or better in 15-213, Introduction to Computer Systems

Lectures: Monday and Wednesday, 8:30 - 9:50 AM, Room 2049

Recitation: Thursday, Time: 4:00 - 4:50PM, Room: 1185

Webpage: http://www.qatar.cmu.edu/~msakr/15440-f11/

Description

15-440 is an introductory course in distributed systems. The emphasis will be on the techniques for creating functional, usable, and high-performance distributed systems. To make the issues more concrete, the class includes several multi-week projects requiring significant design and implementation.

The goals of this course are twofold: First, for students to gain an understanding of the principles and techniques behind the design of distributed systems, such as locking, concurrency, scheduling, and communication across networks. Second, for students to gain practical experience designing, implementing, and debugging real distributed systems.

The major themes this course will teach include process distribution and communication, data distribution, scheduling, concurrency, resource sharing, synchronization, naming, abstraction and modularity, failure handling, protection from accidental and malicious harm, and the use of instrumentation, monitoring and debugging tools in problem solving. As the creation and management of software systems is a fundamental goal of any undergraduate systems course, students will design, implement, and debug large programming projects. Students will learn the design and implementation of today's popular distributed system paradigms, such as Google File System, MapReduce and system virtualization.

Instructors

Prof. Majd F. Sakr
msakr@qatar.cmu.edu, CMUQ 2121, 4454-8625.
Office hours: Tue, 3-4pm

Dr. Mohammad Hammoud,
mhhammou@qatar.cmu.edu, CMUQ 1013, 4454-8506.
Office hours: Thu, 11am-12pm

Dr. Vinay Kolar,
vkolar@qatar.cmu.edu, CMUQ 1013, 4454-8683.
Office hours: Sun, 1:30-2:30pm

Objectives

Distributed Systems combine the computational power of multiple computers to solve complex problems. The individual computers in a distributed system are typically spread over wide geographies, and possess heterogeneous processor and operating system architectures. Hence, an important challenge in distributed systems is to design system models, algorithms and protocols that allow computers to communicate and coordinate their actions to solve a problem.

Our aim in this course is to introduce you to the area of distributed systems. You will examine and analyze how a set of connected computers can form a functional, usable and high-performance distributed system.

The course has three goals:

Through these objectives, the course will transform your computational thinking from designing applications for a single computer system, towards that of distributed systems.

Learning Outcomes:

Checkout a complete tree of learning outcomes for this course

The primary learning outcome of the course is two-fold:

Understanding the core concepts of distributed systems

You will learn the core concepts underlying distributed system design. You will understand the system constraints, trade-offs and techniques in distributed systems to best serve the computing needs for different types of data and applications. You will learn the following concepts:

Access and location transparency

Hiding the details of machines and exposing the capabilities is one of the first steps to design distributed systems that scale and penetrate economies and masses to utilize their power. For example, in the Internet, which is a successful distributed system, a simple browser interface will allow you to explore information scattered over wide-geographies. In this course, you will examine how to abstract locations and processes that may reside in different physical places.

You will learn the following topics:

Parallelization of tasks

Traditional algorithms that work on a single processor are inefficient -- or even fail to work -- in a system where multiple machines are working in parallel. In distributed systems, jobs can be solved using parallelization. Generally a job is split into multiple tasks, and each task is executed concurrently with other tasks on a different machine. The tasks may access common resources, such as the data contained in a single file. As such, two main challenges emerge. The first challenge is to ensure that concurrently running tasks coordinate and synchronize to achieve a common goal. The second challenge is to replicate and place resources among multiple computers such that concurrently running tasks can access resources efficiently.

You will study the following topics:

Fault-tolerance

In a distributed system with many computers, a failure of a single or a part of the computer is very likely. If such a system failure is not avoided or recovered from, the whole system might halt, resulting in a fragile and unpredictable system. You will identify the issues dealing with avoiding and recovering from failure, which is termed as fault-tolerance, in a distributed system.

Security

In distributed systems, computers that solve your problem may not be under your administrative control; you do not own -- sometimes, even know -- where your program is running on a big connected set of computers. This makes a distributed system vulnerable to security and privacy related issues. You will learn the common security issues in distributed systems and mechanisms to secure the system.

Practical application of the state-of-the-art distributed systems:

You will also learn how to apply principles of distributed systems in a real-world setting. Specifically, you will learn the following topics:

Textbooks

The primary textbooks for this course are:

In addition, we recommend the following text books:

We have several reference books in the library covering most of the topics of the course. We will also be reading tutorials, journals and conference publications on the subject.

Course Organization

Your participation in the course will involve six forms of activity:

Attendance will be taken at the beginning of each lectures, it will be worth 5% of your grade. Before each class, you are required to briefly read about the topics that will be covered. There will be a small (5 minute) pre-class quiz to assess pre-class preparation. You will be responsible for all material presented during the lectures.

Getting Help

For urgent communication with the teaching staff, it is best to send an email (preferred) or phone. If you want to talk to a staff member in person, remember that our posted office hours are merely nominal times when we guarantee that we will be in our offices. You are always welcome to visit us outside of our office hours if you need help or want to talk about the course.

We ask that you follow a few simple guidelines. Prof. Sakr, Dr. Hammoud and Dr. Kolar normally work with their office door open and welcome visits from students whenever the doors are open. However, if their door is closed, then they are busy with a meeting or a phone call and should not be disturbed.

We will use the course web-page as the central repository for all information about the class. Using the web-page, you can:

  1. Obtain copies of any handouts or assignments. This is especially useful if you miss class or you lose your copy.
  2. Find links to any electronic data you need for your assignments
  3. Read clarifications and changes made to any assignments, schedules, or policies.
  4. Provide healthy feedback about the course

You can use the mailing list (15440-f11@lists.qatar.cmu.edu) to post messages, make queries about the course, specific projects, or exams. The messages on this mailing list will be distributed to all the students and staff of the course.

The course also has a "Course Social Interaction Group". This is a Google+ group which you can access to post comments, suggestions, queries and other interesting material regarding the course. Instructors will also be a part of this group. They will help in answering your queries and maintain a healthy and inspiring social interaction.

Policies

Working Alone on Assignments/Projects

Assignments/projects that are assigned to single students should be performed individually. Some projects may be group projects, in which case it will be notified earlier.

Working on Group Assignments/Projects

Some assignments/projects are collectively performed by a group of students. A student can be in only one group. The maximum and minimum number of students in a group will be announced earlier. On such assignments/projects, you can collaborate only among your team members.

Handing in Assignments/ Projects

All assignments/projects are due at 11:59 PM (one minute before midnight) on the specified due date. All hand-ins are electronic using the AFS file system: /afs/qatar.cmu.edu/usr16/msakr/www/15440-f11/handin/userid/, userid is your andrew user id.

Making up Exams, Assignments and Projects

Missed exams, assignments and projects can be made up on a case by case basis, but only if you make prior arrangements with Prof. Sakr. However, you should have a good reason for doing so. You need a written consent from Prof. Sakr for making up exams, assignments or projects. It is your responsibility to get your projects done on time. Be sure to work far enough in advance to avoid unexpected problems, such as illness, unreliable or overloaded computer systems, etc.

Appealing Grades

After each assignment, exam and project is graded, you have seven calendar days to appeal your grade. All your appeals should be provided in writing. If you are still not satisfied, please come and visit Prof. Sakr. If you have questions about an exam grade, please visit Prof. Sakr directly.

Assessment

Final Grade Assignment and Assessment methods

Each student will receive a numeric score for the course, based on a weighted average of the following:

  1. Projects:

    The projects will count a combined total of 50% of your score. There are 4 projects throughout the course. The first three projects are worth 10% each. The fourth project is worth 20%, and it will involve a presentation and a paper as well as the project code. Take into account that small differences in scores can make the difference between two letter grades.

    You are encouraged to submit the projects on time. For all projects except final project, the following rules apply. If you submit one day late, there will be deducted 25% of the project score as penalty. If you are two days late, 50% will be deducted. The project will not be graded (and you will receive a zero score) if you are more than two days late. However, there is a grace-days quota for projects; you are given 3 grace days for all projects (except the final project). You can use the grace days as needed. For example, you can submit your project 1, three days late and still not get any penalty. Your penalty starts from 4th day after the deadline if you use your grace days. However, since you have used up all your grace days from your quota, you do not have any grace days for other projects. Plan how to utilize your grace day quota judiciously. For the team project (project 3), we deduct one grace day from each student if the team submits the project one day late. Hence, make sure that everyone in your team has 'x' grace days left if you want to submit the project 'x' days late.

    Note, the final project is unique. You cannot use grace days for final project. There will not be any penalty system for this project either. If you are one day late in submitting final project, your project will not be graded (and you will receive a zero score).

  2. Exam:

    There will be two in-class exams -- mid-term and final -- that count for 25% of the grade. Mid-term will count for 10%, and final for 15% of the overall grade.

  3. Problem Solving Assignments:

    There will be four mandatory and five recommended, extra-credit, written assignments that will test students on problem analysis and solving skills. The mandatory assignments will carry an overall score of 10% of your total score. The recommended assignments help you to critically think about topics which will be covered in programming projects, and will help you towards tackling problems that might appear in the exam. In addition to testing your technical writing skills, these assignments will also test you on competencies in critical understanding and reasoning in distributed systems.

  4. Pop-quizzes:

    There will be 5 pop-quizzes in the class or recitation, which will account for 10% of your grade. Pop-quizzes are surprise quizzes that test your understanding in the topics covered. Be prepared for being tested on topics that have been covered earlier.

  5. Pre-class quizzes:

    You are required to briefly read about the topics that will be covered in each class. The schedule and topics covered will be posted on the web-page. At the beginning of every class, you will have a brief 5 minute pre-class quiz. These quizzes will account for 5% of your final grade

  6. Class-Recitation participation and attendance:

    Your attendance and participation in the different discussions held in class and recitations will account towards 5% of your final grade.

Type # Weight
Projects 4 50%
Exams 2 25%
Problem Solving Assignments 4 10%
Pop-Quizzes 5 5%
Pre-Class Quizzes 26 5%
Class/recitation participation and attendance 44 5%

Grades for the course will be determined by absolute standards. The total score will be plotted as a histogram. Cutoff points are determined by examining the quality of work by students on the borderlines. Individual cases, especially those near the cutoff points may be adjusted upward or downward based on factors such as attendance, class participation, improvement observed throughout the course, exam performance, and special circumstances.

Cheating

Each project must be the sole work of the student turning it in, except for possible group projects. Projects will be closely monitored by automatic cheat checkers, and students may be asked to explain any suspicious similarities with any piece of code available. The following are guidelines on what collaboration is authorized and what is not:

What is cheating?

  1. Sharing code or other electronic files: either by copying, retyping, looking at, or supplying a copy of a file.
  2. Sharing written assignments: Looking at, copying, or supplying an assignment.

What is NOT cheating?

  1. Clarifying ambiguities or vague points in class handouts.
  2. Helping others use the computer systems, networks, compilers, debuggers, profilers, or other system facilities.
  3. Helping others with high-level design issues.
  4. Helping others debug their code.

Cheating in group projects will also be strictly monitored and penalized (similar to cheating in individual exams, assignments or projects). Be aware of what constitutes cheating (and what does not) while interacting with students in other groups; same rules of cheating as above apply when collaborating between two or more groups. You cannot share or use written assignments, code, and other electronic files from students in other groups. If you are unsure, ask the teaching staff.

Be sure to store your work in protected directories. The penalty for cheating is severe, and might jeopardize your career; cheating is not worth the trouble. By cheating in the course, you are cheating yourself; the worst outcome of cheating is missing an opportunity to learn. In addition, you will be removed from the course with a failing grade. We also place a record of the incident in the student's permanent record.

Class Schedule

Please refer to Schedule page for the tentative schedule for the class. The schedule also indicates the project activities. Any changes will be announced on the class distribution list (15440-f11@lists.qatar.cmu.edu). An updated schedule will be maintained on the class Web page.