Теория отказоустойчивых распределенных систем

2021/2022

Учебный год

RUS

Обучение ведется на русском языке

5

Кредиты

Кто читает:

Департамент больших данных и информационного поиска

Статус:

Курс по выбору

Когда читается:

4-й курс, 1, 2 модуль

Преподаватель

Липовский Роман Германович

Программа дисциплины

Аннотация

Курс посвящен теории, лежащей в основе современных промышленных распределенных систем: файловых систем, очередей сообщений, key/value хранилищ, баз данных. Эти системы хранят десятки и сотни петабайт данных, обслуживают многие тысячи запросов в секунду и масштабируются до сотен и тысяч машин, переживая при этом отказы дисков и питания, дрейф часов, задержки и нарушения связности сети, а потому устроены невероятно сложно. Но если посмотреть сквозь все инженерные детали и сотни тысяч строк кода, то окажется, что сложность, связанную с распределенностью, можно заключить в относительно простые модели и задачи: как узлам договориться о порядке доставки сообщений в асинхронной сети, как выбрать лидера среди равноправных машин, как добавить в систему еще один сервер или обнаружить сбойную машину. Именно от решения этих задач в конечном итоге будут зависеть важнейшие характеристики всей системы: границы ее отказоустойчивости, доступность при нестабильном поведении сети и модель согласованности данных. В курсе мы рассмотрим эти задачи, исследуем ограничения, которые накладывает на них модель сети и сбоев, и потрогаем практические алгоритмы, которые применяются в известных промышленных распределенных системах.

Цель освоения дисциплины

• Научить студента видеть за распределенными системами ряд фундаментальных задач, которые определяют ключевые характеристики этих систем: отказоустойчивость, масштабируемость, доступность
• Изучить различные модели сети и сбоев, исследовать ограничения, которые они накладывают на решения этих задач
• Изучить ключевые алгоритмы, которые используются в промышленных распределенных системах
• Научить студента ориентироваться в научной области, познакомиться с ключевыми академическими работами

Планируемые результаты обучения

• Знает алгоритмы, которые используются в промышленных распределенных системах
• Знает подходы к верификации распределенных систем, владеет формальными методами верификации
• Знает теоретические модели, ключевые задачи и результаты о невозможности
• Ориентируется в корпусе ключевых академических работ

Содержание учебной дисциплины

• Модель распределенной системы. Время
• Репликация, отказоустойчивый атомарный регистр
• State Machine Replication, Atomic Broadcast и Consensus
• Невозможность консенсуса
• Single-Decree Paxos
• Multi-Paxos, RAFT
• Paxos Made Live
• Распределенные транзакции
• Верификация, формальные методы
• Византийские сбои
• Practical Byzantine Fault-Tolerance
• Bitcoin и блокчейны
• Финал

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

• Домашние задания
• Экзамен

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

• 2021/2022 учебный год 2 модуль
  0.3 * Экзамен + 0.7 * Домашние задания

Список литературы

Рекомендуемая основная литература

• Diego Ongaro, & John Ousterhout. (n.d.). search of an understandable consensus algorithm (extended version). http://ramcloud.stanford.edu/raft.pdf. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsbas&AN=edsbas.A4E9E649
• Leslie Lamport, John Matthews, Mark Tuttle, & Yuan Yu. (2002). Specifying and Verifying Systems with TLA+. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsbas&AN=edsbas.50C26A50
• Leslie Lamport. (2000). The part-time parliament. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsbas&AN=edsbas.18E496B7
• Michael J Fischer, Nancy A Lynch, Michael S Paterson, & Coventry England. (1985). Impossibility of distributed consensus with one faulty process. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsbas&AN=edsbas.A8DAD60D
• Miguel Castro, & Barbara Liskov. (1999). Practical Byzantine Fault Tolerance. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsbas&AN=edsbas.30DBEB
• Miguel Castro, & Barbara Liskov. (1999). Practical Byzantine Fault Tolerance. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsbas&AN=edsbas.74E767E1
• Miguel Castro, & Barbara Liskov. (1999). Practical Byzantine Fault Tolerance. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsbas&AN=edsbas.A9BB0A53
• Miguel Castro. (1999). Practical byzantine fault tolerance. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsbas&AN=edsbas.77FEF0D
• Miguel Castro. (1999). Practical byzantine fault tolerance. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsbas&AN=edsbas.BF8BF52B
• Satoshi Nakamoto. (n.d.). Bitcoin: A peer-to-peer electronic cash system,” http://bitcoin.org/bitcoin.pdf. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsbas&AN=edsbas.E2C1762F
• Tushar Chandra, Robert Griesemer, & Joshua Redstone. (2007). Paxos made live: an engineering perspective. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsbas&AN=edsbas.EC238F24
• Tushar Deepak Chandra, & Sam Toueg. (1996). Unreliable failure detectors for reliable distributed systems. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsbas&AN=edsbas.706C61D1

Рекомендуемая дополнительная литература

• Barbara Liskov. (n.d.). Chapter 7 From Viewstamped Replication to Byzantine Fault Tolerance. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsbas&AN=edsbas.C6D4326F
• Herlihy, M. (2018). Atomic Cross-Chain Swaps. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsarx&AN=edsarx.1801.09515