UIUC CS 425 / ECE 428 分布式系统 · 开篇与课程概览

目录 · l1 →

Distributed Systems — Fall 2026, University of Illinois at Urbana-Champaign

基于 UIUC CS 425 / ECE 428 公开课程资料整理，以分布式算法实现与正确性论证为核心 配套：可运行的 Python 实现 · 算法伪代码 · 安全性/活性论证 · 复杂度分析 · 真实系统案例

第一部分：课程概览

1. 这门课在教什么

CS 425 / ECE 428 是 UIUC 的分布式系统核心课程。用课程讲义自己的话说，它关心四件事：

1. Distributed Systems —— 分布式系统是什么样的系统
2. How to design algorithms for them —— 如何为它们设计算法
3. How to design these systems —— 如何设计系统
4. How they work in real life / How to build real distributed systems —— 它们在真实世界中如何工作、如何真正构建出来

这不是一门”介绍各种云产品”的课，而是一门讲原理、讲算法、讲正确性的课。整门课的主线是：

在自治、可编程、异步、易故障的实体集合之上，通过不可靠的通信介质， 如何设计出可扩展、容错、且行为可被证明正确的系统？

课程的三个层次贯穿始终：

2. 课程的目标定义（本课程的”工作定义”）

课程给出的、贯穿全学期的工作定义是：

A distributed system is a collection of entities, each of which is autonomous, programmable, asynchronous and failure-prone, and which communicate through an unreliable communication medium.

这个定义值得逐词拆解，因为它直接决定了后面每一讲算法的假设：

课程同时给出了 Lamport 那个著名的、带着黑色幽默的定义：

“A distributed system is one in which the failure of a computer you didn’t even know existed can render your own computer unusable.” —— Leslie Lamport

以及几个”看起来不错但对设计者不够用”的经典定义：

• Tanenbaum：a collection of independent computers that appear to the users of the system as a single computer.
• Schroeder：several computers doing something together，因此有三个主要特征：multiple computers、interconnections、shared state。
• FOLDOC：A collection of (probably heterogeneous) automata whose distribution is transparent to the user so that the system appears as one local machine.

课程明确说这些定义”unsatisfactory“，原因是它们只描述了外观（透明性），而没有描述内部——而本课程恰恰关心 internal 的 design and implementation、maintenance、和 algorithmics（protocols / distributed algorithms）。这是理解整门课立场的关键。

3. 课程范围

根据官方 Syllabus，课程主题包括（但不限于）：

MapReduce、peer-to-peer systems、failure detectors、synchronization、election、consensus、 inter-process communication、gossiping、concurrency control、replication、key-value stores、 NoSQL、security、probabilistic protocols、stream processing、measurements

这些主题被放在真实的、已部署的系统背景下讨论：云与数据中心、数据库、P2P 系统、集群。

课程明确不涵盖的内容：计算机网络与路由的细节、无线/移动计算（这些由 CS 438/439 等课程覆盖）。这是一个重要的边界——CS 425 从”网络已经提供了某种传输能力”开始，专注于在传输层之上构建分布式系统。

4. 先修要求

课程反复强调：This course assumes knowledge of fundamentals in both OS and networking. 虽然 CS 240/241 名义上是 co-requisite，但实际按”已修完”对待。

5. 课程基本信息

教学团队：主讲 Aishwarya Ganesan、Ram Kesavan；Lead TA：Nishant Sheikh；On-campus TAs：Rafid Murshed、Wei Zhang、Tianyi Zhong、Weidong Wang、Yaqi Qiao；MCS Online TAs：Xinying Zheng（Lead MCS Online TA 兼 Deputy Lead TA）、Soham Chakraborty。

6. 教材

主教材（推荐，非必需）

Coulouris, G., Dollimore, J., Kindberg, T., and Blair, G. Distributed Systems: Concepts and Design, Addison-Wesley, 5th Edition, 2011. ISBN: 0132143011

课程的一条硬性规定：所有章节号、小节号、习题号只以第 5 版为准。使用旧版本的学生需自行负责编号的转换（讲义原文：no excuses）。

