CS443
Distributed Algorithms and Systems
2018 Fall

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 was originally motivated by Google 101 (UW CS 490h) but now has evolved to include fundamentals of distributed algorithms and systems. This semester we are including theories and pratices behind BitCoin as well.

Instructor
Sue Moon (sbmoon golbaengi kaist edu)
TAs
Wonsup Yoon
Jinhyun Kim
Email: cs443-ta golbaengi an kaist ac kr
Lecture Time
Mon/Wed 10:30 AM - 11:45 AM
Lecture Room
E3-1 Room #1101
[Mon, September 10th]
Homepage is up!


Lab 1
~ 2018/11/11 23:59 link
Lab 2
~ 2018/11/22 23:59 link
Lab 3
~ 2018/12/4 23:59 link
Lab 4
~ 2018/12/19 23:59
Challenges
~ 2018/12/19 23:59 same as Lab 4
Review 1
~ 2018/11/05 09:00
Review 2
~ 2018/11/19 09:00
Review 3
~ 2018/11/26 09:00
Review of Reviews
~ 2018/12/01 11:59
[1]
Distributed Algorithms by Nancy Lynch
[2]
Distributed Systems: Concepts and Design (5th Edition) by George Coulouris, Jean Dollimore, and Tim Kindberg
[3]
Distributed Systems: Principles and Paradigms (2nd Edition) by Andrew S. Tanenbaum and Maarten Van Steen
[4]
Principles of Computer System Design by Jerome H. Saltzer and M. Frans Kaashoek
[4]
Distributed Algorithms by Nancy Lynch
[5]
Bitcoin and Cryptocurrency Technologies by Arvind Narayanan, Joseph Bonneau, Edward Felten, Andrew Miller, Steven Gb 1
[6]
Bitcoin related articles:
1. Bitcoin: A Peer-to-Peer Electronic Cash System by Satoshi Nakamoto.
2. What is Bitcoin?i All About the Mysterious Digital Currency by Nathaniel Popper for the New York Times.
3. The Crypto-Currency by Joshua Davis for New Yorker.
4. Inside the Fight over Bitcoins' Future by Maria Bustillos for New Yorker.
5. What is Ethereum and How does it differ from Bitcoin? by Cara McGoogan for the Telegraph.
#1 is the original manifesto of Bitcoin by mysterious Satoshi Nakamoto. It reads like an IETF draft. #2 is an easier version of #1, written in plain English and explanations for usage and recent developments. #3 is an investigative report on the identity of the inventor. #4 and #5 are about Bitcoin users and new competing cryptocurrency.
[7]
"Be Selfish and Avoid Dilemmas: Fork After Withholding (FAW) Attacks on Bitcoini" (CCS 2017) Yujin Kwon, Dohyun Kim, Yunmok Son, Eugene Vasserman, and Yongdae Kim
[8]
"Algorand: Scaling Byzantine Agreements for Cryptocurrencies" (SOSP 2017) Yossi Gilad, Rotem Hemo, Silvio Micali, Georgios Vlachos, Nickolai Zeldovich
[9]
"Paralle data processing with MapReduce: A Survey" (SIGMOD Bulletin 2012) Kyong-Ha Lee, Yoon-Joon Lee, Hyunsik Choi, Yon Dohn Chung, Bongki Moon
[10]
"MapReduce: Simplified Data Processing on Large Cluster" Jeff Dean, Sanjay Ghemawat

Schedule

Week 1 8/27 Overview 8/29 Introduction to Distributed Algorithms (Read [1] 1, 2, 3.1)
Week 2 9/3 [1] 3.1 to 3.5 9/7 [1] 3.6 to 4.2
Week 3 9/10 [1] 4.3 to 4.5 9/14 [1] 5.1 and 6.1 to 6.3
Week 4 9/17 [1] 6.4 to 6.7 9/21 [1] 7.2 to 7.3
Week 5 9/24 Chuseok Holiday 9/28 Chuseok Holiday
Week 6 10/1 DA 10/3 No Class (National Foundation Day)
Week 7 10/8 No Class 10/10 No Class
Week 8 Mid-term Exam at 10am-12pm on Wednesday, Oct. 17
Week 9 10/22 No Class 10/24 DS #1
Week 10 10/29 DS #2 10/31 DS #3
Week 11 11/5 DS #4 (Make-up #1) 11/7 DS #5
Week 12 11/12 DS #6 11/14 DS #7
Week 13 11/19 DS #8 11/21 DS #9
Week 14 11/26 BC #1 (Make-up #2) 11/28 No Class (Undergrad Admission Exam)
Week 15 12/3 BC #2 (Make-up #3) 12/5 BC #3 (Guest Lecturer: Dr. Jong Gun Lee)
Week 16 Final Exam Week

Readling List

Paper 1 In Search of an Understandable Consensus Algorithm (Extended Version) USENIX ATC'14 Due: 2018/11/5 9:00
Paper 2 ZooKeeper: Wait-free Coordination for Internet-scale Systems USENIX ATC'10 Due: 2018/11/19 9:00
Paper 3 (Select One) Paxos Replicated State Machines as the Basis of a High-Performance Data Store USENIX NSDI'11 Due: 2018/11/26 9:00
Paper 4 (Select One) Paxos Made Live - An Engineering Perspective ACM PODC'07 Due: 2018/11/26 9:00