درخت پوشای مینیمم توزیع شده

مسئله درخت پوشای مینیمم توزیع شده (به انگلیسی: Distributed minimum spanning tree)، شامل درخت پوشای مینیمم توسط الگوریتم توزیع شده در شبکه (جایی که گره‌ها با عبور پیام با هم در ارتباط اند) است، اگرچه اساس این روش شبیه الگوریتم Borůvka است. یکی از کاربردهای مهم این مسئله، پیدا کردن درختی برای broadcasting (پخش کردن) استفاده می‌شود. به‌طور خاص، زمانی را که هزینه یک پیام از طریق لبه در گراف منتقل کند قابل توجه است. MST می‌تواند هزینه کل فرایند منبع برای برقراری ارتباط با تمام فرایندهای دیگر در شبکه را به حداقل برساند. این مسئله برای اولین بار در سال ۱۹۸۳ و در زمان $O(V\log V)$ توسط Gallager و همکارانش پیشنهاد شد.^[۱] که $V$ تعداد رئوس در گراف است. بعدها راه حل دیگری ارائه شد $O(V)$ ^[۲] و سرانجام^[۳]^[۴] $O({\sqrt {V}}\log ^{*}V+D)$ که D شبکه یا قطر گراف است. پیچیدگی زمانی کمتر راه حل مقید بوده‌است که در نهایت نشان داده می‌شود^[۵] $\Omega \left({\frac {\sqrt {V}}{\log V}}\right)$ .

بررسی اجمالی ویرایش

گراف ورودی $G(V,E)$ در یک شبکه در نظر گرفته شده، که رئوس $V$ گره‌ها و لبه‌های مستقل هستند. $E$ لینک‌های ارتباطی هستند. لینک‌ها مانند مسئله کلاسیک برای نمایش وزن داده شده‌است.

در آغاز الگوریتم، گره‌ها فقط وزن لینک‌هایی که به آن متصل هستند را می‌دانند.

به عنوان خروجی این الگوریتم، هر گره می‌داند کدامیک از لینک‌های خود را متعلق به درخت پوشا حداقل قرار دهد و کدام را قرار ندهد.

درخت پوشای مینیمم در گذر مدل پیام ویرایش

این مدل، یکی از رایج‌ترین مدل‌های مورد استفاده در محاسبات توزیع شده است. در این مدل، هر فرایند مانند یک گره گراف مدلسازی می‌شود. کانال‌های ارتباطی بین دو فرایند لبه گراف است.

دو الگوریتم مورد استفاده برای مسئله درخت پوشای مینیمم، الگوریتم پریم و الگوریتم کروسکال هستند. با این حال، دشوار است این دو الگوریتم در مدل توزیع پیام را به کار برد. چالش‌های اصلی عبارتند از:

هر دو الگوریتم پریم و الگوریتم کروسکال نیاز به پردازش یک گره یا راس در یک زمان دارند، ایجاد آن مشکل است که هر دو به صورت موازی با هم اجرا شوند.
هر دو الگوریتم پریم و الگوریتم کروسکال نیاز به فرایندهایی برای دانستن حالت گراف کامل دارند که کدامیک برای کشف در این مدل بسیار دشوار است.

با این حال، نوبری و همکاران^[۶] یک الگوریتم موازی PMA، پیشنهاد دادند که به موازات الگوریتم پریم است. با توجه به این مشکلات، روش‌های جدید برای الگوریتم‌های‌های MST توزیع شده در مدل گذر پیام مورد نیاز شد.

الگوریتم GHS ویرایش

الگوریتم GHS تشکیل شده‌است از Gallager, Humblet و Spira. یکی از شناخته شده‌ترین الگوریتم‌های نظریه محاسبات توزیع شده‌است. این الگوریتم می‌تواند MST را در مدل گذر پیام غیرهمزمان ایجاد کند.

پیش شرط‌ها ویرایش

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

شرح الگوریتم ویرایش

الگوریتم GHS یک سطح به هر قطعه اختصاص می‌دهد، که کدامیک یک عدد صحیح بامقدار اولیه ۰ است. هر قطعه در سطح غیر صفر یک ID(شناسه) دارد که شناسه متعلق به لبه هستهٔ هر قطعه است. در طول اجرای الگوریتم، هر گره می‌تواند هر کدام از لبه‌های خود را به سه دسته طبقه‌بندی کند

