Comprehension and Analysis of Large Systems

538B, Winter 2014, Ivan Beschastnikh

MW 9:30-11:00, ICCS 206, UBC course page

Course description

Billions of people rely on correct and efficient execution of large software systems, such as the distributed systems that power Google and Facebook. Yet these systems are complex and challenging to build, maintain, extend, and understand.

• How do engineers, those who design and implement such systems, cope with these issues today?
• Are these pain-points inherent to complex software, or can they be mitigated?
• As researchers, what tools/abstractions/software processes can we propose to help engineers do a better job in building reliable and robust systems?

This course will cover a broad range of topics that fall into the general category of comprehension and analysis of software systems, with the hope of shedding light on some of the above questions.

Format

This seminar-style course will be grounded in discussion of papers that appeared in top conferences in systems, software engineering, program analysis, and more. There is no textbook. The course will also include a substantial team-based course project.

• The discussion in each class will focus on 1-2 papers
• The discussion for each paper is led by two students, an advocate and a skeptic
• Everyone except for the paper advocate and skeptic writes a review of each of the assigned papers, due at 9 PM the day before class
• Students work in pairs on a course-long project in an area related to the class

Advocate and skeptic are in charge of leading the discussion for a paper. Do not use slides. Instead, give a concice summary of the reading and pose questions to dig deeper into why the paper was written, what can we take away from it, how does the paper relate to the course, why it is or is not the final word on the subject, etc.

Advocate and skeptic need to review any other paper(s) that are discussed on same day, but they do not need to write a review for the paper they are leading.

Please create an account on the hotcrp server. This is the system where you are responsible for entering reviews on the papers that we discuss in class.

Also, sign up for the class Piazza instance. We will use this for most class communication.

Schedule (a work in progress)

Papers pool

• Schneider. Implementing Fault-Tolerant Services Using the State Machine Approach: A Tutorial.
• Fisher, Lynch, and Paterson. Impossibility of Distributed Consensus with One Faulty Process
• Protocol Buffers
• Nightingale, Douceur, and Orgovan. Cycles, Cells and Platters: An Empirical Analysis of Hardware Failures on a Million Consumer PCs
• Yuan, Park, and Zhou. Characterising Logging Practices in Open-Source Software
• Yin et al. How Do Fixes Become Bugs?
• Musuvathi et al. Finding and Reproducing Heisenbugs in Concurrent Programs
• Anvik et al. Who should fix this bug?
• Pacheco et al.Feedback-directed random test generation
• Burg et al.Interactive record/replay for web application debugging
• Zeller et al.Simplifying and Isolating Failure-Inducing Input
• Device Driver Safety Through a Reference Validation Mechanism. OSDI 2008
• Model Checking a Networked System Without the Network. NSDI 2011.
• Pip: Detecting the Unexpected in Distributed Systems. NSDI 2006
• CrystalBall: Predicting and Preventing Inconsistencies in Deployed Distributed Systems. NSDI 2009.
• Checking system rules using system-specific, programmer-written compiler extensions. OSDI 2000.
• BorderPatrol: isolating events for black-box tracing. EuroSys 2008.
• S2E: a platform for in-vivo multi-path analysis of software systems. ASPLOS 2011.
• Characterizing Logging Practices in Open-Source Software. ICSE 2012.

Project

The project must be a substantial (three months long) software effort and must be done in collaboration with one other student who is taking the course for credit. Example project categories (don't limit yourself to these!):

• Implement a new comprehension/analysis technique or re-create an existing technique and evaluate it.
• Extend an existing comprehension/analysis tool in some interesting way, and evaluate it.
• Simplify/constrain an existing technique/tool and evaluate it on a large software system.
• Organize and perform a pilot study on a small set of developers to better understand/refine a software comprehension issue.

The project is structured as series of regularly occurring deadlines (listed in the schedule above). Don't miss these! The deadline deliverable must be submitted by email to the instructor by 9 PM of the day of the deadline.

• The project proposal must be no longer than 5 pages and include at least the following sections: introduction, motivation, research questions, proposed methodology, timeline.
• The project presentation/demo must be no longer than 10 minutes long and will be followed by a five minute Q/A.
• The project report should be no longer than 10 pages long and resemble a research paper.

Grading

Final course mark will be based off of:

• Paper reviews: 30%
• Class participation: 20%
• Project: 50%
• Proposal: 10%
• Presentation: 10%
• Final report: 30%

How to do well in the course

Show up to class on time and be prepared to participate in discussion. This is a seminar-style course, which means that all of the class time will be devoted to discussion. It is expected that each student contributes to the discussion in each class session. The best way to prepare for class is to read the assigned paper(s), write a thoughtful review, and then read and carefully consider the reviews submitted by your peers. Periodically re-read the readings from 1/6 and work to improve your paper reading and reviewing abilities.

Invest time into the project. Do not underestimate the importance of a thorough (and interesting!) project proposal. Proposal write-ups that are vague or are incomplete will not be accepted. Do not delay finding a partner and put in consistent, weekly effort throughout the term. Rehearse and polish your presentation, and make sure your final report is well-written and conveys its ideas clearly.

Email and schedule a time to meet with the instructor to discuss the course, project ideas, etc. Be proactive.