Алгоритм Дейкстри Шолтена названий на честь Едсгера В Дейкстри та Карела С Шолтен алгоритм виявлення припинення в розпод

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

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

Алгоритм

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

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

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

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

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

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

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

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

Дивись також

Алгоритм Хуанга

Ghosh, Sukumar (2010), 9.3.1 The Dijkstra–Scholten Algorithm, , CRC Press, с. 140—143, ISBN , архів оригіналу за 7 липня 2014, процитовано 10 грудня 2019
Fokkink, Wan (2013), 6.1 Dijkstra–Scholten algorithm, , MIT Press, с. 38—39, ISBN , архів оригіналу за 7 липня 2014, процитовано 10 грудня 2019.
Dijkstra, Edsger W.; Scholten, C. S. (1980), (PDF), Information Processing Letters, 11 (1): 1—4, doi:10.1016/0020-0190(80)90021-6, MR 0585394, архів оригіналу (PDF) за 19 вересня 2020, процитовано 10 грудня 2019.

[1] Ghosh, Sukumar (2010), 9.3.1 The Dijkstra–Scholten Algorithm, , CRC Press, с. 140—143, ISBN , архів оригіналу за 7 липня 2014, процитовано 10 грудня 2019

[2] Fokkink, Wan (2013), 6.1 Dijkstra–Scholten algorithm, , MIT Press, с. 38—39, ISBN , архів оригіналу за 7 липня 2014, процитовано 10 грудня 2019.

[3] Dijkstra, Edsger W.; Scholten, C. S. (1980), (PDF), Information Processing Letters, 11 (1): 1—4, doi:10.1016/0020-0190(80)90021-6, MR 0585394, архів оригіналу (PDF) за 19 вересня 2020, процитовано 10 грудня 2019.