Branch، لبه‌هایی که در حال حاضر مشخص شده‌است، بخشی از MST هستند.
Rejected، لبه‌هایی که در حال حاضر مشخص شده‌است، بخشی از MST نیستند.
Basic، لبه‌ها نه لبه‌های شاخه و نه رد لبه است.

برای آگاهی دادن به قطعات سطح صفر هر گره، به شرح زیر انجام دهید:

حداقل وزن لبه آن را انتخاب کنید و مانند لبهٔ شاخه‌ها علامت‌گذاری کنید.
یک پیام از طریق لبهٔ شاخه برای اطلاع دادن به گره در طرف دیگر ارسال کنید.
برای دریافت یک پیام از طرف دیگر لبه منتظر بمانید.

لبه‌های انتخاب شده توسط هر دو گره به هسته با سطح ۱ متصل می‌شود. برای یک قطعه غیر صفر، اجرای الگوریتم را می‌توان به سه مرحله در هر سطح جدا از هم انجام داد.

منتشر کردن ویرایش

دو گره مجاور به پخش پیام‌های هسته به بقیه گره‌ها در قطعه می‌پردازند. پیام‌ها از طریق لبه شاخه، فرستاده شده‌است نه از طریق هسته. هر یک از پیام‌های پخشی شامل ID و سطح قطعه است. در پایان این مرحله، هر گره، ID و سطح قطعه جدید را دریافت کرده‌است.

convergecast ویرایش

در این مرحله، تمام گره‌ها در قطعه، برای پیدا کردن حداقل وزن لبه خروجی قطعه همکاری می‌کنند. لبه‌های خروجی، لبه‌هایی هستند که به قطعات دیگر متصل می‌شوند. پیام‌هایی که در این مرحله فرستاده می‌شوند در جهت مخالف مرحله پخش هستند. برای مقدار دهی اولیه تمام برگ‌ها (گره‌هایی که تنها یک لبهٔ شاخه دارند)، یک پیام از طریق لبهٔ شاخه فرستاده می‌شود. پیام‌هایی که حداقل وزن لبهٔ خروجی را دارند پیدا می‌شوند. راه حلی برای پیدا کردن حداقل لبه خروجی بعداً مورد بحث قرار خواهد گرفت. برای هر یک از گره‌های بدون برگ (تعدادلبه‌های شاخه آن را n در نظر بگیرید)، پس از دریافت n-1 پیام convergecast، حداقل وزن پیام انتخاب می‌شود و با وزن‌های لبه‌های خروجی مقایسه می‌شود. کمترین وزن به سمت شاخهٔ آن فرستاده می‌شود و از broadcast دریافت می‌شود.

تغییرهسته ویرایش

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

چگونه می‌توان حداقل وزن خروجی لبه را پیدا کرد؟ ویرایش

