CS 598XU: Schedule and Readings

Spring 2022

Week 1

Week 2

Week 3

Week 4

Week 5

Week 6

Week 7

Week 8

Week 9

Week 10

Week 11

Week 12

Week 13

Week 14

Week 15

1/18
1/20

1/25
1/27

2/1
2/3

2/8
2/10

2/15
2/17

2/22
2/24

3/1
3/3

3/8
3/10

3/22
3/24

3/29
3/31

4/5
4/7

4/12
4/14

4/19
4/21

4/26
4/28

5/3

This page conforms to the FERPA policy of disclosure of education records. All the students listed as (co-)presenters provide the written consents.

Note: The reading list will be adjusted on the fly! We show a tentative list to give you some ideas about what kinds of papers will be discussed in the course.

Course Introduction

Tue
1/18

Course Overview

Cloud and Datacenter Systems

Thu
1/20

L. A. Barroso et al., The Datacenter as a Computer: An Introduction to the Design of Warehouse-Scale Machines (2nd Edition), Morgan & Claypool, July 2013.
Read: Chapter 1 (Introduction) and Chapter 7 (Dealing with Failures and Repairs).
B. Maurer, Fail at Scale, Communications of the ACM (CACM), Vol. 58 No. 11, Pages 44-49, November 2015.
(Optional) related papers mentioned in Dean's talk:
- S. Ghemawat, et al., The Google file system, In Proceedings of the 19th ACM Symposium on Operating Systems Principles (SOSP '03), October 2003.
- F. Chang et al., Bigtable: A Distributed Storage System for Structured Data, In Proceedings of the 7th USENIX Symposium on Operating Systems Design and Implementation (OSDI '06), December 2006.
- J. Dean and S. Ghemawat, MapReduce: simplified data processing on large clusters, In Proceedings of the 6th USENIX Symposium on Operating Systems Design and Implementation (OSDI '04), December 2004.
- J. C. Corbett et al., Spanner: Google’s Globally-Distributed Database, In Proceedings of the 10th USENIX Symposium on Operating Systems Design and Implementation (OSDI '12), October 2012.

Availability

Tue
1/25

B. Treynor et al., The Calculus of Service Availability, Communications of the ACM (CACM), Vol. 60 No. 9, Pages 42-47, September 2017.
H. S. Gunawi et al., Why Does the Cloud Stop Computing? Lessons from Hundreds of Service Outages, In Proceedings of the 6th ACM Symposium on Cloud Computing (SOCC '16), October 2016.
J. C. Mogul et al., Thinking about Availability in Large Service Infrastructures, In Proceedings of the 16th Workshop on Hot Topics in Operating Systems (HotOS-XVI), May 2017.
(Optional) related failure studies:
- J. C. Mogul and J, Wilkes, Nines are Not Enough: Meaningful Metrics for Clouds, In Proceedings of the 17th Workshop on Hot Topics in Operating Systems (HotOS-XVII), May 2019.
- T. Hauer et al., Meaningful Availability, In Proceedings of the 17th USENIX Symposium on Networked Systems Design and Implementation (NSDI '20), Feb. 2020.
- D. Oppenheimer et al., Why do Internet services fail, and what can be done about it?, In Proceedings of the 4th USENIX Symposium on Internet Technologies and Systems (USITS '03), March 2003.
- J. Gray, Why Do Computers Stop and What Can Be Done About It?, Technical Report 85.7, Tandem Computers, June 1985.

Flaky Hardware

Thu
1/27

T. Do et al., Limplock: Understanding the Impact of Limpware on Scale-Out Cloud Systems, In Proceedings of the 5th ACM Symposium on Cloud Computing (SoCC '13), October, 2013.
P. H. Hochschild et al., Cores that don’t count, In Proceedings of the 18th Workshop on Hot Topics in Operating Systems (HotOS-XVIII), May 2021.
(Optional) related papers on fail-slow fault tolerance:
- R. H. Arpaci-Dusseau and A. C. Arpaci-Dusseau, Fail-Stutter Fault Tolerance, In Proceedings of the 8th Workshop on Hot Topics in Operating Systems (HotOS-VIII), May 2001.
- A. B. Yoo et al., Fail-slow fault tolerance needs programming support, In Proceedings of the 18th Workshop on Hot Topics in Operating Systems (HotOS-XVIII), May 2021.
- H. S. Gunawi et al., Fail-Slow at Scale: Evidence of Hardware Performance Faults in Large Production Systems, In Proceedings of the 16th USENIX Conference on File and Storage Technologies (FAST '18), February 2018.
(Optional) related papers on flaky cores:
- H. D. Dixit et al., Silent Data Corruptions at Scale, arXiv:2102.11245, Feb. 2021.

Birds of a Feather

Tue
2/1

Please read the Raft paper (you will need to understand Raft for Assignment #2).
D. Ongaro and J. Ousterhout, In Search of an Understandable Consensus Algorithm, In Proceedings of the 2014 USENIX Annual Technical Conference (USENIX ATC '14), June 2014.

Buggy Code

Thu
2/3

D. Yuan et al., Simple Testing Can Prevent Most Critical Failures: An Analysis of Production Failures in Distributed Data-Intensive Systems, In Proceedings of the 11th USENIX Symposium on Operating Systems Design and Implementation (OSDI '14), October 2014.
H. S. Gunawi et al., What Bugs Live in the Cloud? A Study of 3000+ Issues in Cloud Systems, In Proceedings of the 5th ACM Symposium on Cloud Computing (SOCC '14), November 2014.
(Optional) related bug studies:
- L. Lu et al., A Study of Linux File System Evolution, In Proceedings of the 11th USENIX Conference on File and Storage Technologies (FAST '13), February 2013.
- G. Jin et al., Understanding and Detecting Real-World Performance Bugs, In Proceedings of the 33rd ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI '12), June 2012.
- S. Lu et al., Learning from Mistakes — A Comprehensive Study on Real World Concurrency Bug Characteristics, In Proceedings of the 13th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS '08), March 2008.
- A. Chou et al., An Empirical Study of Operating Systems Errors, In Proceedings of the 18th ACM Symposium on Operating Systems Principles (SOSP '01), October 2001.

Discussion Section on Assignment #1

Tue
2/8

We will go over Assignment #1 and do QA.

Bad Configs

Thu
2/10

C. Tang et al., Holistic Configuration Management at Facebook, In Proceedings of the 25th Symposium on Operating Systems Principles (SOSP '15), October 2015.
X. Sun et al., Testing Configuration Changes in Context to Prevent Production Failures, In Proceedings of the 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI'20), Nov. 2020.
(Optional) related papers:
- T. Xu, et al., Do Not Blame Users for Misconfigurations, In Proceedings of the 24th ACM Symposium on Operating Systems Principles (SOSP '13), November, 2013.
- T. Xu et al., Early Detection of Configuration Errors to Reduce Failure Damage, In Proceedings of the 12th USENIX Symposium on Operating Systems Design and Implementation (OSDI '16), November 2016.
- R. Cheng et al., Test-Case Prioritization for Configuration Testing, In Proceedings of the 30th ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA'21), July 2021.

Partitioned Networks

Tue
2/15

A. Alquraan et al., An Analysis of Network-Partitioning Failures in Cloud Systems, In Proceedings of the 13th USENIX Symposium on Operating Systems Design and Implementation (OSDI '18), October 2018.
P. Bailis and K. Kingsbury, The Network Is Reliable, Communications of the ACM (CACM), Vol. 57 No. 9, Pages 48-55, September 2014.
(Optional) related papers:
- M. Alfatafta et al., Toward a Generic Fault Tolerance Technique for Partial Network Partitioning, In Proceedings of the 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI '20), Nov. 2020.
- E. Brewer, CAP Twelve Years Later: How the "Rules" Have Changed, IEEE Computer, 45(2):23-29, February 2012.
- E. Brewer, Spanner, TrueTime & The CAP Theorem, Technical report, Google Inc., 2017.

To Err is Human

Thu
2/17

A. B. Brown and D. A. Patterson, Undo for Operators: Building an Undoable E-mail Store, In Proceedings of the 2003 USENIX Annual Technical Conference (USENIX ATC '03), June 2003.
K. Nagaraja et al., Understanding and Dealing with Operator Mistakes in Internet Services, In Proceedings of the 6th Symposium on Operating Systems Design and Implementation (OSDI '04), December 2004.
Read the postmortem: Summary of the Amazon S3 Service Disruption in the Northern Virginia (US-EAST-1) Region, February 2017. (discussions on Hacker News)
(Optional) related papers:
- R. Bianchini et al., Human-Aware Computer System Design, In Proceedings of the 10th Workshop on Hot Topics in Operating Systems (HotOS-X), Jun. 2005.
- D. A. Patterson et al., Recovery Oriented Computing (ROC): Motivation, Definition, Techniques, and Case Studies, Tech Report UCB//CSD-02-1175, University of California Berkeley, March 2002. (the ROC project website)

Project Proposal Review

Tue
2/22

We will go over Assignment #1 and do QA.

(Too Much) Load

Thu
2/24

A. F. Cuervo, Handling Overload, Site Reliability Engineering: How Google Runs Production Systems, O'Reilly, April 2016.
M. Ulrich, Addressing Cascading Failures, Site Reliability Engineering: How Google Runs Production Systems, O'Reilly, April 2016.
H. Zhou et al., Overload Control for Scaling WeChat Microservices, In Proceedings of the 2018 ACM Symposium on Cloud Computing (SOCC '18), Oct., 2018.
(Optional) related papers:
- L. Fang et al., Interruptible Tasks: Treating Memory Pressure As Interrupts for Highly Scalable Data-Parallel Programs, In Proceedings of the 25th ACM Symposium on Operating Systems Principles (SOSP '15), October 2015.

Scale

Tue
3/1

C. A. Stuardo et al., ScaleCheck: A Single-Machine Approach for Discovering Scalability Bugs in Large Distributed Systems, In Proceedings of the 17th USENIX Conference on File and Storage Technologies (FAST '19), Feb. 2019.
F. McSherry et al., Scalability! But at what COST?, In Proceedings of the 15th Workshop on Hot Topics in Operating Systems (HotOS-XV), May 2015.

"High Performance" Computers

Thu
3/3

I. Laguna et al., Debugging High-Performance Computing Applications at Massive Scales, Communications of the ACM, September 2015, Vol. 58 No. 9, Pages 72-81.
C. D. Martino et al., Lessons Learned from the Analysis of System Failures at Petascale: The Case of Blue Waters, In Proceedings of the 44th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN '14), June 2014.
(Optional) related paper:
- S. Jha et al., Live Forensics for HPC Systems: A Case Study on Distributed Storage Systems, In Proceedings of the 2020 International Conference for High-Performance Computing, Networking, Storage and Analysis (SC '20), Nov. 2020.

Discussion Section for Assignment #2

Tue
3/8

Go over Assignment #2 and do QA.

Integration and Deployment

Tue
3/22

Y. Zhang et al., Understanding and Detecting Software Upgrade Failures in Distributed Systems, In Proceedings of the ACM SIGOPS 28th Symposium on Operating Systems Principles (SOSP '21), October 2021.
T. Savor et al., Continuous Deployment at Facebook and OANDA, In Proceedings of the IEEE/ACM 38th International Conference on Software Engineering (ICSE '16), May 2016.
(Optional) related papers:
- C. Rossi et al., Continuous Deployment of Mobile Software at Facebook, In Proceedings of the ACM SIGSOFT International Symposium on the Foundations of Software Engineering (FSE '16), November 2016.
- J. Hamilton, On Designing and Deploying Internet-Scale Services, In Proceedings of the 21st USENIX Large Installation System Administration Conference (LISA '07), November 2007.
- Š. Davidovič and B. Beyer, Canary Analysis Service, Communications of the ACM (CACM), May 2018.
- E. Zhai et al., Check before You Change: Preventing Correlated Failures in Service Updates, In Proceedings of the 17th USENIX Symposium on Networked Systems Design and Implementation (NSDI '20), Feb. 2020.

Software Testing and Analysis

Thu
3/24

G. Li et al., Efficient Scalable Thread-Safety-Violation Detection: Finding thousands of concurrency bugs during testing, In Proceedings of the 27th ACM Symposium on Operating Systems Principles (SOSP '19), October 2019.
T. Leesatapornwongsa et al., SAMC: Semantic-Aware Model Checking for Fast Discovery of Deep Bugs in Cloud Systems, In Proceedings of the 11th USENIX Symposium on Operating Systems Design and Implementation (OSDI '14), October 2014.
To grab an overview of industry practices of testing distributed systems, watch the video: C. McCaffrey, The Verification of a Distributed System, goto; conference, May 2016,
or read the article: C. McCaffrey, The Verification of a Distributed System, Communications of the ACM (CACM), Vol. 59 No. 2, pp. 52-55, February 2016.
(Optional) related papers:
- C. Sadowski et al., Lessons from Building Static Analysis Tools at Google, Communications of the ACM (CACM), Vol. 61 No. 4, Pages 58-66, April 2018.

Observability

Tue
3/29

P. Huang et al., Capturing and Enhancing In Situ System Observability for Failure Detection, In Proceedings of the 13th USENIX Symposium on Operating Systems Design and Implementation (OSDI '18), October 2018.
J. B. Leners et al., Detecting failures in distributed systems with the FALCON spy network, In Proceedings of the 23rd ACM Symposium on Operating Systems Principles (SOSP '11), October 2011.
(Optional) related papers:
- J. B. Leners et al., Improving Availability in Distributed Systems with Failure Informers, In Proceedings of the 10th USENIX Symposium Networked Systems Design and Implementation (NSDI '13), April 2013.
- J. B. Leners et al., Taming uncertainty in distributed systems with help from the network, In Proceedings of the 10th ACM European Conference on Computer Systems (EuroSys '15), April 2015.

Checkpoint-1 Workshop

Thu
3/31

Lightening talks on your Checkpoint-1 reports.

Guest Lecture

Tue
4/5

Designing Serverless Platforms to Support Emerging Applications

Failure Recovery

Thu
4/7

A. Ganesan et al., Redundancy Does Not Imply Fault Tolerance: Analysis of Distributed Storage Reactions to Single Errors and Corruptions, In Proceedings of the 15th USENIX Conference on File and Storage Technologies (FAST '17), Feb. 2017.
H. S. Gunawi et al., FATE and DESTINI: A Framework for Cloud Recovery Testing, In Proceedings of the 8th USENIX Symposium on Networked Systems Design and Implementation (NSDI '11), March 2011.
(Optional) related papers:
- M. Rinard et al., Enhancing Server Availability and Security Through Failure-Oblivious Computing, In Proceedings of the 6th Symposium on Operating Systems Design and Implementation (OSDI '04), December 2004.
- C. Candea et al., Microreboot – A Technique for Cheap Recovery, In Proceedings of the 6th Symposium on Operating Systems Design and Implementation (OSDI '04), December 2004.

Production Testing

Tue
4/12

P. Alvaro et al., Automating Failure Testing Research at Internet Scale, In Proceedings of the 6th ACM Symposium on Cloud Computing (SOCC '16), October 2016.
A. Basiri et al., Chaos Engineering, IEEE Software, Vol. 33, Issue 3, Page 35-41, May 2016.
K. Veeraraghavan et al., Kraken: Leveraging Live Traffic Tests to Identify and Resolve Resource Utilization Bottlenecks in Large Scale Web Services, In Proceedings of the 12th USENIX Symposium on Operating Systems Design and Implementation (OSDI '16), November 2016.
K. Veeraraghavan et al., Maelstrom: Mitigating Datacenter-level Disasters by Draining Interdependent Traffic Safely and Efficiently, In Proceedings of the 13th USENIX Symposium on Operating Systems Design and Implementation (OSDI '18), October 2018.
(Optional) the original Molly paper:
- P. Alvaro et al., Lineage-driven Fault Injection, In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data (SIGMOD '15), May 2015.
(Optional) related papers on chaos engineering:
- P. Alvaro and S. Tymon, Abstracting the Geniuses Away from Failure Testing, Communications of the ACM (CACM), January 2018.
- A. Tseitlin, The Antifragile Organization, Communications of the ACM (CACM), August 2013.
- K. Kingsbury, Jepsen: A framework for distributed systems verification, with fault injection,
(optional) DiRT and GameDay:
- K. Krishnan, Weathering the Unexpected, Communications of the ACM (CACM), Vol. 55, No. 11, Pages 48-52, November 2012.
- J. Robbins et al., Resilience Engineering: Learning to Embrace Failure, ACM Queue, Vol. 10, Issue 9, Pages 1–9, September 2012.

Tracing

Thu
4/14

J. Mace et al., Pivot Tracing: Dynamic Causal Monitoring for Distributed Systems, In Proceedings of the 25th ACM Symposium on Operating Systems Principles (SOSP '15), October 2015.
J. Kaldor et al., Canopy: An End-to-End Performance Tracing And Analysis System, In Proceedings of the 26th ACM Symposium on Operating Systems Principles (SOSP '17), October 2017.
(optional) other tracing systems and frameworks
- B. H. Sigelman et al., Dapper, a Large-Scale Distributed Systems Tracing Infrastructure, Google Technical Report dapper-2010-1, April 2010.
- R. Fonseca et al., X-Trace: A Pervasive Network Tracing Framework, In Proceedings of the 4th USENIX Symposium on Networked Systems Design and Implementation (NSDI '07), Apirl 2007.
- Ú. Erlingsson et al., Fay: Extensible Distributed Tracing from Kernels to Clusters, In Proceedings of the 23rd ACM Symposium on Operating Systems Principles (SOSP '11), October 2011.

Hacker's Day

Tue
4/19

No class. Focus on your projects and assignments.

Diagnosis

Thu
4/21

Y. Zhang et al., Pensieve: Non-Intrusive Failure Reproduction for Distributed Systems using the Event Chaining Approach, In Proceedings of the 26th Symposium on Operating Systems Principles (SOSP '17), October 2017.
R. Bhagwan et al., Orca: Differential Bug Localization in Large-Scale Services, In Proceedings of the 13th USENIX Symposium on Operating Systems Design and Implementation (OSDI '18), Oct. 2018.
(optional) related work on failure diagnosis
- C. Scott et al., Minimizing Faulty Executions of Distributed Systems, In Proceedings of the 13th USENIX Symposium on Networked Systems Design and Implementation (NSDI '16), March 2016.
- D. Yuan et al., Be Conservative: Enhancing Failure Diagnosis with Proactive Logging, In Proceedings of the 10th USENIX Symposium on Operating Systems Design and Implementation (OSDI '12), November 2012.
- D. Yuan et al., SherLog: Error Diagnosis by Connecting Clues from Run-time Logs, In Proceedings of the 16th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS XVI), March 2011.

Formal Verification

Thu
4/28

J. Bornholt et al., Using Lightweight Formal Methods to Validate a Key-Value Storage Node in Amazon S3, In Proceedings of the 28th ACM Symposium on Operating Systems Principles (SOSP '21), October 2021.
C. Hawblitzel et al., IronFleet: Proving Practical Distributed Systems Correct, In Proceedings of the 25th ACM Symposium on Operating Systems Principles (SOSP '15), October 2015.
(Optional) related papers on verified systems:
- C. Newcombe et al., How Amazon Web Services Uses Formal Methods, Communications of the ACM (CACM), Vol. 58 No. 4, Pages 66-73, April 2015.
- P. Fonseca et al., An Empirical Study on the Correctness of Formally Verified Distributed Systems, In Proceedings of the 2017 European Conference on Computer Systems (EuroSys '17), April 2017.

Final Review and Conclusion

Tue
5/3

No more readings.