Определение завершения распределённых вычислений

Несколько ссылок

• Слайды-книжка Кшемкальяни и Сингала Termination detection
• Раджив Мисра Termination detection
• Обзор статьи Мисры (видимо, другого) Detecting Termination of Distributed Computations Using Markers (1983)

А вообще как-то негусто лекционного материала на эту тему

Снимки глобального состояния - ссылки

Самый известный алгоритм для случая FIFO каналов - алгоритм Чанди-Лэмпорта, для неFIFO - алгоритм Лай-Янга. Есть ещё парочка алгоритмов для случая каузальной доставки (causal ordering).

Теперь ссылки. Сначала классические статьи

K. Chandy, L. Lamport Distributed Snapshots: Determining Global States of Distributed Systems (ссылка)

Ten H. Lai and Tao H. Yang On Distributed Snapshots (ссылка) 

F. Mattern Efficient Algorithms for Distributed Snapshots and Global Virtual Time Approximation (ссылка)

Материалы университета Принстон (курс COS 418: Distributed Systems):

• Themis Melissaris and Daniel Suo Chandy-Lamport Snapshotting (ссылка) 
• Kyle Jamieson Vector Clocks and Distributed Snapshots (ссылка)
• Лабораторка Chandy-Lamport Distributed Snapshots (ссылка)

Материалы университета МакМастера (курс CAS 769):

• Dr. Borzoo Bonakdarpour  Introduction, Logical clocks, Snapshots (ссылка)

Материалы университета Айовы:

• Ghosh Distributed Snapshot (ссылка) - есть граф достижимости состояний

Разбор статьи Чанди-Лэмпорта (ссылка)

Нашёл тут интересный блог The morning paper, где разбирают разные статьи по информатике. Понравился подзаголовок журнала: A random walk through Computer Science research. Блог интересный, располагается здесь.

Поскольку сейчас вникаю в тему распределённых снимков глобального состояния, просмотрел заметку о статье Чанди и Лэмпорта Distributed Snapshots: Determining Global States of Distributed Systems (1985). Хороший пересказ, есть пример о разноцветных шариках.

Из другого поста того же блога (Asynchronous Distributed Snapshots for Distributed Dataflows) можно узнать, что алгоритм Чанди-Лэмпорта используется в Apache Flink (это такая штука, которая позволяет проводить вычисления на потоках данных).

Снимки: предварительные сведения

Глобальное состояние - совокупность состояний всех локальных состояний процессов и каналов.

Глобальное состояние согласовано, если выполнены два условия:
C1. если посылка сообщения по каналу от P_i к P_j входит в локальное состояние P_i, то либо это сообщение входит в состояние канала C_ij, либо событие приёма этого сообщения входит в локальное состояние процесса P_j. Имеются ввиду состояния канала C_ij и локальные состояния процессов P_i и P_j, входящие в данное глобальное состояние. 
C2. если посылка сообщения по каналу от P_i к P_j не входит в локальное состояние P_i, то это сообщение не входит в состояние канала C_ij и не входит в локальное состояние процесса P_j.

Две основные проблемы при записи состояний:
П1. Как отличить сообщения, которые нужно записать в снимок от тех, которые записывать не нужно. С1 и C2 говорят, что нужно записывать те сообщения от P_i, которые были посланы процессом P_i до фиксации своего локального состояния.
П2. Как определить момент, когда процессу нужно сделать снимок. С2 говорит, что процесс P_j должен зафиксировать своё состояние до обработки сообщения от P_i, которое было послано  P_i после фиксации своего состояния.

Снимки глобального состояния

Непростая тема. И вроде не такая уж большая . Нужно только понять, что такое согласованное состояние и изучить два алгоритма - Чанди-Лэмпорта (требует FIFO каналов) и Лая-Янга (нет требования FIFO). А что-то трудно идёт.

По книге Фоккинга разбираться сложно. Гораздо лучше написано у Кшемкальяни и Сингала. Вот ссылка на их лекцию (на самом деле, это просто кусок их книги, перенесённый на слайды).

У Фоккинга нашёл только хороший перевод понятия FIFO-канала : каналы с обработкой сообщений в порядке очереди.

Дополнение. Почитав Кшемкальяни (упомянутую лекцию и их же статью An introduction to snapshot algorithms in distributed computing), понял, что весьма упрощённо представлял себе область. На самом деле, там три группы алгоритмов:

1. для FIFO-каналов. Здесь алгоритм Чанди-Лэмпорта и его модификации ( Spezialetti and Kearns, Venkatesan, Helary). 
2. для не-FIFO.  Алгоритм Лая-Янга, Маттерна
3. для систем с каузальной доставкой. Алгоритмы Acharya-Badrinath, Alagar-Venkatesan.

Алгоритм банкира

Здесь я пишу о своём нынешнем понимании алгоритма банкира, которое пока является неполным.

Этот алгоритм - стратегия, которая позволяет ресурсы потребителям, избегая тупиковых ситуаций (deadlock avoidance). Такой алгоритм пригодится, например, операционной системе, которая распределяет процессам память, даёт доступ к принтеру и т.д.

Тупиком здесь является ситуация, когда у ОС (или у банкира) нет достаточно ресурсов, чтобы удовлетворить запрос хотя бы одного потребителя (это моё понимание). Получается, что потребители ждут выделения ресурсов  от ОС, а ОС в свою очередь ждёт, пока ему вернут достаточно ресурсов, чтобы можно было выдать их кому-нибудь. 

Нам дано: количество ресурсов и количество потребителей (процессов). Важное ограничение алгоритма: необходимо знать максимальную потребность в каждом ресурсе каждого потребителя. 

В двух словах алгоритм выглядит следующим образом. У нас есть Available - вектор наличных ресурсов (один на всю систему) и Need - вектор потребностей каждого процесса. Просматриваем потребности процессов, начиная с первого. Если у i-го процесса Need <= Available, то система выдаст ему все нужные ресурсы. Процесс отработает, вернёт ресурсы и будет исключен из списка работающих процессов. Далее опять происходит просмотр обновлённого списка работающих процессов, определяется следующий процесс, который получит ресурсы.  

Ссылки:
Dijkstra’s Banker’s algorithm detailed explanation [ссылка] - лучшая
Wiki: Banker’s algorithm [ссылка]
What is Banker's Algorithm? [ссылка]