همان‌طور که در بالا بحث شد، هر گره نیاز به پیدا کردن حداقل وزن لبه خروجی پس از دریافت پیام پخش از هسته دارد. اگر گره n یک broadcast دریافت کند، می‌تواند حداقل وزن اولیهٔ لبه را انتخاب کند و یک پیام به گره n در سوی دیگر با استفاده از ID (شماره قطعه) و سطح آن ارسال کند. سپس گره n، تصمیم می‌گیرد که آیا لبه یک لبهٔ خروجی است یا نه و یک پیام برای اطلاع دادن نتیجه به گره n می‌فرستد. این تصمیم با توجه به موارد زیر گرفته می‌شود:

 (Case 1: Fragment_ID(n) = Fragment_ID(n

سپس، گره n و 'n متعلق به قطعه مشابه است.

 (Case 2: Fragment_ID(n) != Fragment_ID(n’) and Level(n) <= Level(n

سپس، گره n و 'n متعلق به قطعات مختلف است.

 (Case 3: Fragment_ID(n) != Fragment_ID(n’) and Level(n)> Level(n

نمی‌توانیم نتیجه‌گیری خاصی کنیم و دلیل آن این است در حال حاضر ممکن است دو گره به همان قطعه تعلق داشته باشد. اما گره 'n به علت تأخیر پیام broadcast هنوز این حقیقت را کشف نکرده‌است. در این حالت، الگوریتم به شما اجازه می‌دهد که گره ’n، پاسخ را تا زمانی که سطح آن بالاتر یا برابر با سطح باشد از گره n دریافت کند و به تعویق بیندازید.

چگونه می‌توان دو قطعه را باهم مقایسه کرد؟ ویرایش

فرض کنید F و’F دو قطعه‌ای باشند که می‌خواهیم به هم مقایسه کنیم؛ که به دو روش می‌توان مقایسه را انجام داد:^[۷]^[۳]

Merge: این روش زمانی استفاده می‌شود که دو قطعهٔ F و ’F، حداقل وزن لبه خروجی شان را به اشتراک بگذارند. (’Level(F) = Level(F. سطح قطعهٔ مقایسه شدهLevel(F) + 1 خواهد بود.
Absorb: این روش زمانی استفاده می‌شود که (’Level(F) <Level(F و قطعهٔ مقایسه شده و’Level F را خواهد داشت.

علاوه بر این زمانی که از "Absorb" استفاده می‌شود، F باید در حالت تغییر هسته باشد و این در صورتی است که ’F می‌تواند در حالت دلخواه باشد. به همین دلیل "Absorb" به حالتی که برای’F انتخاب می‌شود بستگی دارد. فرض کنید که e لبه‌ای است که ’F و F با n و’n دو گره متصل شده به e با هم ترکیب می‌شوند. این دو نمونه را در نظر بگیرید:

نمونه۱: گره’n، پیام broadcastرا دریافت کرده‌است اما پیام convergecast را به هسته نفرستاده‌است. در این حالت، قطعه F به سادگی می‌تواند فرایند پخش 'F بپیوندد. تصور کنید که F و 'F در حال حاضر با’’F ترکیب شده‌است؛ بنابراین می‌خواهیم حداقل وزن لبهٔ خروجی را از ’’F پیدا کنیم. به این منظور گره’n،

نمونه۲: گره 'n، یک پیام convergecast به هسته فرستاده‌است. قبل ازاینکه گره'n یک پیام convergecast بفرستد، باید حداقل وزن لبهٔ خروجی انتخاب شود. همان‌طور که در بالا بحث شد، به لبه‌های دیگر یک پیام آزمایشی می‌فرستیم و منتظر پاسخ آن می‌مانیم. فرض کنید 'e لبه انتخاب شده‌است، ما می‌توانیم به شرح زیر نتیجه‌گیری کنیم:

e’ != e
(weight(e’) <weight(e

بیشترین تعداد سطوح ویرایش

همان‌طور که در بالا ذکر شد، قطعات با "Merge" یا "Absorb" ترکیب شده‌است. "Absorb"، حداکثر سطح میان قطعات را تغییر نمی‌دهد. "Merge"، حداکثر سطح را یک واحد افزایش می‌دهد. در بدترین حالت، همه قطعات با"Merge" مقایسه می‌شود. به‌طوری‌که تعداد قطعات، حدوداً بیش از نیمی در هر سطح، کاهش می‌یابد؛ بنابراین حداکثر تعداد سطوح $O(\log V)$ ، که در آن V تعداد گره است.

الگوریتم‌های تقریبی ویرایش

الگوریتم تقریبی $O(\log n)$ توسط مالک خان و گوپال توسعه داده شد.^[۸] زمان اجرای این الگوریتم، $O(D+L\log n)$ است که $L$ که قطر کوتاه‌ترین مسیر محلی گراف است.^[۸]

منابع ویرایش

↑ Baruch Awerbuch. “Optimal Distributed Algorithms for Minimum Weight Spanning Tree, Counting, Leader Election, and Related Problems,” Proceedings of the 19th ACM Symposium on Theory of Computing (STOC), New York City, New York, May 1987.
↑ Robert G. Gallager, Pierre A. Humblet, and P. M. Spira, “A distributed algorithm for minimum-weight spanning trees,” ACM Transactions on Programming Languages and Systems, vol. 5, no. 1, pp. 66–77, January 1983.
↑ ^۳٫۰ ^۳٫۱ Nancy A. Lynch. Distributed Algorithms. Morgan Kaufmann, 1996.
↑ Shay Kutten and David Peleg, “Fast Distributed Construction of Smallk-Dominating Sets and Applications,” Journal of Algorithms, Volume 28, Issue 1, July 1998, Pages 40-66.
↑ David Peleg and Vitaly Rubinovich “A near tight lower bound on the time complexity of Distributed Minimum Spanning Tree Construction,“ SIAM Journal on Computing, 2000, and IEEE Symposium on Foundations of Computer Science (FOCS), 1999.
↑ Nobari, Sadegh; Cao, Thanh-Tung; Karras, Panagiotis; Bressan, Stéphane (2012), "Scalable parallel minimum spanning forest computation", Proceedings of the 17th ACM SIGPLAN symposium on Principles and Practice of Parallel Programming, New Orleans, Louisiana, USA: ACM (11): 205–214, doi:10.1145/2145816.2145842, ISBN 978-1-4503-1160-1, archived from the original on 18 January 2013, retrieved 9 July 2012 {{citation}}: Unknown parameter |address= ignored (|location= suggested) (help); Unknown parameter |keywords= ignored (help).
↑ Robert G. Gallager, Pierre A. Humblet, and P. M. Spira, “A distributed algorithm for minimum-weight spanning trees,” ACM Transactions on Programming Languages and Systems, vol. 5, no. 1, pp. 66–77, January 1983.
↑ ^۸٫۰ ^۸٫۱ Maleq Khan and Gopal Pandurangan. “A Fast Distributed Approximation Algorithm for Minimum Spanning Trees,” Distributed Computing, vol. 20, no. 6, pp. 391–402, Apr. 2008.

^[۱]^[۲]

↑ خطای یادکرد: خطای یادکرد:برچسب <ref>‎ غیرمجاز؛ متنی برای یادکردهای با نام Lynch وارد نشده است. (صفحهٔ راهنما را مطالعه کنید.).
↑ خطای یادکرد: خطای یادکرد:برچسب <ref>‎ غیرمجاز؛ متنی برای یادکردهای با نام GHS وارد نشده است. (صفحهٔ راهنما را مطالعه کنید.).

[1] Baruch Awerbuch. “Optimal Distributed Algorithms for Minimum Weight Spanning Tree, Counting, Leader Election, and Related Problems,” Proceedings of the 19th ACM Symposium on Theory of Computing (STOC), New York City, New York, May 1987.

[2] Robert G. Gallager, Pierre A. Humblet, and P. M. Spira, “A distributed algorithm for minimum-weight spanning trees,” ACM Transactions on Programming Languages and Systems, vol. 5, no. 1, pp. 66–77, January 1983.

[Lynch-3] ۳٫۰ ^۳٫۱ Nancy A. Lynch. Distributed Algorithms. Morgan Kaufmann, 1996.

[4] Shay Kutten and David Peleg, “Fast Distributed Construction of Smallk-Dominating Sets and Applications,” Journal of Algorithms, Volume 28, Issue 1, July 1998, Pages 40-66.

[5] David Peleg and Vitaly Rubinovich “A near tight lower bound on the time complexity of Distributed Minimum Spanning Tree Construction,“ SIAM Journal on Computing, 2000, and IEEE Symposium on Foundations of Computer Science (FOCS), 1999.

[nobari2012-6] Nobari, Sadegh; Cao, Thanh-Tung; Karras, Panagiotis; Bressan, Stéphane (2012), "Scalable parallel minimum spanning forest computation", Proceedings of the 17th ACM SIGPLAN symposium on Principles and Practice of Parallel Programming, New Orleans, Louisiana, USA: ACM (11): 205–214, doi:10.1145/2145816.2145842, ISBN 978-1-4503-1160-1, archived from the original on 18 January 2013, retrieved 9 July 2012 {{citation}}: Unknown parameter |address= ignored (|location= suggested) (help); Unknown parameter |keywords= ignored (help).

[GHS-7] Robert G. Gallager, Pierre A. Humblet, and P. M. Spira, “A distributed algorithm for minimum-weight spanning trees,” ACM Transactions on Programming Languages and Systems, vol. 5, no. 1, pp. 66–77, January 1983.

[khan-8] ۸٫۰ ^۸٫۱ Maleq Khan and Gopal Pandurangan. “A Fast Distributed Approximation Algorithm for Minimum Spanning Trees,” Distributed Computing, vol. 20, no. 6, pp. 391–402, Apr. 2008.

[Lynch-9] خطای یادکرد: خطای یادکرد:برچسب <ref>‎ غیرمجاز؛ متنی برای یادکردهای با نام Lynch وارد نشده است. (صفحهٔ راهنما را مطالعه کنید.).

[GHS-10] خطای یادکرد: خطای یادکرد:برچسب <ref>‎ غیرمجاز؛ متنی برای یادکردهای با نام GHS وارد نشده است. (صفحهٔ راهنما را مطالعه کنید.).

[۱]

[۲]

[۳]

[۴]

[۵]

[۶]

[۷]

[۸]

[۱]

[۲]