分布式系统

MIT的Distributed Algorithms课程介绍(zz)

2012年10月13日 阅读(53)

zz from:http://www.myoops.org/main.php?act=course&id=2165

翻譯:林家弘

編輯:朱學恒,陳盈

Image of honeycomb, a common architectural metaphor for distributed algorithms.

The honeycomb shown above is a common architectural metaphor for distributed algorithms. Similar to bees performing different functions to build a honeycomb, multiple computing devices depend on each other to accomplish a task. (Image by MIT OCW.)

[PICS]

上圖所顯示的巢狀是一種分散式演算法常見的結構隱喻。類似蜜蜂分工合作以建造蜂巢,彼此依賴的複合式運算方式以完成任務。(圖像來自麻省理工開放式課程)

課程重點

This course features a complete bibliography of readings and, in the assignments section, all problem sets.

本課程以一份完整的閱讀材料清單的參考書目,以及在作業部份中所有的問題集為重點.

課程描述

This course intends to provide a rigorous introduction to the most important research results in the area of distributed algorithms, and prepare interested students to carry out independent research in distributed algorithms. Topics covered include: design and analysis of concurrent algorithms, emphasizing those suitable for use in distributed networks, process synchronization, allocation of computational resources, distributed consensus, distributed graph algorithms, election of a leader in a network, distributed termination, deadlock detection, concurrency control, communication, and clock synchronization. Special consideration is given to issues of efficiency and fault tolerance. Formal models and proof methods for distributed computation are also discussed.

Detailed information on the course textbook can be found here:

Lynch, Nancy A. Distributed Algorithms. San Francisco, CA: Morgan Kaufmann, 1997. ISBN: 1558603484.

這門課程企圖提供一個對分散式演算法領域裡最重要之研究結果的精確介紹,並且協助讓有興趣的學生在分散式演算法裡能執行獨立研究。主題包括︰同時運算演算法分析和設計,著重在那些合適在分散式網路使用的行程同步;運算資源配置;分散式的共識;分散式圖形演算法;網路領導的選擇;分散式結果終止;死結偵測;同時運算控制;溝通以及時脈同步。特別需要考慮的是,效能的議題和容錯。針對分散式運算的形式模型和驗證方法,也一併討論。

教科書上詳盡資料可以在這裡找到︰

Lynch, Nancy A. 《分散式演算法》舊金山,CA: Morgan Kaufmann, 1997, ISBN: 1558603484

教學大綱

The field of distributed algorithms has become a well-developed research area over the past 25 years. Its results appear in specialized research conferences such as PODC (Principles Of Distributed Computing) and DISC (International Symposium on Distributed Computing), and in general conferences involving distributed computing.

在過去25年來,分散式演算法已經成為充分發展的研究領域。它的成果展現於一些特定的學術會議,就如PODC (分散式運算法則) 和 DISC (分散式運算國際座談會),以及涵蓋分散式運算的一般研討會。

Distributed algorithms researchers define models for various kinds of distributed computing environments, define problems to be solved in those environments, including performance and fault-tolerance requirements, design new distributed algorithms to solve these problems, and analyze the correctness and performance of these algorithms. They also sometimes prove lower bounds and other impossibility results, which explain why certain tasks cannot be carried out in certain kinds of distributed settings, or cannot be carried out within certain cost constraints. Researchers typically study problems that arise in practical distributed systems, including problems of communication, data management, resource management, synchronization, and distributed agreement.

分散式演算法的研究,定義了不同種類分散式運算環境的模型,也定義了在那樣的環境下所需要解決的問題。包括效能和容錯需求;設計新的分散式演算法以解決這些問題;還有分析這些演算法的正確性和效能。它們有時也顯示較低界限和其他不可能的結果,說明了為什麼某些行程在一些分散式設定裡無法被完成,或是在某些成本限制下,不能被完成。研究人員典型地研究在實際分散式系統出現的問題,包括︰通訊問題、資料管理、資源管理、同步以及分散式協定。

Because distributed computing theory is a branch of theoretical computer science, the work is supposed to be mathematically rigorous; however, you will find that preliminary papers in this area are often written somewhat informally.

由於分散式運算理論是一門電腦科學理論的分支,它進行的工作被認定為如數學般高度嚴謹的;然而,你將發現在此領域的初步報告,常是被以不很正式的方式書寫的。

6.852J is a graduate-level course that is intended to do two things:

6.852J 是一門研究所程度的課程,它將進行以下兩件工作︰

1. Provide an introduction to the most important basic results in the area of distributed algorithms.

1. 提供對分散式演算法領域中最重要之基本成果的介紹

2. Prepare interested students to begin independent research or take a more advanced course in distributed algorithms.

2. 協助有興趣的學生開始進行獨立研究,或修習更多分散式演算法的進階課程

Usually, the students who take the course are a mixture of PhD students and MEng students. The course is run at a graduate level, which means that most MEng students will probably find it challenging (and time-consuming).

通常,修習這門課的學生是混和了博士研究生和工程系學生。這是研究所的課程,這表示大部份的工程系的學生,也許將發現這門課很具挑戰性(費時的)。

修課條件

To take 6.852J, you should have:

修習本課程,你應該先具有︰

"Mathematical maturity". In particular, you should be very good at reading and writing mathematical proofs.

「具有相當的數學程度」。尤其,你應該具備對數學證明有良好的理解和作題能力

General knowledge about some distributed systems. For instance, MIT’s undergraduate course 6.033: Computer Systems Engineering, would be good background.

對分散式系統具備基本的知識。舉例而言,麻省理工學院的大學課程 6.033︰計算機系統工程, 會是好的基礎背景

Experience with sequential algorithms and their analysis. MIT’s undergraduate course 6.046J: Introduction to Algorithms, is sufficient.

對循序演算法和它的分析有相當經驗。麻省理工學院的大學課程 6.046J︰演算法介紹,是足夠的

Experience with formal models of computation. MIT’s course 6.045J: Automata, Computability, and Complexity, on automata theory would be fine for this. (Desirable, but not essential.)

具有正式模式的運算的經驗。麻省理工學院課程 6.045J︰在自動機械裝置理論中的自動機械裝置,可運算度以及複雜度,將對本門課有幫助。(建議課程,但非必要)

資料來源

The main source will be the book:

主要資料將來自書本:

Lynch, Nancy A. Distributed Algorithms. San Francisco, CA: Morgan Kaufmann, 1997. ISBN: 1558603484.