主教材第 5 版的章节结构（本课程的主要对应关系）：

补充教材

1. Ghosh, S. Distributed Systems: An Algorithmic Approach, CRC Press, 2006, ISBN 1584885645. （UIUC 图书馆可在线免费访问；算法视角，与 Coulouris 的系统视角互补）
2. Tanenbaum, A. & van Steen, M. Distributed Systems: Principles and Paradigms, Prentice Hall, 2nd Ed., 2005, ISBN 0132392275.
3. Lynch, N. Distributed Algorithms: Concepts and Design, Morgan-Kaufmann, 1996, ISBN 1558603484. （分布式算法的理论经典）
4. Coulouris 等，第 4 版（可在 Grainger 图书馆查阅）

课程指定论文（Reading）

7. 评分与作业

学生分三类（Section）

分数构成（tentative）

评分是相对评分（curve），本科生与研究生分开 curve，3cr 与 4cr 分开 curve。官方说明：过去几年各组的中位数成绩在 B+/B。4cr 的 CS 425 满足院系的 team project / one-term capstone 要求（编程项目占比至少 30%）。

政策要点

• Best 3 of 4 Homeworks：4 次 HW 各 10 分，只取最高 3 次计入（最多 30 分）。适用于所有学生。但课程警告：不要因此完全放弃某次 HW，否则会丢失期中/期末所需的知识。
• HW：全部个人独立完成，必须提交打字版（手写不收）。每次 HW 的新题从新的一页开始。截止时间是美国中部时间 23:59（硬性，无延期）。
• MP（仅 4cr on-campus/Chicago）：必须 2 人一组（1 人、3 人及以上都不接受）。共 4 次，每次需要 2-4 周工作量，包含报告 + 现场 demo（Chicago 学生通过 Zoom）。所有组可获得 CS VM Farm 集群的访问权限。编程语言自选。
• 考试：期中 10/8（课堂内，75 分钟，闭卷闭笔记，允许计算器，不允许 cheatsheet 与任何电子设备），范围 Lectures 1-12 + HW1-2。期末 3 小时，范围 Lectures 1-29 + HW1-4。补考/冲突考试需提前 2 周申请，且不因旅行、面试、课程冲突批准。
• 学术诚信：所有提交必须是本人/本组从零到完成的原创。HW/MP 只能使用提供的课程材料。明确禁止使用 LLM/ChatGPT/Gemini 等 AI 工具（讲义原文：trust us, they will give you wrong solutions）。在 Piazza 上泄露解答即视为违规。首次违规该次作业 0 分，第二次违规整门课 F。
• Regrade：成绩返回后 1 周内在原提交系统中提交，TA 的决定是最终决定（不能再对 regrade 结果 regrade）。

⚠️ 笔记使用声明：本笔记是为学习和理解而整理的知识材料。由于课程禁止使用 AI 工具完成 HW/MP，本笔记中的任何代码不应用于作业提交。笔记的目的是帮助你建立分布式系统的知识体系与直觉。

8. 课程日程（Fall 2026，共 29 讲）

作业时间线

9. 本笔记的组织方式

本笔记按上面 29 讲的顺序组织，共 27 章（Lecture 14 为考试，无笔记；部分内容相近的讲座合并为一章）：

用户需求主题 → 章节对应表

每章统一结构

每章严格遵循以下 8 段式结构，以便横向对照学习：

1. 概述 —— 本讲核心问题与在课程中的位置
2. 核心概念与分布式机制图解 —— 概念定义 + 直观类比 + ASCII 机制图 + 系统模型假设
3. 算法伪代码与正确性分析 —— 假设与系统模型 → 伪代码 → 算法逻辑解说 → 安全性/活性论证 → 复杂度
4. 代码示例与分布式实现 —— 可运行的 Python 实现 + “代码做什么” + “分布式机制透视” + “与理论的对应”
5. 性能与可扩展性分析 —— 时间/消息/空间复杂度、容错能力、真实系统表现
6. 关键要点 —— 3-6 条”分布式系统黄金法则”
7. 常见陷阱与注意事项 —— 学生最易犯的错误与正确做法
8. 思考题（带答案） —— 概念题 + 计算推演题 + “错在哪里”类问题

