Syllabus
CS 431: Data-Intensive Distributed Computing (Fall 2026)

• What does it mean to be an AI-first or data-driven company?
• What's the data flywheel?
• What's data engineering?
• What are data platforms?
• What are the 4 V's of data?
• What is this course about? And what is it not about?

• Fundamentals of Data Engineering:
  • Chapter 1. Data Engineering Described
• Designing Data-Intensive Applications, 2nd Edition:
  
  • Chapter 1. Trade-offs in Data Systems Architecture

The above readings are available for free online through the university's library. The links above point directly to Waterloo proxied content, but if you're having trouble accessing the material (e.g., due to VPN settings), you might have to go through the library's portal (i.e., search for the book title and follow the appropriate links).

PDF slides for Sep 10 (v1.00)

• What are the main differences between operational and analytical infrastructure?
• What are data warehouses? What problems did they evolve to solve?
• What are data lakes and lakehouses? What problems did they evolve to solve?
• What are the components of modern data platforms?
• How do operational and analytical data models differ?
• What goes on in ETL/ELT?
• How do different physical representations of data affect storage, compute, and other tradeoffs within data platforms?

• Designing Data-Intensive Applications, 2nd Edition:
  
  • Chapter 3. Data Models and Query Languages — skip "Event Sourcing and CQRS" but read everything else
  • Chapter 4. Storage and Retrieval — Intro section and "Data Storage for Analytics" (i.e., skip "Storage and Indexing for OLTP" and "Multidimensional and Full-Text Indexes")
  • Chapter 5. Encoding and Evolution — Intro section and "Formats for Encoding Data" (skip "Modes of Dataflow")
• (Optional) Fundamentals of Data Engineering (These readings cover similar content but offer a complementary perspective):
  • Chapter 3. Designing Good Data Architecture — Discussion of data warehouses, ETL, etc.
  • Chapter 8. Queries, Modeling, and Transformation — Discussion of data modeling, star and snowflake organizations, etc.

The above readings are available for free online through the university's library. The links above point directly to Waterloo proxied content, but if you're having trouble accessing the content (e.g., due to VPN settings), you might have to go through the library's portal (i.e., search for the book title and follow the appropriate link).

