Вікіпедія

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

Алгоритм Дейкстри – Шолтена (названий на честь Едсгера В. Дейкстри та Карела С. Шолтен) - алгоритм виявлення припинення в розподіленій системі. [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. Information Processing Letters 11 (1): 1–4. MR 585394. doi:10.1016/0020-0190(80)90021-6. Архів оригіналу за 19 вересня 2020. Процитовано 10 грудня 2019. .
Отримано з https://uk.wikipedia.org/w/index.php?title=Алгоритм_Дейкстри_–_Шолтена&oldid=35851253