Lynch, Nancy A.《分散式演算法》,San Francisco, CA: Morgan Kaufmann, 1997. ISBN: 1558603484.

The book refers to many papers from the research literature on distributed algorithms; you might want to track down and read some of these.

本書提到很多來自分散式演算法研究文獻中的論文;你可能想追溯以及閱讀某些內容

Other books that you will find useful are:

其它你將會發現有用的書有︰

Attiya, Hagit, and Jennifer Welch. Distributed Computing: Fundamentals, Simulations, and Advanced Topics. 2nd ed. Hoboken, NJ: Wiley, 2004. ISBN: 0471453242.

Attiya, Hagit, 以及 Jennifer Welch. 《分散式運算︰基礎,模擬和進階主題》,第二版. Hoboken, NJ: Wiley, 2004. ISBN: 0471453242.

This is another textbook on distributed algorithms, initially published a little after the Lynch book. It now has a second edition. The material covered overlaps quite a lot with the Lynch book, though Attiya and Welch do cover some topics, like clock synchronization, that Lynch doesn’t cover. The style of Attiya and Welch’s book is less formal.

這是另外一本分散式演算法的教科書,一開始在Lynch書的稍後出版。它現在有第二版。內容涵蓋許多和Lynch的書重複的材料。雖然Attuya和Welch也涵概部份Lynch所沒有提到的主題,像時脈同步。Attiya和Welch之書的風格是較不正式。

Dolev, Shlomi. Self-Stabilization. Cambridge, MA: MIT Press, 2000. ISBN: 0262041782.

Dolev, Shlomi.《自穩定性》,Cambridge, MA: 麻省理工學院發行, 2000. ISBN: 0262041782.

This gives a good description of self-stabilizing distributed algorithms. Self-stabilization is one kind of fault-tolerance, which we will study near the end of the course.

這本書對分散式演算法之自穩定性有良好的闡述。自穩定性是容錯的一種,我們在課程結尾將會學習

In addition, some research papers that are not covered in the textbook will be covered in class and on problem sets. They will cover a variety of topics, for example, computability and relative computability results for different kinds of objects and services, in the presence of various numbers of failures. These papers are listed in the readings section.

除此之外,某些沒有被涵蓋在教科書裡的研究論文,將被包括在課堂上和問題集裡。它將包括不同的主題。例如,可運算度和針對不同物件及服務相關聯的可運算度結果,在不同次數之失敗當中的呈現。這些報告被列在「閱讀部份」裡

課程需求

Readings

閱讀

Readings that cover the material for each class will be announced ahead of time. For most classes, these will be sections from the textbook. For some classes, however, these will be research papers from the reading list in the readings section. Reading a research paper will generally take more time than reading sections from the textbook – so be prepared to put in the extra time.

每節課將涵蓋的閱讀內容將提前公布。就大部份的課程而言,這些都會在教科書的部份裡。然而,針對部份課程來說,這些將會是閱讀部份中之閱讀清單裡的研究論文。閱讀一份研究論文通常會比閱讀教科書耗費更多時間 – 所以請對佔用額外時間有所準備

We expect students to read the assigned material ahead of time, and to come to class prepared with questions and discussion ideas.

我們期待學生能預先閱讀所指定的材料,並且來上課時準備好問題和討論的想法

Problem Sets

問題集

These are intended to help you to understand the material being covered in class. Most problems will involve thinking about algorithms and problems already covered in class; some will be designed to get you started thinking about ideas to be discussed in later classes.

這些是想幫助你理解課程所涵蓋之內容的。大部份的問題將加入思考演算法和課程所涵蓋的問題裡;某些問題將被設計成讓你開始思考後面的課程將要討論的想法.

Specifically, approximately five problems will be given out approximately every Thursday. The problems will be batched and due every two weeks, at the beginning of class on alternate Thursdays. There will be a total of seven problem set due dates. No late homeworks will be accepted. If you haven’t finished, just hand in what you have completed. However, in case of a serious emergency, please talk to either the Teaching Assistant or Prof. Lynch.

特別是,大概在每週的星期四,會公布大約五個問題題目,這些問題將於每兩週之後截止,在另一個星期四課程開始時回收。將會有一次七個問題集的總截止日。不接受遲交的作業。如果你還有未完成的習題,就繳交你完成的部份。然而,考慮到一些緊急的情況,請預先告知和聯絡助教或Lynch教授.

Homework is an important part of your grade. When grading homework problems, we will try to give full credit to solutions that include all the important logical steps and ideas. We consider it a minus for a write up to be lengthy and overly detailed. An exception is when we specifically ask for details, for instance, in formal proofs of correctness of algorithms.

作業是你成績很重要的一部份。當對作業問題評分時,我們會偏好給包括所有重要的邏輯步驟和想法的解決方案滿分。我們會對冗長和過多細節的作法加以扣分。

除非我們有特別要求提供細節的解答,舉例來說,以正式的證明演算法的正確性

Solutions to homework problems will be handed out. Whenever possible, the best student solution will be used. Students who would like us to use their write ups can help us by writing elegant and concise solutions and formatting them using LaTeX (and the LaTeX style files provided by us). When you submit the homework, keep the .tex file since it may need to be edited if your solution is chosen. Problem sets will be graded by teams of students in the class, led by the Teaching Assistant and/or Prof. Lynch.

會分發作業的解答。不論何時有可能,最好的學生解題方案會被採用。希望我們使用它們作法的學生,可以藉由寫出優雅和簡明的解題方案以及使用LaTeX格式化來協助我們。(且我們提供LaTeX格式)。當你繳交作業,保留 .tex檔,因為它可能在如果你的解法被選中時,需要被編輯。問題集將被以課堂學生的組別單位來評分,由教授Lynch或是助教引導

We will have software available to assist you in writing syntactically-correct distributed algorithms. This software consists of the TIOA language processor, which allows specification of algorithms as interacting state machines, possibly with timing constraints. Information about how to download the software and how to get started using it will be provided in a tutorial handout about three weeks after the term begins. We hope that you will find the software helpful. We are not absolutely requiring you to use it, but we prefer that you do so. (It should help ensure that your programs make some sense, and will certainly make the graders’ jobs a lot easier.)

我們會有軟體協助你寫出語意上正確的分散式演算法。這套軟體由TIOA語言處理,它使得演算法的規格像互動的機器,但可能有時間限制。開課後的三個禮拜,分發的教學手冊會提供下載該軟體及如何使用的說明。我們希望你發現這個軟體對你很有幫助。我們並不強制性要求你使用它,但建議你這麼做。(它將協助去確保你的程式有意義,且會令評分者的工作相對簡單)

