Алгоритм Дейкстри – Шолтена (названий на честь Едсгера В. Дейкстри та Карела С. Шолтен) - алгоритм виявлення припинення в розподіленій системі. Алгоритм запропонували Дейкстра і Шолтеном 1980 року.
Спочатку розглянемо випадок простого графіка процесу, який є деревом. Розподілене обчислення, яке складається з дерев, не є рідкістю. Такий графік процесу може виникнути тоді, коли обчислення суворо є типом поділу і перемоги. Вузол запускає обчислення і ділить задачу на дві (або більше, зазвичай кратну 2) приблизно однакові частини і розподіляє ці частини іншим процесорам. Цей процес триває рекурсивно, поки проблеми не мають достатньо невеликого розміру для вирішення в одному процесорі.
Алгоритм
Алгоритм Дейкстри – Шолтена - це алгоритм на основі дерева, який можна описати наступним чином:
- Ініціатором обчислення є корінь дерева.
- Після отримання обчислювального повідомлення:
- Якщо процес отримання в даний момент не знаходиться в обчисленні: процес приєднується до дерева, ставши дочірньою точкою відправника повідомлення. (Наразі повідомлення про підтвердження не надсилається.)
- Якщо процес отримання вже знаходиться в обчисленні: процес негайно надсилає повідомлення-підтвердження відправника повідомлення.
- Якщо у процесу немає більше варіантів і він не працює, процес від'єднується від дерева, надсилаючи повідомлення-підтвердження своєму батьківському дереву.
- Припинення відбувається тоді, коли у ініціатора немає варіантів і він простоює.
Алгоритм Дейкстри – Шолтена для дерева
- Для дерева легко виявити закінчення. Коли процес опустошення визначає, що він припинився, він надсилає сигнал своєму головному елементу. Загалом, процес чекає, коли всі його варіанти надсилають сигнали, а потім він надсилає сигнал своєму головному елементу.
- Програма припиняється, коли корінь отримує сигнали від усіх своїх варіантів.
Алгоритм Дейкстри – Шолтена для спрямованих ациклічних графіків
- Алгоритм для дерева може бути розширений до ациклічно спрямованих графіків. До кожного краю додаємо додатковий цілий атрибут Deficit.
- На вхідному краї Deficit позначатиме різницю між кількістю отриманих повідомлень та кількістю сигналів, що надсилаються у відповідь.
- Коли вузол хоче закінчитися, він чекає, поки він отримає сигнали від вихідних ребер, зменшуючи їх дефіцит до нуля.
- Потім він надсилає достатньо сигналів, щоб переконатися, що дефіцит дорівнює нулю на кожному вхідному краї.
- Оскільки графік є ациклічним, деякі вузли не матимуть вихідних країв, і ці вузли будуть першими припинятися після надсилання достатньої кількості сигналів на їх вхідні краї. Після цього вузли на більш високих рівнях припиняються за рівнем.
Алгоритм Дейкстри – Шолтена для циклічних спрямованих графіків
- Якщо цикли дозволені, попередній алгоритм не працює. Це відбувається тому, що може бути не будь-який вузол із нульовими вихідними ребрами. Отже, потенційно не існує вузла, який може закінчитися без консультацій з іншими вузлами.
- Алгоритм Дайкстра – Шолтена вирішує цю проблему шляхом неявного створення розтягнутого дерева графу. Діапазонне дерево - це дерево, яке включає кожен вузол базового графу один раз, а набір ребер є підмножиною вихідного набору ребер.
- Дерево буде спрямоване (тобто канали будуть спрямовані) з вихідним вузлом (який ініціює обчислення) як коренем.
- Дерево, що складається, створюється наступним чином. Змінна First_Edge додається до кожного вузла. Коли вузол отримує повідомлення вперше, він ініціалізує First_Edge з краєм, через який він отримав повідомлення. First_Edge після цього ніколи не змінюється. Зауважте, що дерево, що охоплює, не є унікальним, і це залежить від порядку повідомлень у системі.
- Завершенням обробляється кожен вузол у три етапи:
- Посилайте сигнали на всі вхідні краї, крім першого краю. (Кожен вузол надсилатиме сигнали, що зменшує дефіцит кожного вхідного краю до нуля.)
- Зачекайте сигналів з усіх вихідних країв. (Кількість сигналів, що надходять на кожен вихідний край, має зменшити кожен їх дефіцит до нуля.)
- Надсилайте сигнали на First_Edge. (Після того, як кроки 1 і 2 завершені, вузол повідомляє свого батька в дереві, що охоплює, про намір припинити роботу.)
Дивись також
- Ghosh, Sukumar (2010), 9.3.1 The Dijkstra–Scholten Algorithm, Distributed Systems: An Algorithmic Approach, CRC Press, с. 140—143, ISBN , архів оригіналу за 7 липня 2014, процитовано 10 грудня 2019
- Fokkink, Wan (2013), 6.1 Dijkstra–Scholten algorithm, Distributed Algorithms: An Intuitive Approach, MIT Press, с. 38—39, ISBN , архів оригіналу за 7 липня 2014, процитовано 10 грудня 2019.
- 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.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Algoritm Dejkstri Sholtena nazvanij na chest Edsgera V Dejkstri ta Karela S Sholten algoritm viyavlennya pripinennya v rozpodilenij sistemi Algoritm zaproponuvali Dejkstra i Sholtenom 1980 roku Spochatku rozglyanemo vipadok prostogo grafika procesu yakij ye derevom Rozpodilene obchislennya yake skladayetsya z derev ne ye ridkistyu Takij grafik procesu mozhe viniknuti todi koli obchislennya suvoro ye tipom podilu i peremogi Vuzol zapuskaye obchislennya i dilit zadachu na dvi abo bilshe zazvichaj kratnu 2 priblizno odnakovi chastini i rozpodilyaye ci chastini inshim procesoram Cej proces trivaye rekursivno poki problemi ne mayut dostatno nevelikogo rozmiru dlya virishennya v odnomu procesori AlgoritmAlgoritm Dejkstri Sholtena ce algoritm na osnovi dereva yakij mozhna opisati nastupnim chinom Iniciatorom obchislennya ye korin dereva Pislya otrimannya obchislyuvalnogo povidomlennya Yaksho proces otrimannya v danij moment ne znahoditsya v obchislenni proces priyednuyetsya do dereva stavshi dochirnoyu tochkoyu vidpravnika povidomlennya Narazi povidomlennya pro pidtverdzhennya ne nadsilayetsya Yaksho proces otrimannya vzhe znahoditsya v obchislenni proces negajno nadsilaye povidomlennya pidtverdzhennya vidpravnika povidomlennya Yaksho u procesu nemaye bilshe variantiv i vin ne pracyuye proces vid yednuyetsya vid dereva nadsilayuchi povidomlennya pidtverdzhennya svoyemu batkivskomu derevu Pripinennya vidbuvayetsya todi koli u iniciatora nemaye variantiv i vin prostoyuye Algoritm Dejkstri Sholtena dlya derevaDlya dereva legko viyaviti zakinchennya Koli proces opustoshennya viznachaye sho vin pripinivsya vin nadsilaye signal svoyemu golovnomu elementu Zagalom proces chekaye koli vsi jogo varianti nadsilayut signali a potim vin nadsilaye signal svoyemu golovnomu elementu Programa pripinyayetsya koli korin otrimuye signali vid usih svoyih variantiv Algoritm Dejkstri Sholtena dlya spryamovanih aciklichnih grafikivAlgoritm dlya dereva mozhe buti rozshirenij do aciklichno spryamovanih grafikiv Do kozhnogo krayu dodayemo dodatkovij cilij atribut Deficit Na vhidnomu krayi Deficit poznachatime riznicyu mizh kilkistyu otrimanih povidomlen ta kilkistyu signaliv sho nadsilayutsya u vidpovid Koli vuzol hoche zakinchitisya vin chekaye poki vin otrimaye signali vid vihidnih reber zmenshuyuchi yih deficit do nulya Potim vin nadsilaye dostatno signaliv shob perekonatisya sho deficit dorivnyuye nulyu na kozhnomu vhidnomu krayi Oskilki grafik ye aciklichnim deyaki vuzli ne matimut vihidnih krayiv i ci vuzli budut pershimi pripinyatisya pislya nadsilannya dostatnoyi kilkosti signaliv na yih vhidni krayi Pislya cogo vuzli na bilsh visokih rivnyah pripinyayutsya za rivnem Algoritm Dejkstri Sholtena dlya ciklichnih spryamovanih grafikivYaksho cikli dozvoleni poperednij algoritm ne pracyuye Ce vidbuvayetsya tomu sho mozhe buti ne bud yakij vuzol iz nulovimi vihidnimi rebrami Otzhe potencijno ne isnuye vuzla yakij mozhe zakinchitisya bez konsultacij z inshimi vuzlami Algoritm Dajkstra Sholtena virishuye cyu problemu shlyahom neyavnogo stvorennya roztyagnutogo dereva grafu Diapazonne derevo ce derevo yake vklyuchaye kozhen vuzol bazovogo grafu odin raz a nabir reber ye pidmnozhinoyu vihidnogo naboru reber Derevo bude spryamovane tobto kanali budut spryamovani z vihidnim vuzlom yakij iniciyuye obchislennya yak korenem Derevo sho skladayetsya stvoryuyetsya nastupnim chinom Zminna First Edge dodayetsya do kozhnogo vuzla Koli vuzol otrimuye povidomlennya vpershe vin inicializuye First Edge z krayem cherez yakij vin otrimav povidomlennya First Edge pislya cogo nikoli ne zminyuyetsya Zauvazhte sho derevo sho ohoplyuye ne ye unikalnim i ce zalezhit vid poryadku povidomlen u sistemi Zavershennyam obroblyayetsya kozhen vuzol u tri etapi Posilajte signali na vsi vhidni krayi krim pershogo krayu Kozhen vuzol nadsilatime signali sho zmenshuye deficit kozhnogo vhidnogo krayu do nulya Zachekajte signaliv z usih vihidnih krayiv Kilkist signaliv sho nadhodyat na kozhen vihidnij kraj maye zmenshiti kozhen yih deficit do nulya Nadsilajte signali na First Edge Pislya togo yak kroki 1 i 2 zaversheni vuzol povidomlyaye svogo batka v derevi sho ohoplyuye pro namir pripiniti robotu Divis takozhAlgoritm Huanga Ghosh Sukumar 2010 9 3 1 The Dijkstra Scholten Algorithm Distributed Systems An Algorithmic Approach CRC Press s 140 143 ISBN 9781420010848 arhiv originalu za 7 lipnya 2014 procitovano 10 grudnya 2019 Fokkink Wan 2013 6 1 Dijkstra Scholten algorithm Distributed Algorithms An Intuitive Approach MIT Press s 38 39 ISBN 9780262318952 arhiv originalu za 7 lipnya 2014 procitovano 10 grudnya 2019 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 arhiv originalu PDF za 19 veresnya 2020 procitovano 10 grudnya 2019