第二部分：课程公开资料获取记录

10. 资料抓取范围与方法

本笔记的所有技术内容均来自以下公开可访问的课程资料。抓取范围与方法如下：

10.1 公开可访问并已抓取的资源

10.2 Fall 2026 学期已发布的讲义（公开）

重要说明：Fall 2026 学期在进行中，课程表上 lectures.html 对每讲的幻灯片都给出了 [ppt] [pdf] 链接，但只有上述 7 份 PDF 实际可下载。其余讲次的幻灯片页面标注为 “Tentative” 且文件尚未上传（HTTP 404），这是学期进度导致的正常现象，不是访问限制。

10.3 为保证笔记完整性而补充的同等资料（公开）

由于 FA2026 仅发布了前 6 讲的讲义，本笔记同时抓取了同一门课程 Fall 2025 的完整讲义集（/cs425/fa2025/）。选择 FA2025 的理由：

• 同一课程代码、同一课程体系、同一教材（Coulouris 5th Ed.），讲义内容与 FA2026 高度一致（FA2026 的前几讲与 FA2025 逐页对应）
• FA2025 的 29 讲全部幻灯片均已公开，是本课程最完整的公开技术资料来源
• FA2026 的讲座主题序列与 FA2025 基本一一对应

合计 28 份讲义、1142 页、约 19 MB。

补充取自 FA2025 的 Spark 讲义（L26.B.FA25.pdf，17 页）—— FA2026 课程表规定所有学生必须观看 Spark 视频（在考试范围内），因此该主题的讲义内容以 FA2025 版本为准。

10.4 课程站公开的指定论文

⚠️ 一处课程网站链接错标的记录：lectures.html 在 Lecture 23 的 “DRF Paper” 标签下指向 http://www.eecs.berkeley.edu/Pubs/TechRpts/2012/EECS-2012-259.pdf，但该 PDF 的实际内容是 《Discretized Streams: A Fault-Tolerant Model for Scalable Stream Processing》（Zaharia et al., UCB/EECS-2012-259, 2012 年 12 月），即 Spark Streaming 的原始论文，而非 DRF（Dominant Resource Fairness）论文。DRF 的原始论文是 Ghodsi et al., Dominant Resource Fairness: Fair Allocation of Multiple Resource Types, NSDI 2011，课程站未提供该 PDF。本笔记在 Lecture 21 章节中已如实标注这一差异：Spark Streaming 的容错细节依据该 Berkeley 技术报告，DRF 部分依据讲义口径与 NSDI 2011 的四条公理。

10.5 受限资源（仅记录名称，未抓取内容）

以下资源需要 UIUC netid、课程注册或付费订阅，本笔记不包含其内容，仅如实记录其存在与访问条件：

结论：课程的知识框架完全可以通过公开资料重建——讲座主题序列（lectures.html）、教材章节结构（Syllabus + 教材目录）、以及 28 份完整讲义幻灯片（FA2025）共同构成了足够的技术基础。受限的主要是作业题、考试成绩、讨论区互动和录播视频，这些属于教学管理资源而非知识内容。

11. 公告记录（Announcements）

课程主页的公告栏（Oldest First，最新公告移至 Piazza）：

关键信息：从 8/25 起，所有后续公告都只在 Piazza 发布。这意味着课程主页的公告栏不会继续更新，重要信息（如考试地点、截止日期变更、MP 澄清、Piazza pinned post 中的说明）需要通过 Piazza 获取。这是本笔记无法覆盖的部分。

12. 课程政策全文要点

12.1 学术诚信政策（原文要点）

课程遵循 CS 学术诚信政策。核心条款：

It is the course policy that all of the work you submit for grading, or in support of graded material, as an individual or project group, shall be your own product, from inception to completion. The only resources you can avail of in your HWs and MPs are the provided course materials (slides, textbooks, etc.), and communication with instructor/TA via newsgroup and email.