• What Goes Around Comes Around... And Around... by Michael Stonebraker and Andrew Pavlo (2024). Answers the question: Why relational?
• What Goes Around Comes Around by Michael Stonebraker and Joseph M. Hellerstein (2005). Optional reading, but provides nice historical perspective, written over 20 years ago.
• Introduction to Data Lakes from Databricks.
• What is a Data Lake? from Microsoft. (It's helpful to get multiple perspectives, even if some aspects are repetitive.)
• What Is a Lakehouse? from Databricks.
• What is a medallion architecture? from Databricks.

PDF slides for Sep 15 (v1.01) PDF slides for Sep 17 (v1.00)

• What's the difference between scaling up and scaling out?
• What are the implications of distributed processing across many machines?
• What are the challenges for a divide-and-conquer strategy?
• What challenges does partitioning address? What challenges does it exacerbate?
• What challenges does replication address? What challenges does it exacerbate?
• What's MapReduce and how does it work with HDFS?
• What challenges do communication and skew present in scaling out?
• Why is local aggregation important?

• Designing Data-Intensive Applications, 2nd Edition:
  
  • Chapter 2. Defining Nonfunctional Requirements
  • Chapter 5. Encoding and Evolution — Intro section and "Formats for Encoding Data" (repeated from last week, ties in with 2nd lecture last week)
  • Chapter 6. Replication — Intro section and "Single-Leader Replication" (Hadoop uses single-leader replication)
  • Chapter 7. Sharding — Intro section to "Request Routing", inclusive (Hadoop uses option 2 in Figure 7-7; "Sharding of Key-Value Data" won't be directly relevant until next week, but makes sense to read together)
• Hadoop: The Definitive Guide, 4th Edition:
  
  • Chapter 3. The Hadoop Distributed Filesystem
  • Chapter 7. How MapReduce Works

Although the Hadoop book is quite old, the overall design of the framework remains relevant. Focus on its overall architecture and the tradeoffs encoded in the design; you can safely ignore details such as specific APIs, command-line invocations, classes, etc.

The above readings are available for free online through the university's library. The links above point directly to Waterloo proxied content, but if you're having trouble accessing the content (e.g., due to VPN settings), you might have to go through the library's portal (i.e., search for the book title and follow the appropriate link).

The following are optional. They comprise some of the primary sources from which lecture content is drawn, and can enrich your understanding by providing broader context.

• The Datacenter as a Computer: Designing Warehouse-Scale Machines, Fourth Edition by Luiz André Barroso, Urs Hölzle, Parthasarathy Ranganathan. (This is a long book, but worthwhile to flip through and read anything that catches your attention if you want a better understanding of datacenter design.)
• The original GFS paper
• The original MapReduce paper

In the original GFS/MapReduce papers, you'll notice an emphasis on aggregated storage (i.e., compute-disk locality). But that was over two decades ago... how does that approach compare to modern trends?

PDF slides for Sep 22 (v1.00) PDF slides for Sep 24 (v1.00)

Key Questions

• In what ways does Spark improve over MapReduce?
• How is distributed group by implemented efficiently at scale?
• How do commutative and associative operations contribute to efficient distributed execution?
• How does partitioning contribute to efficient distributed execution?
• How do these concepts come together in efficient joins at scale?

Reread the assigned readings from last week (or read for the first time if you haven't yet). The material will make a lot more sense given the lecture material. In addition:

• High Performance Spark:
  
  • Chapter 2. How Spark Works
  • Chapter 4. Joins (SQL and Core)
• Data-Intensive Text Processing with MapReduce:
  
  • Chapter 2. MapReduce Basics
  • Chapter 3. MapReduce Algorithm Design

Although both books are quite old, overall design, system architecture, and tradeoffs remain relevant. Focus on these aspects; you can safely ignore details such as specific APIs, command-line invocations, classes, etc. In the MapReduce book, Hadoop-specific material is outdated in the Spark context, but associativity and commutativity remain important as high-level concepts, independent of the execution framework.

The above readings are available for free online through the university's library. The links above point directly to Waterloo proxied content, but if you're having trouble accessing the content (e.g., due to VPN settings), you might have to go through the library's portal (i.e., search for the book title and follow the appropriate link).

The following are optional. They comprise some of the primary sources from which lecture content is drawn, and can enrich your understanding by providing broader context.

• The original Spark paper
• Paper about Spark SQL

PDF slides for Sep 29 (v1.00) PDF slides for Oct 1 (v1.00)

PDF slides for Oct 6 (v1.00) PDF slides for Oct 8 (v1.00)

PDF slides for Oct 20 (v1.00)

Back to top

• What are the key components of an ML solution?
• How is the supervised machine learning problem formulated?
• What roles do data platforms and data engineering play?

• Designing Machine Learning Systems:
  
  • Chapter 2. Introduction to Machine Learning Systems Design — read the section on "Iterative Process", which provides a nice overview of the entire "ML process".
  • Chapter 7. Model Deployment and Prediction Service — Intro section, "Machine Learning Deployment Myths", and "Batch Prediction Versus Online Prediction"
  • Editorial note: there's a lot of solid practical advice in this book. If you're interested in machine learning, there are many topics of interest; skim/read at your leisure.
• Jimmy Lin and Dmitriy Ryaboy. Scaling Big Data Mining Infrastructure: The Twitter Experience, SIGKDD Explorations, 14(2):6-19, 2012.

The above readings are available for free online through the university's library. The links above point directly to Waterloo proxied content, but if you're having trouble accessing the content (e.g., due to VPN settings), you might have to go through the library's portal (i.e., search for the book title and follow the appropriate link).

The following are optional. They provide a deeper dive of lecture content that can enrich your understanding and provide broader context.

• Naive Bayes and Logistic Regression, Tom Mitchell
• Deep Learning: Foundations and Concepts, Christopher M. Bishop and Hugh Bishop [alternative source]
  
  • Chapter 7: Gradient Descent
  • Chapter 5.4.3: Logistic Regression

PDF slides for Oct 27 (v1.00) PDF slides for Oct 29 (v1.00)

• How do data products with operational requirements complicate lakehouse architectures?
• Why does retrieval remain important in the era of LLMs?
• How is retrieval formulated as the problem of computing vector similarity?
• What's the intuition behind sparse and dense vector representations?
• For sparse vector representations, how do we assign weights?
• For sparse retrieval, how do we perform top-k retrieval efficiently?

• Data-Intensive Text Processing with MapReduce:
  
  • Chapter 4. Inverted Indexing for Text Retrieval
• Pretrained Transformers for Text Ranking:
  
  • Chapter 1. Introduction
  • Chapter 2. Setting the Stage
• Introduction to Information Retrieval:
  
  • Chapter 1. Boolean retrieval [Direct Link]

The above readings are available for free online through the university's library. The links above point directly to Waterloo proxied content, but if you're having trouble accessing the content (e.g., due to VPN settings), you might have to go through the library's portal (i.e., search for the book title and follow the appropriate link).

PDF slides for Nov 3 (v1.00)

• For sparse vector representations, how do we assign weights?
• For sparse retrieval, how do we perform top-k retrieval efficiently?
• For dense vector representations, how do we assign weights?
• For dense retrieval, how do we perform top-k retrieval efficiently?
• Do we need specialized databases for sparse and dense vectors?
• Can we also learn sparse representations from data?
• Why do we need rerankers?
• What's the relationship between RAG and LLM tool use?
• What challenges does MCP address?

• What do hash collisions have to do with finding similar items?
• When do you use minhash? And random projections?
• What are the knobs you control and what do they do?
• What makes certain types of clustering algorithms amenable to scale-out distributed processing?
• What are the parallels between k-means clustering and Gaussian Mixture Models?

• What are alternative approaches to representing graphs?
• Why are graph algorithms challenging in MapReduce/Spark?
• What is the general structure of graph traversals in MapReduce/Spark?
• Why (even) MapReduce/Spark (for graph processing)?

• What are the challenges associated with stream processing?
• What are the common patterns in connecting data producers and data consumers?
• What are some common data structures and algorithms for processing unbounded streams?
• What's the distinction between event time and processing time?
• How do stream processing platforms fit into the lakehouse?