User Tools

Site Tools

Buğra Gedik's Courses
@ Bilkent University

Trace: • cs442
cs442

Table of Contents

CS442 - Distributed Systems and Algorithms, Fall 2012

General

This course covers the fundamental concepts for the design and analysis of distributed systems and algorithms, including reasoning about distributed programs, handling the lack of global time and global state, achieving distributed consensus in the presence of faults and asynchrony, and designing fault-tolerance for distributed systems. The course also reviews state-of-the-art distributed systems (programming support, middleware, and more).

Text Books

  • Paolo Sivilotti, “Introduction to Distributed Systems”, 2005. here
  • Andrew S.Tanenbaum and Maarten Van Steen. “Distributed Systems: Principles and Paradigms (2nd Edition)”, Pearson, 2007.

Class Location and Times

  • Location: EB-201 (Engineering Building)
  • Times: Wed 1:40-3:30 and Fri 3:40-5:30

Grades

  • Quizzes (5%)
  • Homeworks (15%)
  • Project (25%) - Report (10%), Demo (15%)
  • Midterm (20%)
  • Final (35%)

Important Dates

  • Midterm: 7 Nov 2012, 01:40pm - 3:30pm, EB-201
  • Demo: 28 Dec 2013, 15:40pm - 17:30pm, EB222
    • Semih Şahin: 15:40pm-16:00pm
    • Yusuf Aytaş, Onur Özcan, Hakan Sözer: 16:00pm-16:20pm
    • Nail Akıncı, Naim Küçükdemirci, Bora Yalçıner - 16:20pm-16:40pm
    • Cansu Pınar Aslantaş: 16:40pm-17:00pm
    • Salih Kardan, Sefa Şahin Koç: 17:00pm-17:20pm
    • Engin Kayrakoğlu, Şerif Yeşil, Tolga Yılmaz: 17:20pm-17:40pm
    • Ömer Ali Acerol, Anıl Anar, Semih Yavuz: 17:40pm-18:00pm
    • Doğukan Çağatay: 18:00pm-18:20pm
    • Gizem Sarıkaya, Tuğcan Akyürek, İlter Ürgüp: 18:20pm-18:40pm
  • Final: 9 Jan 2013, 09:00am - 12:00pm, EB-201

Topics

  • Proving program properties (safety and progress)
  • Time (time synchronization (NTP), logical clocks (Lamport and vector))
  • State (distributed global snapshots)
  • Mutual exclusion (Token rings and trees, Lamport's alg, Dining philosophers)
  • Consensus (FLP, 2PC, Paxos algorithm)
  • Fault-tolerance (Byzantine agreement)
  • Programming support (RMI, MPI, DSM)
  • Distributed filesystems
  • Web-based systems
  • Cloud computing (map-reduce, key/value stores, BSP)
  • Peer-to-peer systems

Course TAs and Graders

  • Fahrettin Şükrü Torun (TA)
  • Tolga Dışpınar (Grader)

Syllabus

We will have 15 weeks of classes. Each week will have 2 lectures, where each lecture consists of 2x 50 minutes with a 10 minute break in between.

  • Week 1 (week of 17-21/09) - slides
    • Lecture 1: Introduction
    • Lecture 2: Predicate logic & program representation
    • Reading: Chapter 1 & 2 from Sivilotti
    • Homework 1, due Friday of Week 2
  • Week 2 (week of 24-28/09)
    • Lecture 1: Program correctness: Safety
    • Lecture 2: Program correctness: Progress
    • Reading: Chapter 3 from Sivilotti
    • quiz 1: you can bring it any time
    • Homework 2, due Friday of Week 3
  • Week 3 (week of 1-5/10)
    • Lecture 1: Program correctness proofs, Time: Clock sync. and Lamport clocks
    • Lecture 2: Vector clocks, State: distributed snapshots
    • Reading: Chapter 4, 5 from Sivilotti
    • Homework 3, due Friday of Week 4
  • Week 4 (week of 8-12/10)
    • Lecture 1: Mutual exclusion
    • Lecture 2: Token based mutual exclusion
    • quiz 2: You can bring it any time
    • Homework 4, due Friday of Week 5
  • Week 5 (week of 15-19/10)
    • Lecture 1: Dining philosophers
    • Lecture 2: Leader election
    • Homework 5, due Friday of Week 7
  • Week 6 (week of 22-26/10)
    • No lectures due to holiday
  • Week 7 (week of 29/10-2/11)
    • Lecture 1: Fault kinds, FLP, Consensus
    • Lecture 2: 2PC
    • quiz 3: you can bring it any time
    • Homework 6, due Friday of Week 8
  • Week 8 (week of 5/11-9/11)
    • Lecture 1: Midterm
    • Lecture 2: Midterm solutions
  • Week 9 (week of 12/11-16/11)
  • Week 10 (week of 19/11-23/11)
    • Lecture 1: OpenMP, including clustered OpenMP
    • Lecture 2: Tuple spaces
  • Week 11 (week of 26/11-30/11)
    • Lecture 1: No lectures
    • Lecture 2: Distributed file systems (book slides)
  • Week 12 (week of 3/12-7/12)
    • Lecture 1: Map/Reduce Systems, Hashing
    • Lecture 2: quiz 4: you can bring it any time
    • Homework 8, due Friday of Week 13
  • Week 13 (week of 10-14/12)
    • Lecture 1: Page rank computation, BSP-stype systems
    • Lecture 2: P2P systems
  • Week 14 (week of 17-21/12)
    • Lecture 1: Web-based distributed systems, caching, CDNs
    • Lecture 2: quiz 5: you can bring it any time
  • Week 15 (week of 24-28)
    • Lecture 1: No lecture
    • Lecture 2: Project demos
cs442.txt · Last modified: 2013/01/28 10:58 by bgedik

Page Tools