Policy on homework collaboration: You are strongly encouraged to discuss possible solutions with other class members. Many students in past incarnations of this course have formed homework discussion groups. However, you must always write up the solutions entirely on your own.

作業合作措施:你將被強烈鼓勵和其他課堂成員討論可能的解法。以往有很多這門課的學生會組成作業討論小組。然而,你總是必須自行寫出所有的解答

Problem Set Grading

問題集的評分

For each problem set, a group of 3-4 students will be responsible for working with the course staff to grade the solutions. If possible, we would like the grading to be completed by the Monday afternoon after the homeworks are handed in, so we can record the grades and hand them back on Tuesday. The number of times you have to grade over the course of the semester will depend on the size of the class. Part of your grade will depend on the quality and promptness of your work on problem set grading.

針對每個問題集,每組有三到四個學生需要負責解答以便使課程教師和助教能對該解題方案評分。如果可能,我們希望能在作業繳交後的星期一下午完成評分,如此一來我們能登記分數並在星期四時將它們還給學生。學期的課程中,你必須被評分的次數將依據修課人數多寡而定。你的部份成績將依據你在問題集裡的品質和敏銳來評定

Exams

考試

There will be no exams. No midterm, no final.

將沒有測驗、期中考和期末考

Course Grade Calculation

課程評分計算

Your course grade will be based on problem set grades, problem set grading grades, and class participation. Here is how your grade will be calculated:

你的課程總成績將會根據問題集的評分,問題集的總成績,以及課程參與表現。這裡說明了你的成績將如何被計算

ACTIVITIES PERCENTAGES

活動 百分比

Seven Problem

Sets (10% each) 70%

七個問題集 70%

( 每個10% )

Class Participation

(Attendance, Quality

and Quantity of

Participation) 20%

課程參與表現 20%

(出席, 品質

和參與次數)

Grading (Quality

and Promptness) 10%

評分 10%

(品質和敏銳)

教學時程,相關閱讀資料

A breakdown of supplementary readings per topic follows the session wise listing of reading assignments in the table below.

每個主題有分成數份的輔助閱讀資料,配合課程之閱讀作業進度表列如下

Unless otherwise noted, reading assignments are from the course text:

除非另有註明,閱讀作業來自課程教科書︰

Lynch, Nancy A. Distributed Algorithms. San Francisco, CA: Morgan Kaufmann, 1997. ISBN: 1558603484.

Lynch, Nancy A. 《分散式演算法》,舊金山, CA: Morgan Kaufmann, 1997. ISBN 1558603484

課 課程單元 閱讀資料

1 Course Overview Chapter 1, 2 (Skim)

課程概要 第一、二章(略讀)

Synchronous Networks Chapter 3, sections 3.1 – 3.4

同步網路 第三章, 第3.1-3.4節

Leader Election in

Synchronous Ring Networks

在同步環狀

網路的主要選擇

2 Basic Computational Tasks

in Synchronous Networks:

Leader Election Chapter 3, sections 3.1 – 3.6

基礎運算行程在同步 第三章,3.1-3.6節

網路︰主要選擇

Breadth-first Search

橫向優先搜尋

Shortest Paths

散佈路徑

Broadcast and Convergecast

散佈和收斂

3 Breadth-first Search (cont.) Chapter 4, sections 4.1 – 4.4

橫向優先搜尋(繼續) 第四章,第4.1-4.4節

Shortest Paths (cont.)

最短路徑(繼續)

Broadcast and

Convergecast (cont.)

散佈和收斂(繼續)

Spanning Trees

生成樹

Minimum Spanning

Trees

最小生成樹

4 Fault-tolerant Consensus Chapter 5, section 5.1

容錯共識,第五章,第5.1節

Link Failures: The Two

Generals Problem Chapter 6, sections 6.1, 6.2

連結失敗︰兩個一般性,第六章,第6.1、6.2節

問題

Process Failures Lamport, L., M. Pease, and R.

(Stopping, Byzantine) Shostak. "The Albanian Generals

行程失敗(暫停, Byzantine Problem." Technical Report CSL-97,

failures) SRI International Computer

Science Laboratory, August 22, 1979.

Lamport, L., M. Pease 和

R. Shostak.〈阿拉巴馬一

般性問題〉《技術性報告

CSL-97》,SRI 國際電腦科學

實驗室, 1979年8月22日

Algorithms for Agreement

with Stopping Failures

針對與停用失敗,協議演

算法

5 Exponential Information

Gathering Chapter 6, sections 6.2, 6.7

指數資訊收集 第六章,第6.2、6.7節

作業1截止

Algorithms for Agreement

with Byzantine Failures

針對不預期錯誤

協定演算法

6 Number-of-processes Lower

Bounds for Byzantine

Agreement Chapter 6, sections 6.3 – 6.6

針對不預期錯誤 第六章,第6.3-6.6節

行程數量的下界

Aguilera, Marcos Kawazoe, and

Sam Toueg. "A simple bivalency

proof that t-resilient consensus

requires t+1 rounds." Information

Processing Letters 71, no. 3-4

(August 1999): 155-158.

Aguilera, Marcos Kawazoe, 和

Sam Toueg. 〈一個簡單的二原子價

證明 t-彈性函數共識需要t+1 回〉

《資訊處理過程信件》71, no. 3-4(1999年8月)

155-158

Weak Byzantine Agreement

弱化拜占庭協議

Time Bounds for Consensus

Problems

共識問題的時限

7 Other Kinds of Consensus

Problems: $k$-agreement Chapter 7, sections 7.1 – 7.3

其它種類共識問題:$k$- (skip 7.3.4)

協議 第七章,第7.1-7.3節(略過7.3.4)

Approximate Agreement

近似協議

Distributed Commit

分散式交付

8 Asynchronous Distributed

Computing Chapter 7, section 7.3

非同部分散式運算 第七章,第7.3節

Formal Modeling of

Asynchronous Systems

using I/O Automata Chapter 8

非同步系統使用輸出入自動機 第八章

械裝置正規模式

9 Proof Methods

證明方法

Non-fault-tolerant

Algorithms for Asynchronous

Networks Chapter 8, sections 8.2 – 8.5

針對非同步網路無容錯 第八章

