Алгоритм Дейкстри – Шолтена (названий на честь Едсгера В. Дейкстри та Карела С. Шолтен) - алгоритм виявлення припинення в розподіленій системі. ^{[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.