Алгоритм Дейкстри – Шолтена

Алгоритм Дейкстри – Шолтена (названий на честь Едсгера В. Дейкстри та Карела С. Шолтен) - алгоритм виявлення припинення в розподіленій системі. [1] [2] Алгоритм запропонували Дейкстра і Шолтеном 1980 року. [3]

Спочатку розглянемо випадок простого графіка процесу, який є деревом. Розподілене обчислення, яке складається з дерев, не є рідкістю. Такий графік процесу може виникнути тоді, коли обчислення суворо є типом поділу і перемоги. Вузол запускає обчислення і ділить задачу на дві (або більше, зазвичай кратну 2) приблизно однакові частини і розподіляє ці частини іншим процесорам. Цей процес триває рекурсивно, поки проблеми не мають достатньо невеликого розміру для вирішення в одному процесорі.

Алгоритм[ред. | ред. код]

Алгоритм Дейкстри – Шолтена - це алгоритм на основі дерева, який можна описати наступним чином:

  • Ініціатором обчислення є корінь дерева.
  • Після отримання обчислювального повідомлення:
    • Якщо процес отримання в даний момент не знаходиться в обчисленні: процес приєднується до дерева, ставши дочірньою точкою відправника повідомлення. (Наразі повідомлення про підтвердження не надсилається.)
    • Якщо процес отримання вже знаходиться в обчисленні: процес негайно надсилає повідомлення-підтвердження відправника повідомлення.
  • Якщо у процесу немає більше варіантів і він не працює, процес від'єднується від дерева, надсилаючи повідомлення-підтвердження своєму батьківському дереву.
  • Припинення відбувається тоді, коли у ініціатора немає варіантів і він простоює.

Алгоритм Дейкстри – Шолтена для дерева[ред. | ред. код]

  • Для дерева легко виявити закінчення. Коли процес опустошення визначає, що він припинився, він надсилає сигнал своєму головному елементу. Загалом, процес чекає, коли всі його варіанти надсилають сигнали, а потім він надсилає сигнал своєму головному елементу.
  • Програма припиняється, коли корінь отримує сигнали від усіх своїх варіантів.

Алгоритм Дейкстри – Шолтена для спрямованих ациклічних графіків[ред. | ред. код]

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

Алгоритм Дейкстри – Шолтена для циклічних спрямованих графіків[ред. | ред. код]

  • Якщо цикли дозволені, попередній алгоритм не працює. Це відбувається тому, що може бути не будь-який вузол із нульовими вихідними ребрами. Отже, потенційно не існує вузла, який може закінчитися без консультацій з іншими вузлами.
  • Алгоритм Дайкстра – Шолтена вирішує цю проблему шляхом неявного створення розтягнутого дерева графу. Діапазонне дерево - це дерево, яке включає кожен вузол базового графу один раз, а набір ребер є підмножиною вихідного набору ребер.
  • Дерево буде спрямоване (тобто канали будуть спрямовані) з вихідним вузлом (який ініціює обчислення) як коренем.
  • Дерево, що складається, створюється наступним чином. Змінна First_Edge додається до кожного вузла. Коли вузол отримує повідомлення вперше, він ініціалізує First_Edge з краєм, через який він отримав повідомлення. First_Edge після цього ніколи не змінюється. Зауважте, що дерево, що охоплює, не є унікальним, і це залежить від порядку повідомлень у системі.
  • Завершенням обробляється кожен вузол у три етапи:
    1. Посилайте сигнали на всі вхідні краї, крім першого краю. (Кожен вузол надсилатиме сигнали, що зменшує дефіцит кожного вхідного краю до нуля.)
    2. Зачекайте сигналів з усіх вихідних країв. (Кількість сигналів, що надходять на кожен вихідний край, має зменшити кожен їх дефіцит до нуля.)
    3. Надсилайте сигнали на First_Edge. (Після того, як кроки 1 і 2 завершені, вузол повідомляє свого батька в дереві, що охоплює, про намір припинити роботу.)

Дивись також[ред. | ред. код]

  1. ↑ Ghosh, Sukumar (2010), 9.3.1 The Dijkstra–Scholten Algorithm, Distributed Systems: An Algorithmic Approach, CRC Press, с. 140—143, ISBN 9781420010848, архів оригіналу за 7 липня 2014, процитовано 10 грудня 2019
  2. ↑ Fokkink, Wan (2013), 6.1 Dijkstra–Scholten algorithm, Distributed Algorithms: An Intuitive Approach, MIT Press, с. 38—39, ISBN 9780262318952, архів оригіналу за 7 липня 2014, процитовано 10 грудня 2019.
  3. ↑ Dijkstra, Edsger W.; Scholten, C. S. (1980), Termination detection for diffusing computations (PDF), Information Processing Letters, 11 (1): 1—4, doi:10.1016/0020-0190(80)90021-6, MR 0585394, архів оригіналу (PDF) за 19 вересня 2020, процитовано 10 грудня 2019.
Отримано з https://uk.wikipedia.org/w/index.php?title=Алгоритм_Дейкстри_–_Шолтена&oldid=35851253