Опис курсу

Навчальна дисципліна присвячена вивченню фундаментальних принципів проектування та аналізу розподілених алгоритмів – специфікацій процесів обробки інформації, що виконуються множиною локальних процесів, об’єднаних мережею. На відміну від багатопроцесних систем, де взаємодія відбувається через спільну пам’ять, у розподілених системах кожен процес має монопольний доступ до власної пам’яті та координує свої дії виключно через обмін повідомленнями.

Актуальність курсу зумовлена необхідністю створення високонадійних систем, що забезпечують масштабованість обчислень, відмовостійкість та ефективне використання географічно розподілених ресурсів. У межах дисципліни розглядаються ключові чинники складності розробки такого ПЗ: відсутність глобального часу, недетермінованість через паралелізм подій, гетерогенність вузлів та відсутність єдиної точки відмови.

Програма курсу охоплює такі ключові напрямки.

• Моделювання та синхронізація: вивчення мереж як комунікаційних графів та опанування концепції причинно-наслідкового порядку подій. Студенти вивчають механізми логічних годинників (зокрема годинники Лемпорта), які дозволяють впорядковувати події в системі без потреби у фізичній синхронізації часу.
• Базові класи алгоритмів: дослідження хвильових та обхідних алгоритмів (алгоритм Таррі, DFS-обхід), що забезпечують обмін інформацією та прийняття рішень усіма вузлами мережі.
• Стабільність та виживання системи: опанування методів створення глобальних знімків стану (Snapshots) за алгоритмами Чанді-Лемпорта та Лаї-Янга, що необхідно для діагностики та відновлення систем. Також розглядаються алгоритми виборів лідера у кільцевих та деревних топологіях для відновлення координації після збоїв.
• Управління ресурсами та завершенням: виявлення та усунення взаємних блокувань (deadlocks) за допомогою графів очікування, а також методи розподіленого збирання сміття (непрямий та зважений підрахунок посилань).

Ефективна комунікація: побудова таблиць маршрутизації за алгоритмом Мерліна-Сігалла для пошуку найкоротших шляхів передачі даних.