Бакалавриат
2026/2027




Теория отказоустойчивых распределенных систем
ID 1134297
Статус:
Курс обязательный (Компьютерные науки и анализ данных)
Где читается:
Факультет компьютерных наук
Когда читается:
4-й курс, 1, 2 модуль
Охват аудитории:
для своего кампуса
Язык:
русский
Кредиты:
5
Контактные часы:
56
Программа дисциплины
Аннотация
Курс посвящен теории, лежащей в основе современных промышленных распределенных систем: файловых систем, очередей сообщений, key/value хранилищ, баз данных. Эти системы хранят десятки и сотни петабайт данных, обслуживают многие тысячи запросов в секунду и масштабируются до сотен и тысяч машин, переживая при этом отказы дисков и питания, дрейф часов, задержки и нарушения связности сети, а потому устроены невероятно сложно. Но если посмотреть сквозь все инженерные детали и сотни тысяч строк кода, то окажется, что сложность, связанную с распределенностью, можно заключить в относительно простые модели и задачи: как узлам договориться о порядке доставки сообщений в асинхронной сети, как выбрать лидера среди равноправных машин, как добавить в систему еще один сервер или обнаружить сбойную машину. Именно от решения этих задач в конечном итоге будут зависеть важнейшие характеристики всей системы: границы ее отказоустойчивости, доступность при нестабильном поведении сети и модель согласованности данных. В курсе мы рассмотрим эти задачи, исследуем ограничения, которые накладывает на них модель сети и сбоев, и потрогаем практические алгоритмы, которые применяются в известных промышленных распределенных системах.
Цель освоения дисциплины
- Научить студента видеть за распределенными системами ряд фундаментальных задач, которые определяют ключевые характеристики этих систем: отказоустойчивость, масштабируемость, доступность
- Изучить различные модели сети и сбоев, исследовать ограничения, которые они накладывают на решения этих задач
- Изучить ключевые алгоритмы, которые используются в промышленных распределенных системах
- Научить студента ориентироваться в научной области, познакомиться с ключевыми академическими работами
Планируемые результаты обучения
- Знает алгоритмы, которые используются в промышленных распределенных системах
- Знает подходы к верификации распределенных систем, владеет формальными методами верификации
- Знает теоретические модели, ключевые задачи и результаты о невозможности
- Ориентируется в корпусе ключевых академических работ
Содержание учебной дисциплины
- Модель распределенной системы и часы в ней
- Модели согласованности, линеаризуемый регистр (алгоритм ABD)
- Replicated State Machine, сведение к задаче консенсуса
- Ограничения решений задачи консенсуса, FLP теорема
- The Part-Time Parliament, алгоритм синода
- Алгоритм Paxos, репликация лога
- Алгоритм RAFT
- Масштабирование RSM, шардирование
- Транзакции в распределенной системе, Serialized Snapshot Isolation, Atomic commit
- Транзакции в Google Spanner
- Deterministic Transactions (Calvin) и client side транзакции в Percolator
- Византийский консенсус, PBFT
- Bitcoin, консенсус Накамото
- HotStuff
Промежуточная аттестация
- 2026/2027 2nd moduleОценка за курс ставиться по следующей формуле (ОДз1 + ОДз2 + ОДз3 + ОЭкз)*4/3, где максимальная отметка за Дз1 1 балл за Дз2 3 балла за Дз3 2 балла за Экз 2 балла
Список литературы
Рекомендуемая основная литература
- Распределенные системы - Стин ван М., Таненбаум Э. С. - Издательство "ДМК Пресс" - 978-5-97060-708-4 - 2021 - русский - https://e.lanbook.com/book/240992 - ЛАНЬ - 240992
- Распределенные системы и алгоритмы - Миков А.И., Замятина Е.Б. - Национальный Открытый Университет "ИНТУИТ" - - - 2016 - русский - https://e.lanbook.com/book/100446 - ЛАНЬ - 100446
Рекомендуемая дополнительная литература
- Архитектура ЭВМ и информационных систем: функциональная организация - Панфилов И.В., Заяц А.М. - Санкт-Петербургский государственный лесотехнический университет имени С.М. Кирова - 978-5-9239-0578-6 - 2013 - русский - https://e.lanbook.com/book/45461 - ЛАНЬ - 45461