|
|
| (не показана 31 промежуточная версия 3 участников) |
| Строка 1: |
Строка 1: |
| − | Обязательный курс для магистров 521 группы 10 семестра обучения.
| + | #перенаправление [[Распределённые алгоритмы]] |
| − | | + | |
| − | Курс читает профессор [[Захаров Владимир Анатольевич|В. А. Захаров]].
| + | |
| − | | + | |
| − | Лекционная нагрузка — 48 ч., семинары — 16 ч.
| + | |
| − | | + | |
| − | <h4>'''[[Media: Tasks_DisAlg.pdf| ЗАДАЧИ К ЭКЗАМЕНУ.]]'''</h4>
| + | |
| − | | + | |
| − | <!--
| + | |
| − | <h4>'''[[Media: G-521-2017.pdf| ТЕКУЩАЯ УСПЕВАЕМОСТЬ.]]'''</h4>
| + | |
| − | | + | |
| − | <h4>'''[[Media: G-521-2017.pdf| НАЧАЛО ЭКЗАМЕНА - 10.00]]'''</h4>
| + | |
| − | -->
| + | |
| − | | + | |
| − | == Program of the course ==
| + | |
| − | | + | |
| − | <h4>Part 1. Formal Models.</h4>
| + | |
| − | | + | |
| − | #Distributed systems and their generic features. Distributed systems architecture. ISO Open System Interaction standard. Algorithmic problems of distributed computing systems. Specific features of distributed algorithms. '''[[Media: Lecture-DA-1.pdf| Lecture 1.]]''' | + | |
| − | #Formal models of distributed systems. Transition systems. Synchronous and asynchronous message passing. Fairness properties. Dependent and independent events. Causal order of events. Equivalence of execution. Distributed computations. Logical clocks. '''[[Media: Lecture-DA-2.pdf| Lecture 2.]]'''
| + | |
| − | #:
| + | |
| − | #:<h4>Part 2. Communication Protocols.</h4>
| + | |
| − | #:
| + | |
| − | #Communication Protocols. Errors in message transmission. Symmetric sliding window protocol: protocol design. Mathematical techniques for proving correctness of distributed algorithms. Correctness of sliding window protocol. Implementation of sliding window protocol. Alternating Bit Protocol. '''[[Media: Lecture-DA-3.pdf| Lecture 3.]]'''
| + | |
| − | #A timer-based communication protocol. Protocol design. Correctness of timer-based protocol. Implementation of timer-based protocol. '''[[Media: Lecture-DA-4.pdf| Lecture 4.]]'''
| + | |
| − | #Routing problem. Destination-based routing. The all-pairs shortest-path problem. Floyd--Warshall algorithm. Toueg's shortest-path algorithm. Merlin--Segall algorithm. Chandy--Misra algorithm. '''[[Media: Lecture-DA-5.pdf| Lecture 5.]]'''
| + | |
| − | #:
| + | |
| − | #:<h4>Part 3. Wave and Election Algorithms.</h4>
| + | |
| − | #:
| + | |
| − | #Wave algorithms: definition, basic properties, applications. The Ring algorithm. The Tree algorithm. The Echo algorithm. '''[[Media: Lecture-DA-6.pdf| Lecture 6.]]''' The Phase algorithm. Phinn's algorithm. Traversal algorithms. Depth-first-search traversal. Awerbuch's and Cidon's algorithms. '''[[Media: Lecture-DA-7.pdf| Lecture 7.]]'''
| + | |
| − | #Leader Election Problem. Leader election in rings: Le Lann Algorithm. Cheng-Roberts Algorithm. Paterson/Dolev-Clave-Rode Algorithm. Extinguish effect. '''[[Media: Lecture-DA-8.pdf| Lecture 8.]]''' Leader election in arbitrary networks. Lower bounds.
| + | |
| − | Gallager-Humblet-Spira Algorithm (GHS). Corach-Katten-Moran Algorithm. '''[[Media: Lecture-DA-9.pdf| Lecture 9.]]'''
| + | |
| − | #Задача обнаружения завершения вычисления. Алгоритм Дейкстры-Шолтена. Алгоритм Шави-Франчеза. Алгоритм Сафры. Алгоритм возвращения кредитов. Алгоритм Раны. <!--'''[[Media: DistrAlg_11.pdf| Лекция 11.]]'''-->
| + | |
| − | #Задача сохранения моментального состояния. Алгоритм Чанди-Лампорта. Алгоритм Лаи-Янга. Применение алгоритмов обнаружения моментальной разметки и завершения вычислений для выявления блокировки вычислений. <!--'''[[Media: DistrAlg_12.pdf| Лекция 12.]]'''-->
| + | |
| − | #:
| + | |
| − | #:<h4>Часть 4. Вопросы надежности распределенных алгоритмов.</h4>
| + | |
| − | #:
| + | |
| − | #Задача обеспечения отказоустойчивости распределенных систем. Невозможность построения робастных асинхронных систем. Синхронные робастные алгоритмы принятия решения. Использование криптографических примитивов для повышения отказоустойчивости. <!--'''[[Media: DistrAlg_13.pdf| Лекция 13.]]'''
| + | |
| − | #Стабилизирующиеся алгоритмы. Пример Дейкстры. Общие принципы построения стабилизирующихся алгоритмов.-->
| + | |
| − | | + | |
| − | == Литература ==
| + | |
| − | | + | |
| − | #G. Tel. Introduction to Distributed Algorithms. Cambridge University Press. 2000. (русск. пер. Ж. Тель. Введение в распределенные алгоритмы, изд-во МЦНМО, 2009 г., 616 с.)
| + | |
| − | #W. Fokkink. Distributed Algorithms: Intuitive Approach. The MIT Press. 2013. (русск. пер. У. Фоккинк. Распределенные алгоритмв: интуитивный подход., изд-во Питер, 2017 г., 231 с.)
| + | |
| − | #N. Lynch. Distributed Algorithms. Morgan Kaufmann, 1996, 906 pp.
| + | |
