Технология синхронного распараллеливания в распределенных системах

Евдокимова Т.О.
бакалавриат, семестр 8

Курс состоит из двух частей. Первая часть посвящена фундаментальным алгоритмам – алгоритмическим блокам, использующимся как процедуры в различных распределенных программах. Мы рассмотрим класс волновых алгоритмов, которые являются обобщенными схемами, позволяющими посетить все узлы системы. С помощью волновых алгоритмов можно распространять информацию в системе, проводить синхронизацию узлов, вычислять функцию, зависящую от распределенной в узлах системы информации; многие задачи распределенного управления могут быть решены с помощью алгоритмических схем общего вида, использующих волной алгоритм в качестве одного из компонентов. Также будут обсуждаться такие задачи как задача избрания лидера (определение единственного процесса, который будет играть особую роль в последующем вычислении) и задача обнаружения завершения вычисления (процессы должны установить, завершилось ли распределенное вычисление). Будет показано, как процессы системы могут вычислить глобальную картину состояния системы – моментальное состояние, которое используется для определения различных свойств вычисления, например, обнаружения блокировок, а также как вполне асинхронная система может воспроизводить поведение синхронных систем с помощью достаточно простых алгоритмов. Во второй части курса изучаются вопросы отказоустойчивости асинхронных и синхронных распределенных систем. Также рассматривается другой подход к повышению надежности систем – самостабилизирующиеся алгоритмы.

Рекомендуемая литература – учебник Ж.Теля "Ввведение в распределенные алгоритмы".