演算法 Chapter 14 and 15

第十四和十五章

作業2截止

Leader Election, Breadth-first

Search, Shortest Paths,

Broadcast and Convergecast

主要選擇,橫向優先搜尋,

最短路徑, 散佈和收斂

10 Non-fault-tolerant Algorithms

for Asynchronous Networks

(cont.) Chapter 15, sections 15.3 – 15.4

針對非同步網路無容錯 第十五章,第15.3-15.4節

演算法(繼續)

Leader Election, Breadth-first

Search, Shortest Paths,

Broadcast and Convergecast

(cont.)

主要選擇,橫向優先搜尋,

最短路徑,散佈和收斂(繼續)

11 Spanning Trees Chapter 15, sections 15.4, 15.5

生成樹 第十五章,第15.4、15.5節

Gallager et al. Minimum

Spanning Tree Algorithm

Gallager 等人,最小生成樹

演算法

12 Synchronizers Chapter 16

同步控制器 第十六章

作業3截止

13 Synchronizer Applications Chapter 16, section 16.6

同步控制應用程式 第16章,第16.6節

Time, Clocks, and the

Ordering of Events Chapter 18

時間,計時,和事件順序 第18章

Vector Timestamps Lamport, Leslie. "Time, Clocks and

向量時戳 the Ordering of Events in a

Distributed System." Communications

of the ACM 21, no. 7 (July 1978):

558-565.

Lamport, Leslie.〈在分散式系統裡

時間,計時以及事件順序〉,ACM

通訊21, no. 7 (1978年7月)︰第558-565頁

14 State-machine Simulation Mattern, Friedemann. "Virtual time

狀態機器 模擬 and global states of distributed

systems." In Parallel and Distributed

Synchronous vs. Asynchronous Algorithms: Proceedings of the

Distributed Systems International Workshop on Parallel

同步 對比 非同步分散式系統 and Distributed Algorithms. Edited by

Michel Cosnard et al. Gers, France:

Chateau de Bonas, October 1988: pp.

215-226. North Holland, 1989.

(Reprinted in: Yang, Z., and T. A.

Marsland, eds. "Global States and

Time in Distributed Systems."

IEEE (1994): 123-133.)

Mattern, Friedemann.〈分散式系統虛擬時間

和全域狀態〉《在平行和分散式演算法︰

國際平行和分散式演算法工作小組會議記錄》

由 Michel Cosnard 等人 Gers, 法國︰

Chateau de Bonas, 十月 1988: pp.

