سوالهای میان ترم سیستم‌های توزیع شده

سوالها طوری نبودند که خیلی به درس کلاس مربوط باشند یعنی باید خودتان کتاب را بخوانید.

۱- الگوریتم‌های time slice و variable speed را برای انتخاب رهبر توضیح بدهید و بگویید در چه صورتی به جای اولی از دومی استفاده می‌کنیم.

۲- در مورد الگوریتم MST به این موارد جواب بدهید.

الف) مشکل وزن‌های یکسان را چطوری حل می‌کنید؟

ب) چرا زمان O(diam) برای ادغام مولفه‌ها کافی نیست؟

ج) پیچیدگی زمان و پیام الگوریتم را بنویسید.

۳- درخت EIG را برای stopping agreement رسم کنید به ازای این مثال. مثال هم این بود که اول ۱ چند تا پیام می‌فرستد و می‌میرد بعد ۲ می‌میرد و کلاً هم ۴ تا پردازنده بودند.

ب) ثابت کنید که با f راند مسئله حل نمی‌شود.

۴- شرط‌های توافق را بنویسید.

۵- چطوری می‌شود با MST رهبر انتخاب کرد؟

۶- در مسئله‌ی approximate agreement ثابت کنید هر کدام از تابع‌های reduce و select و mean چه نقشی دارند و آیا اگر نباشند باز هم جواب درست پیدا می‌شود؟