موضوع مقاله: درخت پوشای مینیمم توزیع شده | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # درخت پوشای مینیمم توزیع شده | مقدمه: مسئله درخت پوشای مینیمم توزیع شده ، شامل درخت پوشای مینیمم توسط الگوریتم توزیع شده در شبکه (جایی که گره‌ها با عبور پیام با هم در ارتباط اند) است، اگرچه اساس این روش شبیه الگوریتم Borůvka است. | ## بخش 1: درخت پوشای مینیمم توزیع شده | به‌طور خاص، زمانی را که هزینه یک پیام از طریق لبه در گراف منتقل کند قابل توجه است. MST می‌تواند هزینه کل فرایند منبع برای برقراری ارتباط با تمام فرایندهای دیگر در شبکه را به حداقل برساند. بررسی اجمالی گراف ورودی در یک شبکه در نظر گرفته شده، که رئوس گره‌ها و لبه‌های مستقل هستند. به عنوان خروجی این الگوریتم، هر گره می‌داند کدامیک از لینک‌های خود را متعلق به درخت پوشا حداقل قرار دهد و کدام را قرار ندهد. درخت پوشای مینیمم در گذر مدل پیام این مدل، یکی از رایج‌ترین مدل‌های مورد استفاده در محاسبات توزیع شده است. دو الگوریتم مورد استفاده برای مسئله درخت پوشای مینیمم، الگوریتم پریم و الگوریتم کروسکال هستند. چالش‌های اصلی عبارتند از: هر دو الگوریتم پریم و الگوریتم کروسکال نیاز به پردازش یک گره یا راس در یک زمان دارند، ایجاد آن مشکل است که هر دو به صورت موازی با هم اجرا شوند. هر دو الگوریتم پریم و الگوریتم کروسکال نیاز به فرایندهایی برای دانستن حالت گراف کامل دارند که کدامیک برای کشف در این مدل بسیار دشوار است. با توجه به این مشکلات، روش‌های جدید برای الگوریتم‌های‌های MST توزیع شده در مدل گذر پیام مورد نیاز شد. در ابتدا، هر گره در یک حالت ساکن بوده یا خود به خود فراخوانی می‌شود یا دریافت هر پیام از دیگر گره ایجاد می‌شود. | ## بخش 2: درخت پوشای مینیمم توزیع شده | پیام‌ها را می‌توان به‌طور مستقل در هر دو جهت بر روی یک لبه انتقال داد و بعد از تأخیر غیرقابل پیش‌بینی اما محدود و بدون خطا به مقصد رساند. شرح الگوریتم الگوریتم GHS یک سطح به هر قطعه اختصاص می‌دهد، که کدامیک یک عدد صحیح بامقدار اولیه ۰ است. هر قطعه در سطح غیر صفر یک ID(شناسه) دارد که شناسه متعلق به لبه هستهٔ هر قطعه است. در طول اجرای الگوریتم، هر گره می‌تواند هر کدام از لبه‌های خود را به سه دسته طبقه‌بندی کند Branch، لبه‌هایی که در حال حاضر مشخص شده‌است، بخشی از MST هستند. برای آگاهی دادن به قطعات سطح صفر هر گره، به شرح زیر انجام دهید: حداقل وزن لبه آن را انتخاب کنید و مانند لبهٔ شاخه‌ها علامت‌گذاری کنید. برای یک قطعه غیر صفر، اجرای الگوریتم را می‌توان به سه مرحله در هر سطح جدا از هم انجام داد. برای مقدار دهی اولیه تمام برگ‌ها (گره‌هایی که تنها یک لبهٔ شاخه دارند)، یک پیام از طریق لبهٔ شاخه فرستاده می‌شود. برای هر یک از گره‌های بدون برگ (تعدادلبه‌های شاخه آن را n در نظر بگیرید)، پس از دریافت n-1 پیام convergecast، حداقل وزن پیام انتخاب می‌شود و با وزن‌های لبه‌های خروجی مقایسه می‌شود. تغییرهسته پس از اتمام مرحله قبل، دو گره متصل شده به هسته می‌توانند همدیگر را از بهترین لبه‌هایی که دریافت کرده‌اند، مطلع کنند. پیام از هسته با یک مسیر از لبه‌های شاخه به حداقل لبهٔ خروجی فرستاده می‌شود و در نهایت پیام به لبهٔ خروجی انتخاب شده برای مقایسه دو قطعه که لبه‌هایشان به هم متصل اند فرستاده می‌شود. | ## بخش 3: درخت پوشای مینیمم توزیع شده | بسته به نوع سطح دو قطعه، یکی از دو قطعه با عملیات ترکیبی به شکل یک قطعه جدید انجام می‌شود. همان‌طور که در بالا بحث شد، هر گره نیاز به پیدا کردن حداقل وزن لبه خروجی پس از دریافت پیام پخش از هسته دارد. سپس گره n، تصمیم می‌گیرد که آیا لبه یک لبهٔ خروجی است یا نه و یک پیام برای اطلاع دادن نتیجه به گره n می‌فرستد. در این حالت، الگوریتم به شما اجازه می‌دهد که گره ’n، پاسخ را تا زمانی که سطح آن بالاتر یا برابر با سطح باشد از گره n دریافت کند و به تعویق بیندازید. فرض کنید F و’F دو قطعه‌ای باشند که می‌خواهیم به هم مقایسه کنیم؛ که به دو روش می‌توان مقایسه را انجام داد:Robert G. Merge: این روش زمانی استفاده می‌شود که دو قطعهٔ F و ’F، حداقل وزن لبه خروجی شان را به اشتراک بگذارند. علاوه بر این زمانی که از "Absorb" استفاده می‌شود، F باید در حالت تغییر هسته باشد و این در صورتی است که ’F می‌تواند در حالت دلخواه باشد. فرض کنید که e لبه‌ای است که ’F و F با n و’n دو گره متصل شده به e با هم ترکیب می‌شوند. تصور کنید که F و 'F در حال حاضر با’’F ترکیب شده‌است؛ بنابراین می‌خواهیم حداقل وزن لبهٔ خروجی را از ’’F پیدا کنیم. همان‌طور که در بالا بحث شد، به لبه‌های دیگر یک پیام آزمایشی می‌فرستیم و منتظر پاسخ آن می‌مانیم. | ## جمع‌بندی | به‌طوری‌که تعداد قطعات، حدوداً بیش از نیمی در هر سطح، کاهش می‌یابد؛ بنابراین حداکثر تعداد سطوح ، که در آن V تعداد گره است.