215-226. 北荷蘭, 1989. (在 Yang, Z.,

和 T.A. Marsland, eds重印.〈在分散式

系統全域和時間〉,IEEE (1994)︰第123-133頁

第十九章

Stable Property Detection

穩定屬性偵測

Distributed Termination

分散式停止

Global Snapshots

全域映攝

Deadlock Detection

死結針測

Asynchronous Shared-memory

Systems

非同步分享記憶體系統

15 Mutual Exclusion Chapter 9

彼此互斥 第九章

Mutual Exclusion

Algorithms Chapter 10, sections 10.1 – 10.5

互斥演算法 第10章, 第10.1-10.5節

16 Mutual Exclusion

Algorithms (cont.) Chapter 10, sections 10.5 – 10.8

互斥演算法(繼續) 第十章, 第10.5-10-8節

作業4截止

17 Bounds on Shared-memory

for Mutual Exclusion Chapter 10, sections 10.8 – 10.9

針對彼此互斥分享記憶 第十章, 第10.8-10.9節

體界限

Chapter 11 (Skim)

第十一節(略讀)

18 Impossibility of Consensus in

Asynchronous, Fault-prone,

Shared-memory Systems Chapter 12

在非同步,錯誤頃向,分享記 第十二章

憶體中不可能性的共識

Chapter 13, section 13.1

第十三章,第13.1節

19 Atomic Objects Chapter 13

極微物件 第十三章

Atomic Snapshot

Algorithms

原子映射演算法

20 Atomic Read/Write Register

Algorithms Chapter 13

讀寫 原子註冊演算法 第十三章

Wait-free Computability

不用等待可計算性 Herlihy, Maurice. "Wait-free

synchronization." ACM Transactions

on Programming Languages and Systems

13, no. 1 (January 1991): 124-149.

Herlihy, Maurice.〈同步無須等待〉,《程式

語言和系統的ACM會報》13, no.1

(1991年1月)︰第124-149頁

作業5截止

The Wait-free Consensus

Hierarchy

無須等待共識層級

21 The Wait-free Consensus

Hierarchy (cont.)

無須等待 共識階層(繼續)

Herlihy, Maurice. "Wait-free

synchronization." ACM Transactions

on Programming Languages and Systems

13, no. 1 (January 1991): 124-149

Herlihy, Maurice. 〈同步無須等待〉,《程式

語言和系統的ACM會報》13, no.1

(1991年1月)︰第124-149頁

Jayanti, Prasad. "Robust wait-free

hierarchies." Journal of the ACM 44,

no. 4 (1997): 592-614. (Skim)

Jayanti, Prasad. 〈強仞無須等待層級〉《ACM

期刊》44, no. 4(1997年)︰第592-614頁(略讀)

———. "Wait-free computing." In

Distributed Algorithms, 9th

International Workshop, WDAG ’95, Le

Mont-Saint-Michel, France, September

13-15, 1995, Proceedings. Edited by

Jean-Michel H??lary, and Michel Raynal.

Volume 972 of Lecture Notes in

Computer Science, Springer 1995.

ISBN: 3540602747.

— 〈無須等待運算〉在《分散式演算法》,第

九次國際工作小組, WDAG 95′, Le Mont-

Saint-Michel, 法國, 1995年9月13-15日,

會議記錄. 由 Jean-Michel Helary, 和

Michel Raynal 編輯.「電腦科學課程記要

第972卷」, 1995年春.

ISBN:3540602747

22 Wait-free vs.

$f$-fault-tolerant

Atomic Objects Borowsky, Elizabeth, Eli Gafni, Nancy

無須等待 對比 Lynch, and Sergio Rajsbaum. "The BG

$f$- 極微物件 容錯 distributed simulation algorithm."

Distributed Computing 14 (2001):

127-146.

Brorwsky, Elizabeth, Eli Gafni,

Nancy Lynch, 和 Sergio Rajsbaum.

〈BG分散式模擬演算法〉《分散式運算 14》

(2001): 127-146

23 Asynchronous Network Model

vs. Asynchronous

Shared-memory Model Chapter 17, 21

非同步網路模式 對比 第17, 21章

非同步分享記憶體模式 作業6截止

Impossibility of Consensus

in Asynchronous Networks

非同步網路裡的不可能性

共識

Failure Detectors and

Consensus

失敗偵測和共識

24 Paxos Consensus Algorithm Lamport, L. "The part-time parliament." Paxos 共識演算法 ACM Transactions on Computer Systems

16, no. 2 (May 1998): 133-169. Also

Research Report 49, Digital Equipment

Corporation Systems Research Center,

Palo Alto, CA, September 1989.

Lamport, L. 〈部份時間議會〉《電腦系統的

ACM會報》16, no. 2(1998年5月)︰第133-169頁.

亦見《研究報告》49, 數位配備公司系統研究

中心, Palo Alto, CA, 1989年9月.

Reliable Communication using

Unreliable Channels Chapter 22

可信賴通訊使用不可信賴頻道 第二十二章

25 Reliable Communication using

Unreliable Channels (cont.) Chapter 22

使用不可信賴頻道的可信 第二十二章

賴通訊(繼續)

Dijkstra’s self-stabilization paper

(PDF)

Dijkstra的自我穩定報告(PDF)

Dolev, Shlomi. Self-Stabilization.

Cambridge, MA: MIT Press, 2000,

chapter 2. ISBN: 0262041782.

Dolev, Sholmi. 《自我穩定》,劍橋, MA:

MIT出版, 2000年, 第二章.

ISBN: 0262041782

Self-stabilizing Algorithms

自我穩定演算法

26 Atomic Memory Algorithms for

Dynamic Networks

動態網路的極微記憶演算法 Lynch, Nancy, and Alex Shvartsman.

"Rambo: A reconfigurable atomic

memory service for dynamic networks."

Rambo Technical Report MIT-LCS-TR-856. MIT

Rambo Laboratory for Computer Science,

Cambridge, MA, 2002.

Lynch, Nancy, 和 Alex Shvartsman.

〈Rambo: 針對動態網路可重設極微記

憶體服務〉《技術報告 MIT-LCS-TR-856》

MIT電腦科學實驗室, 劍橋, MA, 2002年.

Gilbert, Seth, Nancy Lynch, and Alex

Shvartsman. "RAMBO II: Rapidly

reconfigurable atomic memory for

dynamic networks." Proceedings of the

International Conference on Dependable Systems and Networks (DSN) (June

22nd-25th, 2003): 259-268. San

Francisco, CA. Also, Technical Report

MIT-LCS-TR-890, MIT CSAIL, Cambridge,

MA, 2004.

Gilbert, Seth, Nancy Lynch, 和 Alex

Shvartsman. 〈RAMBO II: 針對動態網路

快速重設的極微記憶〉《國際會議可信賴

系統和網路(DSN)(2003年6月22-24日)

會議記錄》︰第259-268頁. 舊金山, CA. 亦見

《技術報告 MIT-LCS-TR-890》,MIT CSAIL,

劍橋, MA, 2004年

作業7截止

輔助閱讀清單

Other General Distributed Algorithms Textbooks

其它一般分散式演算法教科書

Attiya, Hagit, and Jennifer Welch. Distributed Computing: Fundamentals, Simulations, and Advanced Topics. New York, NY: Wiley-Interscience, 2004. ISBN: 0471453242.

Attiya, Hagit, 和 Jennifer Welch. 《分散式運算︰基礎、模擬和進階主題》,紐約, NY:

Wiley-Interscience, 2004年. ISBN: 0471453242.

The Number of Rounds Required for Consensus

共識需要的數量回合

Aguilera, Marcos Kawazoe, and Sam Toueg. "A simple bivalency proof that t-resilient consensus requires t+1 rounds." Information Processing Letters 71, no. 3-4 (August 1999): 155-158.

Aguilera, Macros Kawazoe, 和 Sam Toueg. 〈一個簡單二原子價 證明 t-彈性函數共識需要t+1回〉《資訊處理信》71, no. 3-4 (1999年8月)︰第155-158頁

Keidar, Idit, and Sergio Rajsbaum. "On the cost of fault-tolerant consensus when there are no faults – a tutorial." Technical Report MIT-LCS-TR-821 (May 2001). Preliminary version in: "Distributed Computing column." SIGACT News 32, no. 2 (June 2001): 45-63. (Published in May 15th.)

Keidar, Idit, 和 Sergio Rajsbaum. 〈當沒有錯誤時的容錯共識成本 – 一份導讀〉《技

術報告MIT-LCS-TR-821》(2001年5月),初步版本在:〈分散式運算專欄〉《SIGACT報導》32, no. 2(2001年3月):第45-63頁. (5月15日出版)

Minimum Spanning Tree Protocol

最小生成數協定

Gallager, R. G., P. A. Humblet, and P. M. Spira. "A distributed algorithm for minimum-weight spanning trees." ACM Trans Programming Language Syst 5 (1983): 66-77.

Gallager, R.G., P. A. Humblet, 和 P. M. Spira.〈針對最小重量生成樹的一個分散式演算法〉《程式語言和系統的ACM會報》5(1983年)︰第66-77頁

Vector TimeStamps

向量時間戳記

Mattern, Friedemann. "Virtual time and global states of distributed systems." In Parallel and Distributed Algorithms: Proceedings of the International Workshop on Parallel and Distributed Algorithms. Edited by Michel Cosnard et al. Gers, France: Chateau de Bonas, October 1988: pp. 215-226. North Holland, 1989. (Reprinted in: Yang, Z., and T. A. Marsland, eds. "Global States and Time in Distributed Systems." IEEE (1994): 123-133.)

Mattern, Friedemann. 〈分散式系統的虛擬時間和全域狀態〉在《平行和分散式演算法︰平行和分散式演算法上的國際工作小組會議記錄》由Michel Cosnard 等人編輯. Ger, 法國: Chateau de Bonas, 1988年10月︰第215-226頁. 北荷蘭, 1989年. (重印︰Yang, Z., 和 T.A. Marsland, eds. 〈分散式系統裡的全域和計時〉,IEEE (1994年)︰第123-133頁)

Fidge, Colin. "Logical time in distributed computing systems." IEEE Computer 24, no. 8 (August 1991): 28-33.

Fidge, Colin. 〈在分散式運算系統的邏輯時間〉,IEEE電腦24, no. 8 (1991年8月): 第28-33頁

Impossibility of Consensus

不可能性共識

Fischer, Michael J., Nancy A. Lynch, and Michael S. Paterson. "Impossibility of Distributed Consensus with One Faulty Process." Journal of the ACM 32, no. 2 (April 1985): 374-382.

Fischer, Michael J., Nancy A. Lynch, 和 Michael S. Paterson.〈以一個有錯誤行程分散式共識的不可能性〉《ACM期刊》32, no. 2 (1985年4月)︰第374-382頁

Chaudhuri, Soma. "More Choices Allow More Faults: Set Consensus Problems in Totally Asynchronous Systems." Information and Computation 105, no. 1 (July 1993): 132-158.

Chaudhuri, Soma. 〈更多選擇產生更多錯誤︰在全部不同步系統集合共識問題〉《資訊和運算》105, no. 1 (1993年7月)︰第132-158頁

Wait-free Computability and the Wait-free Consensus Hierarchy

無須等待可運算和無須等待共識層級

Herlihy, Maurice. "Wait-free synchronization." ACM Transactions on Programming Languages and Systems 13, no. 1 (January 1991): 124-149.

Herlihy, Maurice. 〈無須等待同步化〉在《程式語言和系統的ACM會報》13, no.1(1991年1月)︰第124-149頁

Jayanti, Prasad. "Robust wait-free hierarchies." Journal of the ACM 44, no. 4 (1997): 592-614.

Jayanti, Prasad. 〈強韌性無須等待層級〉《ACM期刊》44, no. 4(1997): 592-614

———. "Wait-free computing." In Distributed Algorithms, 9th International Workshop, WDAG ’95, Le Mont-Saint-Michel, France, September 13-15, 1995, Proceedings. Edited by Jean-Michel H??lary, and Michel Raynal. Volume 972 of Lecture Notes in Computer Science, Springer 1995. ISBN: 3540602747.

—–.〈無須等待運算〉在《分散式演算法》,第九次國際工作小組, WDAG ’95, Le Mont-Saint-Michel, 法國, 1995年9月13-15日, 會議記錄. 由Jean-Michel Helary 編輯, 和 Michel raynal.在「電腦科學課程要點」卷 972, 1995年春. ISBN: 3540602747.

Lo, Wai-Kau, and Vassos Hadzilacos. "All of us are smarter than any of us: nondeterministic wait-free hierarchies are not robust." SIAM Journal on Computing 30, no. 3 (2001): 689-728.

Lo, Wai-Kau, 和 Vassos Hadzilacos. 〈我們加起來比我們中的任何一位聰明︰非決定論無須等待層級並不強韌〉在《SIAM 運算期刊》30, no. 3(2001年)︰第689-728頁

Wait-free vs. f-fault-tolerant Data Objects

無須等待對比f-容錯資料物件

Chandra, T. D., V. Hadzilacos, P. Jayanti, and S. Toueg. "Wait-freedom vs. t-resiliency and the robustness of the hrm hierarchy." Proceedings of the 13th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing. Los Angeles, CA, August 1994, pp. 334-343,

Chandra, T.D. , V. Hadzilacos, P. Jayanti, 和 S. Toueg. 〈無須等待對比 t-彈性函數 和 m進位h的r次方 的強韌度層級〉《第13屆分散式運算法則上的 ACM SIGACT-SIGOPS 座談會會議記錄》,落山磯, CA, 1994年8月,第334-343頁

———. "Generalized irreducibility of consensus and the equivalence of t-resilient and wait-free implementations of consensus." To appear in SIAM Journal on Computing.

—–. 〈一般不可縮減共識和 t-彈性函數對等以及無須等待共識的實作〉出現在《SIAM運算期刊》

Borowsky, Elizabeth, Eli Gafni, Nancy Lynch, and Sergio Rajsbaum. "The BG distributed simulation algorithm." Distributed Computing 14 (2001): 127-146.

Borowsky, elizabeth, Eli Gafni, Nancy Lynch, 和 Sergio Rajsbaum. 〈BG分散式模擬演算法〉《分散式運算》14(2001年)︰第127-146頁

Lo, W. K., and V. Hadzilacos. "On the power of shared object types to implement one-resilient consensus." Distributed Computing 13, no. 4 (2000): 219-238.

Lo, W. K., 和 V. Hadzilacos. 〈論分享物件形態的威力對單一彈性共識的執行〉《分散式運算》13, no. 4 (2000年)︰第219-238頁

Attie, Paul, Rachid Guerraoui, Petr Kouznetsov, Nancy Lynch, and Sergio Rajsbaum. "Impossibility of boosting distributed service resilience." Technical Report MIT-LCS-TR-982, MIT CSAIL, Cambridge, MA, February 2005.

Attie, Paul, Rachid Guerraoui, Petr Kouznetsov, Nancy Lynch, 和 Sergio Rajsbaum. 〈推動分散式服務彈性的不可能性〉《MIT-LCS-TR-982技術報告》, MIT CSAIL, 劍橋, MA, 2005年2月.

Reliable Broadcast

可信賴散佈

Hadzilacos, Vassos, and Sam Toueg. "Fault-tolerant broadcasts and related problems." In Distributed Systems. 2nd ed. Edited by Sape Mullender. Reading, MA: ACM Press and Addison-Wesley, 1993, chapter 5, pp. 97-145. ISBN: 0201624273.

Hadzilacos, Vassos, 和 Sam Toueg. 〈容錯散佈和相關問題〉在《分散式系統》,第二版. 由 Sape Mullender 編輯, MA: ACM出版社 和 Addison-Wesley, 1993年, 第五章, 第97-145頁. ISBN: 0201624273.

———. "A modular approach to the specification and implementation of fault-tolerant broadcasts." Technical Report TR94-1425. Ithaca NY: Cornell University, Department of Computer Science, May 1994.

_____.〈一個模組化方式到規格和容錯散佈實作〉《TR94-1425技術報告》,Ithaca NY: 康乃爾大學, 電腦科學部門, 1994年5月.

Failure Detectors and Consensus

錯誤針測和共識

Chandra, Tushar Deepak, and Sam Toueg. "Unreliable failure detectors for reliable distributed systems." Journal of the ACM 43, no. 2 (March 1996): 225-267.

Chandra, Tushar Deepak, 和 Sam Toueg. 〈針對分散式系統不可信賴失敗偵測〉《ACM期刊》43, no. 4(1996年7月)︰第685-722頁

Gafni, Eli. "A Round-by-Round Failure Detector – Unifying Synchrony and Asynchrony." Proceedings of the 17th Annual ACM Symposium on Principles of Distributed Computing. Puerto Vallarta, Mexico, June 1998, pp. 143-152.

Gafni, Eli. 〈回合制錯誤偵測 – 統合同步和非同步〉《ACM分散式原則座談會第17屆年度會議記錄》,Puerto Vallarta, 墨西哥, 六月 1998, pp. 143-152.

Lamport, L. "The part-time parliament." ACM Transactions on Computer Systems 16, no. 2 (May 1998): 133-169. Also Research Report 49, Digital Equipment Corporation Systems Research Center, Palo Alto, CA, September 1989.

Lamport, L. 〈兼職議會〉《ACM電腦系統會報》16, no. 2 (1998年5月)︰第133-169頁. 亦見《研究報告》 49,數位配備公司系統研究中心, Palo Alto, CA, 1989年9月.

Self-stabilization

自我穩定

Dijkstra, Edsger W. "Self-stabilizing systems in spite of distributed control." Communications of the ACM 17, no. 11 (November 1974): 643-644.

Dijkstra, Edsger W.〈排除分散式控制的自我穩定系統〉《ACM通訊》17, no. 11(1974年11月)︰第643-644頁

Dolev, Shlomi. Self-Stabilization. Cambridge, MA: MIT Press, 2000. ISBN: 0262041782.

Dolev, Shlomi. 《自我穩定》,劍橋, MA: MIT出版, 2000年. ISBN: 0262041782.

Clock Synchronization

計時同步

Attiya, Hagit, and Jennifer Welch. Distributed Computing: Fundamentals, Simulations, and Advanced Topics. New York, NY: Wiley-Interscience, 2004. ISBN: 0471453242.

Attiya, Hagit, 和 Jennifer Welch. 《分散式運算︰基礎、模擬和進階主題》,紐約, NY:Wiley-Interscience, 2004年. ISBN: 0471453242.

Fan, Rui, and Nancy Lynch. "Gradient Clock Synchronization." Proceedings of the Twenty-third Annual ACM PODC. St. Johns, Newfoundland, Canada, July 2004.

Fan, Rui, 和 Nancy Lynch. 〈梯度計時同步〉《第二十三屆年度ACM PODC會議記錄》. St. Johns, Newfoundland, 加拿大, 2004年7月

Dynamic Distributed Algorithms

動態分散式演算法

Lynch, Nancy, and Alex Shvartsman. "Rambo: A reconfigurable atomic memory service for dynamic networks." Technical Report MIT-LCS-TR-856. Cambridge, MA: MIT Laboratory for Computer Science, 2002.

Lynch, Nancy, 和 Alex Shvartsman. 〈Rambo︰針對動態網路可重設極微記憶體服務〉《MIT-LCS-TR-856技術報告》,劍橋, MA: MIT 電腦科學實驗室, 2002年

Gilbert, Seth, Nancy Lynch, and Alex Shvartsman. "RAMBO II: Rapidly reconfigurable atomic memory for dynamic networks." Proceedings of the International Conference on Dependable Systems and Networks (DSN) (June 22nd-25th, 2003): 259-268. San Francisco, CA. Also, Technical Report MIT-LCS-TR-890, MIT CSAIL, Cambridge, MA, 2004.

Gilbert, Seth, Nancy Lynch, 和 Alex Shvartsman. 〈RAMBO II︰針對動態網路快速可重設極微記憶體〉《可信賴系統與網路(DSN)國際會議記錄》(2003年6月22-25日)︰第259-268頁. 舊金山, CA. 亦見《MIT-LCS-TR-890技術報告》,MIT CSAIL, 劍橋, MA, 2004年

Dolev, Shlomi, Seth Gilbert, Nancy Lynch, Alex Shvartsman, and Jennifer Welch. "GeoQuorums: Implementing atomic memory in ad hoc networks." Technical Report MIT-LCS-TR-900a, MIT CSAIL, Cambridge, MA, 2004.

Dolev, Shlomi, Seth Gilbert, Nancy Lynch, Alex Shvartsman, 和 Jennifer Welch. 〈實際最低限度︰在點對點網路實作極微記憶體〉《MIT-LCS-TR-900a技術報告》,MIT CSAIL, 劍橋, MA, 2004年

Dolev, Shlomi, Seth Gilbert, Nancy A. Lynch, Elad Schiller, Alex A. Shvartsman, and Jennifer L. Welch. "Virtual Mobile Nodes for Mobile Ad hoc Networks." Proceedings of the 18th International Conference on Distributed Computing (DISC), October 2004.

Dolev, Shlomi, Seth Gilbert, Nancy A. Lynch, Elad Schiller, Alex A. Shvartsman, 和 Jennifer L. Welch.〈針對行動點對點網路虛擬行動節點〉《分散式運算(DISC)第18次國際會議記錄》,2004年10月

Dolev, Shlomi, Seth Gilbert, Limor Lahiani, Nancy Lynch, and Tina Nolte. "Timed Virtual Stationary Automata for Mobile Networks." Technical Report MIT-LCS-TR-979a, MIT CSAIL, Cambridge, MA, August 2005.

Dolev, Shlomi, Seth Gilbert, Limor Lahiani, Nancy Lynch, 和 Tina Nolte. 〈針對行動網路計時虛擬常備自動機械裝置〉《MIT-LCS-TR-979a技術報告》,MIT CSAIL, 劍橋, MA, 2005年8月

Aspnes, James, Dana Angluin, Zoe Diamadi, Michael J. Fischer, and Rene Peralta. "Computation in networks of passively mobile finite-state sensors." Proceedings of the Twenty-Third ACM Symposium on Principles of Distributed Computing, July 2004, pp. 290-299. Accepted to Distributed Computing (PODC 2004 special issue), September 2004. Last revised May 2005.

Aspnes, James, Dana Angluin, Zoe Diamadi, Michael J. Ficher, 和 Rene Peralta. 〈在被動行動網路有限狀態 偵測運算〉《分散式系統(DISC)第二十三次ACM座談會會議記錄》,2004年7月, 第290-299頁. 被收入《分散式運算(PODC 2004年9月特殊議題)》,最新修訂2005年5月

課堂講稿

This section contains documents created from scanned original files, which are inaccessible to screen reader software. A ‘#’ symbol is used to denote such documents.

此部份包含從原始檔案掃描的文件,那些文件無法讓使用視窗的讀者使用. ‘#’ 的符號乃用來標明此類文件

This section contains the instructor’s notes that were used to structure the lectures from the Fall 2001 instance of this course. These notes are listed by the topics discussed in Fall 2001.

此部份包含授課教師從2001秋季,本課程開始用來架構課程的記錄。這些記錄是依2001秋季的討論主題而列出

課程單元 注釋

Course Overview

課程概要 (PDF – 1.1 MB)#

Synchronous Networks

同步網路

Leader Election in Synchronous

Ring Networks

同步網路裡的

主要選擇

Basic Computational Tasks in

General Synchronous Networks:

Leader Election

在一般同步網路裡的 (PDF – 1.0 MB)#

基儲運算行程:

主要選擇

Breadth-First Search

橫向優先搜尋

Shortest Paths, Broadcast

and Convergecast

最短路徑、散佈及收斂

Spanning Trees

延伸樹 (PDF – 1.2 MB)#

Minimum Spanning Trees

最小延伸樹

Fault-Tolerant Consensus

Problems

容錯共識問題 (PDF)#

Link Failures: The Two

Generals Problem

連結失敗︰兩個一般性問題

Process Failures (Stopping,

Byzantine)

行程失敗(停止、不預期)

Algorithms for Agreement with

Stopping and Byzantine

Failures

針對與停止和不預期錯誤

協議的演算法

Exponential Information

Gathering

等比資訊收集

Number-Of-Processor Bounds for

Byzantine Agreement

針對拜占庭協議的處理器數量 (PDF – 1.2 MB)#

界線

Weak Byzantine Agreement

弱化拜占庭協議

Time Bounds for Consensus

Problems

時間限制的共識問題

Other Kinds of Consensus

Problems: $k$-Agreement

其它種類共識問題 – (PDF)#

$k$(??)-協議

Approximate Agreement

近似協議

Distributed Commit

分散式交付

Asynchronous Distributed

Computing

非同步分散式運算 (PDF – 1.1 MB)#

Formal Modeling of Asynchronous

Systems Using Interacting State

Machines (I/O Automata)

非同步系統使用交互狀態主機的

正規模型(輸出/入自動機械)

Proof Methods

驗證法則

Asynchronous Message-Passing

Systems

非同步訊息傳送系統 (PDF – 1.2 MB)#

Modeling Asynchronous Message-

Passing Systems

模式化非同步訊息傳送系統

Basic Computational Tasks in

Asynchronous Networks

非同步網路基礎運算行程

Leader Election

主要選擇

Breadth-First Search, Shortest

Paths, Broadcast and Convergecast

橫向優先搜尋、最短路徑、散佈

和收斂

Spanning Trees in Asynchronous

Networks

非同步網路的延伸樹 (PDF – 1.2 MB)#

Minimum Spanning Trees

最小延伸樹

Synchronizers

同步裝置 (PDF – 1.1 MB)#

Synchronizer Applications

同步裝置應用程式

Synchronous vs. Asynchronous

Distributed Systems

同步與非同步分散式系統

Asynchronous Shared-Memory

Systems

非同步分享記憶體系統 (PDF – 1.3 MB)#

Modeling

模型

The Mutual Exclusion Problem

互斥問題

Mutual Exclusion Algorithms

互斥演算法

More Mutual Exclusion

Algorithms

更多互斥演算法 (PDF – 1.1 MB)#

Bounds on Shared Memory for

Mutual Exclusion

對互斥的記憶體界限 (PDF – 1.3 MB)#

Resource Allocation

資源分配

The Dining Philosophers Problem

餐桌上的哲學家問題

Impossibility of Consensus in

Asynchronous Shared Memory

Systems

在非同步的分享記憶體系統 (PDF – 1.3 MB)#

不可能性的共識

Atomic Objects

基礎物件

Atomic Snapshot Algorithms

基礎物件映射演算法 (PDF – 1.1 MB)#

Atomic Read/Write Register

Algorithms

基礎物件讀/寫註冊演算法

Translations Between

Asynchronous Network Model

and Asynchronous Shared

Memory Model

非同步網路模型和非同步分 (PDF – 1.0 MB)#

享記憶體模型之間的轉換

Impossibility of Consensus

in Asynchronous Network

Model

在不同步網路模型裡的不可

能性共識

Failure Detectors

失敗偵測

Consensus and

Atomic Broadcast

共識和原子散佈

Time, Clocks, and the

Ordering of Events

時間、計數以及事件順序 (PDF – 1.1 MB#)

State-Machine Simulation

狀態機器模擬

Applications

應用程式

Stable Property Detection

穩定屬性偵測 (PDF)#

Distributed Termination

分散式停止

Global Snapshots

全域映射

Deadlock Detection

死結偵測

Reliable Communication Using

Unreliable Channels

使用不可信賴頻道作可信賴的 (PDF – 1.2 MB)#

溝通

Timing-Based Systems

基於計時的系統 (PDF – 1.3 MB)#

Modeling and Verification

模型和確認

Timing-Based Systems (cont.)

基於計時的系統(繼續) (PDF – 2.1 MB#)

Mutual Exclusion

互斥

Consensus

共識

作 業

One of two sections of each homework assignment, part A and part B, is passed out on a weekly basis. Both sections of each homework are due every two weeks.

每份家庭作業兩個部份的其中之一, Part A 和 Part B, 是每個禮拜固定分派。每個作業的所有部份,將於兩個禮拜後截止回收

Part A Part B

Problem Set 1(PDF) Problem Set 1(PDF)

問題集 1 (PDF) 問題集 1 (PDF)

Problem Set 2(PDF) Problem Set 2(PDF)

問題集 2 (PDF) 問題集 2 (PDF)

Problem Set 3(PDF) Problem Set 3(PDF)

問題集 3 (PDF) 問題集 3 (PDF)

Problem Set 4(PDF) Problem Set 4(PDF)

問題集 4 (PDF) 問題集 4 (PDF)

Problem Set 5(PDF) Problem Set 5(PDF)

問題集 5 (PDF) 問題集 5 (PDF)

Problem Set 6(PDF) Problem Set 6(PDF)

問題集 6 (PDF) 問題集 6 (PDF)

Problem Set 7(PDF) Problem Set 7(PDF)

問題集 7 (PDF) 問題集 7 (PDF)

研習資料

You Might Also Like