الگوریتم دایکسترا – شولتن - ویکی‌پدیا، دانشنامهٔ آزاد

الگوریتم Dijkstra–Scholten (این الگوریتم به نام Edsger W. Dijkstra و Carel S. Scholten نامگذاری شده‌است)، این الگوریتم برای تشخیص پایان یا خاتمه که در یک سیستم توزیع شده‌است.^[۱]^[۲] این الگوریتم توسط دایکسترا و شولتن در سال ۱۹۸۰ پیشنهاد شد.^[۳]

در ابتدا، یک نمودار گراف روند ساده را در نظر بگیرید که از نوع نمودار درختی است. یک محاسبات توزیع شده که ساختار درختی دارد، نامتداول نیست. چنین گراف روندی ممکن است موقعی که محاسبات کاملاً از نوع تقسیم و غلبه باشد، به وجود آید. یک رأس محاسبات را شروع می‌کند و مسئله را به دو (یا بیشتر، معمولاً مضرب ۲) قسمت تقریباً مساوی تقسیم می‌کند و آن قسمت‌ها را به پردازنده‌های دیگر توزیع می‌کند. این فرایند به صورت بازگشتی ادامه می‌یابد تا زمانی که مسئله‌ها به اندازه کافی کوچک باشند تا بتوان آنرا در یک پردازنده واحد حل کرد.

الگوریتم

الگوریتم Dijkstra–Scholten الگوریتمی است مبتنی بر درخت، که با موارد زیر توصیف می‌شود:

آغازگر یک محاسبه ریشه درخت است.
پس از دریافت پیام محاسباتی:
- اگر فرایند دریافت در حال حاضر در محاسبات نباشد: فرایند، با تبدیل شدن به فرزند فرستنده پیام به درخت می‌پیوندد. (در این مرحله هیچ پیامی ارسال نمی‌شود)
- اگر فرایند دریافت از قبل در حال محاسبه باشد: فرایند بلافاصله یک پیام تأیید را برای فرستنده پیام ارسال می‌کند.
وقتی فرآیندی فرزند دیگری نداشته باشد و بیکار شود، فرایند با ارسال یک پیام تأیید به والد درختی خود را از درخت جدا می‌کند.
خاتمه و پایان فرایند زمانی اتفاق می‌افتد که آغازگر فرزندی نداشته باشد و بیکار شده باشد.

الگوریتم Dijkstra–Scholten برای یک درخت

برای یک درخت، تشخیص خاتمه آن آسان است. هنگامی که یک فرایند برگ مشخص می‌کند که پایان یافته‌است، سیگنالی را به والد خود ارسال می‌کند. به‌طور کلی، یک فرایند منتظر می‌ماند تا همه فرزندان خود سیگنال ارسال کنند و سپس سیگنالی را برای والدین خود ارسال می‌کند.
این برنامه زمانی خاتمه می‌یابد که روت سیگنال‌هایی را از همه فرزندان خود دریافت کند.

الگوریتم Dijkstra-Scholten برای نمودارهای غیر چرخه ای جهت دار

الگوریتم یک درخت را می‌توان به نمودارهای جهت دار بدون چرخه گسترش داد. به هر یال یک ویژگی عدد صحیح اضافی اضافه می‌کنیم.
در یال ورودی، تفاوت کمی بین تعداد پیام‌های دریافتی و تعداد سیگنال‌های ارسال شده در پاسخ وجود دارد.
هنگامی که یک راس می‌خواهد خاتمه یابد، منتظر می‌ماند تا سیگنال‌هایی را از یال‌های خروجی دریافت کند و تفاوت آنها را به صفر برساند.
سپس سیگنال‌های کافی برای اطمینان از صفر بودن کسری در هر یال ورودی ارسال می‌کند.
از آنجایی که نمودار غیر چرخه‌ای است، برخی از رأس‌ها یال‌های خروجی ندارند و این رأس‌ها اولین رأس‌هایی هستند که پس از ارسال سیگنال‌های کافی به یال‌های ورودی خود خاتمه می‌یابند. پس از آن رأس‌های سطوح بالاتر سطح به سطح خاتمه می‌یابند.

الگوریتم Dijkstra-Scholten برای نمودارهای چرخه ای جهت دار

اگر چرخه‌ها مجاز باشند، الگوریتم قبلی کار نمی‌کند. این به این دلیل است که ممکن است هیچ رأسی با یال‌های خروجی صفر وجود نداشته باشد؛ بنابراین، به‌طور بالقوه هیچ رأسی وجود ندارد که بتواند بدون مشورت با سایر رأس‌ها خاتمه یابد.
الگوریتم Dijkstra-Scholten این مشکل را با ایجاد ضمنی یک درخت پوشا از نمودار حل می‌کند. درخت پوشا درختی است که هر رأس گراف زیرین را یکبار شامل می‌شود و مجموعه یال زیرمجموعه ای از مجموعه اصلی یال‌ها است.
درخت با رأس منبع (که محاسبات را آغاز می‌کند) به عنوان ریشه هدایت می‌شود (یعنی کانال‌ها هدایت می‌شوند).
درخت پوشا اینگونه ایجاد می شودکه یک متغیر یال اولیه به هر رأس اضافه می‌شود. هنگامی که یک رأس برای اولین بار پیامی را دریافت می‌کند، یال اولیه را با یالی که از طریق آن پیام را دریافت کرده، مقداردهی اولیه می‌کند. یال اولیه بعد از آن هرگز تغییر نمی‌کند. توجه داشته باشید که درخت پوشا منحصر به فرد نیست و به ترتیب پیام‌ها در سیستم بستگی دارد.
خاتمه توسط هر رأس در سه مرحله انجام می‌شود:
1. سیگنال‌ها را در تمام یال‌های ورودی به جز یال اول ارسال کنید. (هر رأس سیگنال‌هایی ارسال می‌کند که کمبود را در هر یال ورودی به صفر کاهش می‌دهد)
2. منتظر سیگنال‌ها از تمام یال‌های خروجی باشید. (تعداد سیگنال‌های دریافتی در هر یال خروجی، باید هر یک از کسری‌های آنها را به صفر برساند)
3. سیگنال‌ها را در یال اولیه ارسال کنید. (پس از تکمیل مراحل ۱ و ۲، یک رأس به والد خود در درخت پوشا در مورد قصد خود برای خاتمه اطلاع می‌دهد)

جستارهای وابسته

الگوریتم هوانگ

منابع

↑ Ghosh, Sukumar (2010), "9.3.1 The Dijkstra–Scholten Algorithm", Distributed Systems: An Algorithmic Approach, CRC Press, pp. 140–143, ISBN 978-1-4200-1084-8.
↑ Fokkink, Wan (2013), "6.1 Dijkstra–Scholten algorithm", Distributed Algorithms: An Intuitive Approach, MIT Press, pp. 38–39, ISBN 978-0-262-31895-2.
↑ 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.

[1] Ghosh, Sukumar (2010), "9.3.1 The Dijkstra–Scholten Algorithm", Distributed Systems: An Algorithmic Approach, CRC Press, pp. 140–143, ISBN 978-1-4200-1084-8.

[2] Fokkink, Wan (2013), "6.1 Dijkstra–Scholten algorithm", Distributed Algorithms: An Intuitive Approach, MIT Press, pp. 38–39, ISBN 978-0-262-31895-2.

[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.

[۱]

[۲]

[۳]