CS 848/858: Models and Applications of Distributed Data Processing Systems

(Fall 2016)

Semih Salihoglu
firname [dot] lastname [at] uwaterloo [dot] ca
DC 3351
Meeting times: Mon-Wed 9:00am
Meeting location: DC 2568

Announcements

Overview

This is a project-based seminar course that is aimed to survey the different models that underly modern large-scale data processing systems, such as MapReduce, Spark, Pregel, Flink, Storm, Timely, and others. The goal is to identify the fundamental advantages and limitations of different models and demonstrate the systems and applications that are built on each model. Main topics include bulk synchronous processing, asynchronous systems, streaming systems, and timely and differential dataflow. For each model, we will study a theoretical model, the systems built on the model, and applications that are built on the systems. We will also cover two recent topics: disorderly distributed data-driven programming and coflow networking, which despite not lying directly in data management, address two exciting challenges that arise in distributed data processing.

Distributed data processing is an exciting research area, to which systems, theory, and application researchers all make significant contributions. Our goal in this seminar will be to cover papers from all three areas. This is not a theory seminar, but we will read some theoretical papers to understand the fundamentals of these systems.

One important goal of the seminar is to cover some of the good PhD theses that were written in the area in the last 5 years. We will discuss what made those theses impactful. So, unlike some other seminars, we will sometimes be reading thesis chapters.

Prerequisites

Students are expected to understand the fundamentals of databases, algorithms, and operating systems each at least at the level of an introductory course.

Workload & Mark Breakdown

The main workload will consist of a term-long project that students will do on one of the systems covered in the seminar. The other workload includes paper reviews and presentations. Detailed information for each piece is below. This is a seminar, so your participation in the class is very critical to everyone's learning. That is why it will be a significant part of your grade. Please ask questions and make comments throuhout the discussions that we will have. The workload pieces and mark breakdown is as follows:

• Class Participation: 15%
• Paper Reviews: 20%
• Presentations: 20%
• Project: 45%

Projects

• Build a new application on top of one of the systems.
• Build a new feature/extension to an existing system.
• Implement a new algorithm that replaces a core part of a system (e.g., scheduling algorithm of a system).
• If interested in theory? Talk to me.

Project Deliverables

• Project presentation: You will deliver these on December 5th. Each project has 12 minutes of presentation time. Please make your presentations short and succinct. Do not forget to identify and answer the 6 questions that any technical presentation (or paper) has to answer. After your presentations, please send me your slides.
• Project Writeup: The project writeups will be minimum 8 pages and maximum 10 pages, including citations, presented in the two-column ACM proceedings format, using one of the ACM SIG Proceedings Templates. Essentially they should be similar in structure to the papers we have read in the seminar. Make sure you include the following sections: (1) Abstract; (2) Introduction that answers the first 4 of "the 6 importantn questions" (see here again); (3) Background (if necessary); (4) Sections where you describe your technical contributions; (5) Evaluation; (6) Related Work; and (7) Future Work. Please watch out for the following in your writeups:
  • Be explicit in your sentences. Avoid non-referential "it", "this", "they", etc.
  • Avoid informal language.
  • Use examples to demonstrate the points you are making.
  • Avoid passive language.
• Project Source Code: Please put your source code into github and include a link in your Project Writeup. On the github page, please document exactly how to run your source code to run your code.

Paper Reviews

For each class we will be writing a review of one of the papers assigned to that day (except the first and last classes). If there are more than one papers assigned, you can pick either one. You are allowed to skip 2 reviews throughout the term. The reviews will be at most 1 page long and roughly 2 paragraphs. You have to finish your review with one question that can start a discussion in the seminar. You are expected to (very very) briefly answer the following 6 questions and finish your reviews with a question that can start a discussion in class:

• What is the problem?
• Why is it important?
• Why is it hard? Why don't naive/previous methods work?
• What is the solution to the problem the authors propose?
• What interesting research questions does the paper raise?
• (If related) How does the paper relate to other papers we have read?

Presentations

Each student will roughly be doing 2 presentations per term. When there are 2 presenters in a day, the presentations will be 20 minutes long. If you are the only presenter that they, then the presentation will be slighly longer, 25-30 minutes long. Here are the importatant points summarizing what you have to do for your presentations.

• You should be presenting with slides. The content in your slides should be your own but you can use others' materials, e.g., figures from the paper we are reading, when necessary and by crediting your source on your slide.
• Important: Please have 1 slide answering the 6 questions about the paper outlined above in the Paper Review section.
• Important: When presenting a system, please show example code and a simulation of the execution of the code (e.g., a small (2 or 3 machine) distributed cluster executing the code and how the data is changing).

Schedule and Papers (TBA)