• 与他人只能讨论课程材料和 HW/MP 的题目本身，不能讨论解法或思路
• 禁止在 Piazza 上泄露解答（包括代码或书面解答）——视为学术诚信违规
• 明确禁止 AI 工具：You cannot use any AI tools like LLMs, ChatGPT, Gemini, etc.
• 考试闭卷闭笔记（除非另有说明）
• 每一份 HW 与 MP（含代码）都会被严格检查违规

违规后果（原文）：

• 第一次违规：该次 HW/MP 得 0 分
• 第二次违规：整门课程 F
• 课程说明：过去我们抓到了几乎所有作弊的学生

12.2 反种族主义 / 反偏见 / 反微侵犯政策

Grainger 工程学院承诺建设反种族主义的包容性社区。课程声明遵循学院的 Anti-Racism and Inclusivity Stance，并鼓励学生向 BART（Bias Assessment and Response Team, https://bart.illinois.edu/） 报告歧视、微侵犯或其他冒犯行为。课程也遵循 CS CARES 与 CS Values and Code of Conduct。

12.3 心理健康声明

课程提供 UIUC 的心理健康资源：

• Counseling Center：217-333-3704，610 East John Street, Champaign, IL 61820
• McKinley Health Center：217-333-2700，1109 South Lincoln Avenue, Urbana, IL 61801
• University Wellness Center

12.4 校园紧急情况

遵循校园的 Run, Hide, Fight 应急指引。

12.5 其他重要政策

• 注册与 waitlist：院系不维护 waitlist，不能授予超出容量的 override。请按时提交 HW 和 MP（即使尚未注册成功）。若 9/30 前仍无法注册，联系课程 staff。
• 3cr 转 4cr：前几周通常会有空位。请先按 4cr 提交 MP；若 9/30 前无法转入 4cr，联系 staff。
• 时间冲突 override：由于班级规模，拒绝需要为期中/期末提供冲突考试的请求。若你的另一门课保证没有冲突考试且你愿意放弃参与分（participation points），可以在邮件中明确说明后申请。
• 本科生注册研究生 section：注册哪个 section 对将来把课程转入硕士学分没有影响（只要该课程未被用于本科学位）。
• 无补考政策：补考只在极少数非学术情形（通常需要 Dean’s office 批准）下提供。因面试、旅行、其他课程 deadline 的延期申请一律不接受。
• DRES 学生：需在考试前至少 2 周（建议 3 周）邮件通知 instructors，并在 DRES 考试中心预约与校内考试同一天同一时间的场次。课程视频已在 DRES 的闭路字幕列表中，幻灯片也会提前发布。

13. 从资料中提炼的”课程精神”

从讲义与 syllabus 的行文中可以提炼出本课程反复强调的几条立场，它们解释了为什么这门课要这样组织：

1. “内部机制”比”外部定义”重要。课程批评经典定义”太短、太不充分”，因为它关心的是 insides：design and implementation、maintenance、algorithmics。

2. AI 时代更需要基础。Lecture 1 专门用一页讲”Computer Science in the time of AI”：

   AI is a capability multiplier: But, 0 × 1000 = 0; if your understanding of concepts, systems, and algorithms is zero, then you’ll produce zero! Prompts express intent, but true engineering is about trade-offs, performance, maintenance, and architectural taste.

3. 必须写代码、调试代码。课程明确说 fundamentals “requires deep engagement with the material; best gained by writing, reading, and debugging code”，并推荐”写并调试你的 MP”。

4. 算法正确性只在特定系统模型下有定义。同一算法在同步模型下可解，在异步模型下可能不可能（FLP）。这是课程把”系统模型”（Ch.3）放在所有算法之前的原因。

5. 权衡（trade-off）是分布式系统的核心语言。一致性 vs 可用性、状态 vs 通信、透明性 vs 性能、简单 vs 高效——每一讲最后都归结为一个取舍。

接下来进入各讲详细笔记。