2025Year

Second Semester

Distributed Algorithms

Lecture

Distributed Algorithms

Z0200001 Distributed Algorithms

MANABE Yoshihumi

2.0Credits

Thu.2Period

Shinjuku Remote

.,A-0511教室

A) A high degree of specialized expertise　80%
B) The skills to use science and technology　20%
C) The ability to conduct research independently, knowledge pertaining to society and occupations, and sense of ethics required of engineers and researchers　0%
D) Creative skills in specific areas of specialization　0%

This is a graduate-level distributed algorithm course. The course provides knowledge about distributed algorithms used in distributed systems and networks to achieve effective and fault-tolerant information processing.
Recent results on distributed algorithms are also studied.
On completion of this course, the student should be able to:
(1)Have basic knowledge related to the fundamentals of distributed algorithms.
(2)Evaluate the complexity of fundamental distributed algorithms.
(3)Have basic knowledge of techniques for fault-tolerant distributed systems.

The 1st -14th classes are executed by 'hybrid'.
The students can take the classes in the remote simultaneous interactive mode (no advance permission by the teacher is necessary).
The 15th class is executed by the remote on-demand mode.

Have knowledge about fundamental algorithms.

Interactive classes using ICT／Support for self-learning using ICT

Subjects in the course
 1 Introduction
 Backgrounds of the distributed systems.
 (Preparation) Read Sections 1.1-1.4 of the textbook.

 2 Issues in distributed processing systems
 (Preparation) Read Sections 1.5-1.6 of the textbook.

 3 Logical clock
 (Preparation) Read Section 2 of the textbook.

 4 Distributed snapshot
 (Preparation) Read Section 3 of the textbook.

 5 Leader election
 (Preparation) Read Section 4 of the textbook.

 6 Mutual exclusion
 (Preparation) Read Section 5 of the textbook.

 7 Two-phase commit, PAXOS
 (Preparation) Review about fundamentals of the database.

 8 Termination detection
 (Preparation) Review about two-phase commit protocol

 9 Deadlock detection
 (Preparation) Review of basic definitions in graph theory.

 10 Broadcast communication
 (Preparation) Read Section 6 of the textbook.

 11 Agreement protocol
 (Preparation) Read Sections 7.1-7.2 of the textbook.

 12 Byzantine agreement
 (Preparation) Read Sections 7.3-7.4 of the textbook.

 13 Self-stabilizing algorithm
 (Preparation) Read Section 8 of the textbook.

 14 Token circulation in dynamic networks
 (Preparation) Review algorithms for spanning trees.

 15 (On-demand) Feedback on the final reports and review
 (Preparation) Checking of the course.

Students must answer the questions given in each class. (10%)
They must write a report about one topic in distributed algorithms shown at an international conference. (90%)
Students are given grades A+, A, B, C, D, and F.
Glades other than F are passed.

Gives feedback to each report in the next class.

Yoshifumi Manabe: "Distributed processing systems," Morikita Publishing (In Japanese)

Nancy Lynch: "Distributed Algorithms," Morgan Kaufmann

Thursday 3rd period at A-1572
(Or contact jt13455@ns.kogakuin.ac.jp)

Applicable

通信会社の研究所での勤務の経験がある教員が、分散処理研究の経験を活かし、先進的な分散アルゴリズムについて講義する。

Informatics Program