CS492 Special Topics in Computer Science:
Distributed Algorithms and Systems


FALL 2009

Course Overview

The goal of this course is to provide students with theoretical basis of distributed system design and hands-on experience with distributed systems. The course is largely motivated by Google 101 (UW CS 490h) and lack of an undergraduate course on a similar topic in our department in recent years. The lecture material will be mostly from the two textbooks. Students will have additional reading material for projects.

Instructors

Sue Moon (sbmoon golbaengi kaist edu)

TAs

Changhyun Lee (chlee golbaengi an kaist ac kr) Hosung Park (hosung golbaengi an kaist ac kr)

Lectures

TuTh 9:00am - 10:20am (1st class on September 1st)

Office Hours

Tue 11:30am - 12:30pm Thu 12:30pm - 1:30pm , 5:30pm - 6:30pm

Prerequisites

CS330 Operating Systems CS330 Operating Systems CS441 Computer Networks (Those who have not taken CS330 or CS441 should consult the instructors.)

Topics to Cover

Trade-offs in System Design
Functional programming and MapReduce
Distributed algorithms

Lecture Notes

12/24 Final project report due
12/15-21 No class/exam during the final exam period
12/10 Thu Final Project Presentation (II)
12/8 Tue Final Project Presentation (I)
12/3 Thu Quiz #6 (Lec19)
12/1 Tue (Lec18)
11/26 Thu (Lec17)
11/24 Tue (Lec16)
11/19 Thu No class; project progress review mtg at Prof. Moon's office
11/17 Tue (Lec15); project progress review mtg at Prof. Moon's office
11/12 No class; (We'll have a class next Tue)
11/10 Tue (Lec14)
11/5 Thu Project Proposal Presentation
11/3 Tue No class; team project review mtg at Prof. Moon's office
10/29 Thu (Lec13)
10/27 Tue Introduction to distributed algorithms (Lec12)
10/20-26 No class/exam during the mid-term
10/15 Thu No Class
10/13 Tue 9:30am Quiz #5 on PageRank
10/9 Thu
PageRank (Lec11), Review of term project ideas (mailed out)
10/6 Tue
PageRank (Lec10)
10/1 Thu
Quiz #4 on NFS, NFS/GFS (Lec9)
9/29 Tue
Quiz #3 on Giant-Scale Services, Giant-Scale Services (Lec8)
9/24 Thu
GFS, HDFS, Hadoop (Lec7)
9/22 Tue
Quiz #2 on Giant-Scale Services, Dr. Jaesun Han on Cloud Computing (slides)
9/17 Thu
MapReduce (II) (Lec6)
9/15 Tue
MapReduce (Lec5)
9/10 Thu Quiz #1, Introduction to data parallelism and MapReduce (Lec4)
9/8 Tue Functional programming (Lec3), handout3.txt, handout4.txt
9/3 Thu Functional Programming (Lec2), handout1.ml, handout2.txt
9/1 Tue Introduction (Lec1)

Project

Term Project (final report due 2009/12/24)
Project #3 on PageRank (due midnight on Sun, 2009/11/1)
Project #2 on MapReduce (due midnight on Wed, 2009/10/7)
Project #1 (due midnight on Monday, 2009/9/21). See here for the Noah Board posting.

References

Please see the lecture notes.

Supplementary Reading

Principles of Computer System Design: An Introduction (by Jerome H. Saltzer and M. Frans Kaashoek) Distributed Systems: Concepts and Design (by Coulouris, Dollimore, Kindberg) Distributed Algorithms (by Nancy A. Lynch) Distributed Systems (by Andrew Tanenbaum, 2nd Edition)

Grading Policy

Attendance and participation: 10%
Quiz: 20%
Projects: #1 (10%), #2 (10%), #3 (20%), #4 (30%)