CS443
Distributed Algorithms and Systems
2017 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
- Keunhong Lee
Seokjoo Hong
Email: cs443-ta golbaengi an kaist ac kr
- Lecture Time
- Tue/Thu 9:00 AM - 10:15 AM
- Lecture Room
- N1 Room #112
- [Tue, October 31st]
- Report #3 out!
- Check out the homework section.
- [Tue, October 24th]
- No Class!
- Make-up class will be announced.
- [Tue, September 19th]
- Report #2 out!
- Check out the homework section.
- [Tue, September 19th]
- No Class!
- Make-up class will be at 8am on Thu, September 21st.
- [Tue, August 29th]
- Report #1 out!
- Read the first TWO chapters of Reference [4] for Thu, August 31st.
- Report #3
- Due 9am on Thursday, November 9th, 2017
- Submit a report on a use case of blockchain technology. Describe how it is different cryptocurrency. Discuss remaining challenges for your use case to become a reality. Again your report must be in PDF, and no longer than two pages no smaller font than 10pt. No cover page please.
- Report #2
- Due 9am on Saturday, September 30th, 2017
- Read [6] #1, [6] #2, and the first two chapters of [5], and write an essay on what BitCoin is and how it works. Your report must be in PDF, no longer than two pages no smaller font than 10pt.
- Report #1
- Due 9am on Thursday, AUgust 31st, 2017
- Read the following article and submit a page of review. Your report must be in PDF, no longer than a page in no smaller font than 10pt.
- How the NSA identified Satoshi Nakamoto
-
- [1]
-
Distributed Systems: Concepts and Design (5th Edition) by George Coulouris, Jean Dollimore, and Tim Kindberg
- [2]
- Distributed Systems: Principles and Paradigms (2nd Edition)
by Andrew S. Tanenbaum and Maarten Van Steen
- [3]
-
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 Goldfeder
- [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/29 Overview |
8/31 Introduction to Distributed Algorithms (Read [4] 1, 2, 3.1) |
|---|
| Week 2 | 9/5 [4] 3.1 to 3.4 | 9/7 [4] 3.5 to 3.7 |
|---|
| Week 3 | 9/12 [4] 4.1 to 4.3 | 9/14 [4] 4.4 and 4.5 |
|---|
| Week 4 | 9/19 [4] Chapter 5 | 9/21 [4] Chapter 5/6 |
|---|
| Week 5 | 9/26 [4] Chapter 6 | 9/28 Quiz starting at 8am |
|---|
| Week 6 | 10/3 Chuseok Holiday | 10/5 Chuseok Holiday |
|---|
| Week 7 | 10/10 [5] Chapter 1 | 10/12 |
|---|
| Week 8 | Mid-term Exam Week | |
|---|
| Week 8 | 10/24 no class | 10/26 [5] Chapter 2 |
|---|
| Week 10 | 10/31 Bitcoin technology wrap-up | 11/2 Intro on Cloud Computing |
|---|
| Week 11 | 11/7 [9] [10] | 11/9 Talks on [7] and [8] (to be confirmed) |
|---|
| Week 12 | 11/14 | 11/16 |
|---|
| Week 13 | 11/21 | 11/23 |
|---|
| Week 14 | 11/28 | 11/30 No Class (College Entrance Interview) |
|---|
| Week 15 | 12/5 | 12/7 Wrap-up |
|---|
| Week 16 | Final Exam Week [Report #5 Out] | |
|---|