• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
Бакалавриат 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
Элементы контроля

Элементы контроля

  • неблокирующий Домашнее задание 3
  • неблокирующий Экзамен
  • неблокирующий Домашнее задание 2
  • неблокирующий Домашнее задание 1
Промежуточная аттестация

Промежуточная аттестация

  • 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

Авторы

  • Ахмедова Гюнай Интигам кызы