حداقل درخت پوشا توزیع شده

مثال یک MST: حداقل درخت پوششی از نمودار مسطح . هر لبه با وزن خود برچسب خورده است ، که در اینجا تقریبا متناسب با طول آن است.

حداقل توزیع درخت پوشا (MST) مشکل شامل ساخت یک درخت پوشای کمینه توسط الگوریتم توزیع شده ، در یک شبکه که در آن گره در اثر عبور پیام ارتباط برقرار کنید. این مسئله با مسئله پیگیری کلاسیک بسیار متفاوت است ، اگرچه ابتدایی ترین روش به الگوریتم Borůvka شباهت دارد . یکی از کاربردهای مهم این مشکل ، یافتن درختی است که می تواند برای پخش آن استفاده شود . به طور خاص ، اگر هزینه ارسال یک پیام از یک لبه در یک نمودار قابل توجه باشد ، یک MST می تواند هزینه کل یک فرآیند منبع را به حداقل برساند تا بتواند با تمام فرآیندهای دیگر در شبکه ارتباط برقرار کند.

ابتدا این مشکل پیشنهاد و حل شد $O (V \ log V)$ زمان در سال 1983 توسط Gallager و همکاران. ، [1] که در آن $V$ تعداد رئوس های موجود در نمودار است . بعداً ، راه حل به بهبود یافت O (V) $ا (V)$ [2] و سرانجام [3] [4] $O ({\ sqrt V} \ log ^ {*} V + D)$ جایی که D شبکه یا قطر نمودار است. سرانجام پایین بودن پیچیدگی زمان راه حل نشان داده شده است [5] . ${\ displaystyle \ Omega \ left ({{\ frac {\ sqrt {V}} {\ log V}} + D} \ right).$

فهرست

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

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

در آغاز الگوریتم ، گره ها فقط وزن پیوندهایی را که به آنها وصل شده اند می دانند. (می توان مدلهایی را در نظر گرفت که در آنها اطلاعات بیشتری کسب می کنند ، به عنوان مثال پیوندهای همسایگانشان.)

به عنوان خروجی الگوریتم ، هر گره می داند که کدام یک از پیوندهای آن متعلق به Minimum Spanning Tree و کدام یک نیست.

MST در مدل انتقال پیام [ ویرایش ]

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

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

هر دو الگوریتم پریم و الگوریتم کروسکال نیاز به پردازش یک گره یا راس در یک زمان، ساختن آن دشوار به آنها را به صورت موازی اجرا. (به عنوان مثال ، الگوریتم Kruskal به نوبه خود لبه ها را پردازش می کند ، تصمیم می گیرد که آیا لبه را در MST بگنجانید که آیا این چرخه را با تمام لبه های قبلاً انتخاب شده تشکیل می دهد.)
هر دو الگوریتم پریم و الگوریتم کروسکال لازم برای فرآیندهای به دانستن دولت تمام نمودار است که به کشف در مدل پیام عبور بسیار دشوار است.

با توجه به این مشکلات ، تکنیک های جدیدی برای الگوریتم های توزیع شده MST در مدل ارسال پیام مورد نیاز بود. برخی از شباهت ها با الگوریتم Bor forvka برای مسئله کلاسیک MST دارند.

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

الگوریتم GHS از Gallager ، Humblet و Spira یکی از الگوریتم های شناخته شده در تئوری محاسبات توزیع شده است. این الگوریتم می تواند MST را در مدل انتقال پیام ناهمزمان ایجاد کند .

پیش شرط ها [1] [ ویرایش ]

الگوریتم باید روی یک نمودار مستقر متصل نشده اجرا شود.
نمودار باید دارای وزن محدود مشخص باشد که به هر لبه اختصاص داده شده است. (این فرض را می توان با شکستن پیوندها بین وزنه های لبه به روشی ثابت حذف کرد.)
هر گره در ابتدا وزن هر حادثه لبه را به آن گره می داند.
در ابتدا ، هر گره در حالت خاموش قرار دارد و بطور خودبخود بیدار می شود یا با دریافت هر پیام از گره دیگر بیدار می شود.
پیام ها می توانند به صورت مستقل از هر دو جهت بر روی یک لبه منتقل شده و پس از یک تأخیر غیرقابل پیش بینی اما محدود ، بدون خطا وارد شوند.
هر لبه به ترتیب FIFO پیام ارسال می کند .

خواص MST [ ویرایش ]

قطعه MST T را به عنوان زیر درخت T تعریف کنید ، یعنی یک مجموعه متصل به گره ها و لبه های T وجود دارد. دو ویژگی MST وجود دارد:

با توجه به قطعه ای از MST T ، بگذارید یک لبه با حداقل وزن خروجی از قطعه باشد. سپس پیوستن e و گره غیر قطعه مجاور آن به قطعه قطعه دیگری از MST می دهد. [1]
اگر تمام لبه های یک نمودار متصل وزن های مختلفی داشته باشند ، MST نمودار منحصر به فرد است. [1]

این دو خاصیت پایه ای برای اثبات صحت الگوریتم GHS را تشکیل می دهند. به طور کلی ، الگوریتم GHS یک الگوریتم از پایین به بالا است به این معنا که با اجازه دادن به هر گره جداگانه یک قطعه و پیوستن به قطعات به روشی خاص برای تشکیل قطعات جدید شروع می شود. این روند پیوستن به قطعات تا زمانی که تنها یک قطعه باقی مانده باشد تکرار می شود و ویژگی 1 و 2 دلالت بر این دارد که قطعه حاصل MST است.

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

الگوریتم GHS یک سطح را به هر قطعه اختصاص می دهد ، که یک عدد صحیح در حال کاهش نیست با مقدار اولیه 0 است. هر قطعه سطح غیر صفر دارای یک شناسه است ، که همان شناسه لبه هسته در قطعه است ، که در هنگام قطعه انتخاب می شود. ساخته شده است در حین اجرای الگوریتم ، هر گره می تواند هر یک از لبه های حادثه خود را به سه دسته طبقه بندی کند: [1] [6]

لبه های شعبه مواردی هستند که قبلاً مشخص شده اند که بخشی از MST هستند.
لبه های رد شده مواردی هستند که قبلاً مشخص شده است که جزئی از MST نیستند.
لبه های پایه نه لبه های شاخه هستند و نه لبه های رد شده.

برای قطعات سطح 0 ، هر گره بیدار زیر را انجام می دهد:

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

لبه انتخاب شده توسط هر دو گره ای که به آن متصل می شوند هسته با سطح 1 می شود.

برای یک قطعه سطح غیر صفر ، اجرای الگوریتم را می توان در هر مرحله به سه مرحله تفکیک کرد:

پخش [ ویرایش ]

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

Convergecast [ ویرایش ]

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

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

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

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

همانطور که در بالا گفته شد ، هر گره باید بعد از دریافت پیام پخش شده از هسته ، حداقل لبه حادثه خروجی خود را پیدا کند. اگر گره n پخش را دریافت کند ، لبه اصلی وزن خود را انتخاب می کند و با شناسه و سطح قطعه آن ، پیامی را به گره n 'از طرف دیگر ارسال می کند. سپس ، گره n 'تصمیم خواهد گرفت كه لبه یك لبه خروجی باشد یا پیامی را ارسال كند تا گره n را از نتیجه آن مطلع كند. این تصمیم با توجه به موارد زیر گرفته می شود:
مورد 1 : Fragment_ID (n) = Fragment_ID (n ').
سپس گره n و n به همان قطعه تعلق دارد (بنابراین لبه خروجی نیست).
مورد 2 : Fragment_ID (n)! = Fragment_ID (n ') و سطح (n) <= سطح (n').
سپس گره n و n به قطعات مختلف تعلق دارد (بنابراین لبه در حال خروج است).
مورد 3: Fragment_ID (n)! = Fragment_ID (n ') و سطح (n)> سطح (n').
ما نمی توانیم نتیجه بگیریم. دلیل این امر این است که دو گره ممکن است متعلق به همان قطعه باشند اما گره n به دلیل تاخیر در یک پیام پخش ، این واقعیت را کشف نکرده است. در این حالت ، الگوریتم به گره n اجازه می دهد تا پاسخ را به تعویق بیندازد تا سطح آن بالاتر از یا مساوی از سطح دریافت شده از گره n باشد.

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

بگذارید F و F 'دو قطعه ای باشند که باید با هم ترکیب شوند. برای این کار دو روش وجود دارد: [1] [6]

ادغام : این عمل در صورتی اتفاق می افتد که هر دو F و F دارای یک حداقل وزن مشترک در لبه های خروجی و سطح (F) = سطح (F)) باشند. سطح قطعه ترکیبی سطح (F) + 1 خواهد بود.
Absorb : اگر سطح (F) <سطح (F ') انجام شود ، این عمل اتفاق می افتد. قطعه ترکیبی همان سطح F را خواهد داشت.

علاوه بر این ، هنگامی که یک عمل "جذب" رخ می دهد ، F باید در مرحله تغییر هسته باشد در حالی که F 'می تواند در مرحله دلخواه باشد. بنابراین ، عملیات "جذب" بسته به وضعیت F "ممکن است متفاوت انجام شود. بگذارید لبه هایی باشد که F و F می خواهند با هم ترکیب شوند و بگذارید n و n به ترتیب دو گره متصل به e در F و F باشند. دو مورد در نظر گرفته شده است:
مورد 1 : گره n 'پیام پخش شده را دریافت کرده است اما پیام همگرا را به هسته ارسال نکرده است.
در این حالت ، قطعه F به سادگی می تواند به روند پخش F 'بپیوندد. به طور خاص ، ما F و F را قبلاً ترکیب کرده ایم تا یک قطعه جدید F '' شکل بگیرد ، بنابراین می خواهیم حداقل وزن خروجی F 'را پیدا کنیم. برای انجام این کار ، گره n 'می تواند یک پخش را به F شروع کند تا شناسه قطعه هر گره را در F به روز کند و حداقل لبه وزن خروجی را در F جمع کند.
مورد 2 : Node n' قبلاً یک پیام همگرا را به هسته ارسال کرده است. .
قبل از اینکه گره n 'یک پیام همگرا ارسال کند ، باید حداقل وزن خروجی آن را انتخاب کرد. همانطور که در بالا بحث کردیم ، n 'با انتخاب حداقل وزن اصلی خود ، ارسال یک پیام آزمایشی به طرف دیگر لبه انتخاب شده و انتظار پاسخ را انجام می دهد. فرض کنید e 'لبه انتخاب شده است ، می توانیم موارد زیر را نتیجه بگیریم:

e '! = e
وزن (e ') <وزن (e)

بیانیه دوم در صورت بیان اول وجود دارد. برای اولین عبارت ، فرض کنید n 'لبه e را انتخاب کرده و یک پیام آزمایشی را از طریق edge e به n ارسال کرده است. سپس ، گره n پاسخ را به تاخیر می اندازد (مطابق مورد شماره 3 "چگونه می توان حادثه حداقل وزن را در لبه خروجی پیدا کرد؟"). بنابراین ، غیرممکن است که n 'قبلاً پیام همگرا خود را ارسال کرده باشد. با 1 و 2 می توان نتیجه گرفت که جذب F در F بی خطر است زیرا e هنوز حداقل لبه خروجی برای گزارش بعد از جذب F است.

حداکثر تعداد سطح [ ویرایش ]

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

پیشرفت ویژگی [ ویرایش ]

این الگوریتم از خواص خوبی برخوردار است که پایین ترین سطح قطعات مسدود نخواهند شد ، اگرچه ممکن است برخی از عملیات در قطعات کمترین سطح مسدود شود. این ویژگی نشان می دهد که الگوریتم در نهایت با حداقل یک درخت پوشا خاتمه می یابد.

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

یک $O (\ log n)$ الگوریتم -approximation توسط Maleq Khan و Gopal Pandurangan ساخته شده است. [7] این الگوریتم اجرا می شود $O (D + L \ log n)$ زمان ، کجا $ل$ قطر کوتاهترین مسیر محلی [7] نمودار است.