CME 323: Distributed Algorithms and Optimization

https://stanford.edu/~rezab/dao/

اسلایدهای توزیع‌شده‌ی ETH

http://www.dcg.ethz.ch/lectures/podc/

انیمیشن و اسلاید برای توزیع شده و سیستم عامل پیشرفته

http://slides.com/rezamohammadi/concurrent-computing#/

http://thesecretlivesofdata.com/raft/

خوبیش سایت ساختن اسلایدهای این طوری است:
https://slides.com/pricing?ref=caplt

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

۱- تعریف فرمال trace property, progress, liveness را بنویسید.
آیا یک ویژگی می‌تواند همزمان progress و liveness باشد؟
ثابت کنید هر trace property را به صورت اشتراک یک safety property و یک trace property می‌توان نوشت. (قضیه 8.9 کتاب)
۲- تمرین 8.5 کتاب
۳- الگوریتم Peterson2P را بنویسید و ثابت کنید درست کار می‌کند و شرط lockout freedom را ارضا می‌کند. (قضیه 10.13 کتاب)
۴- الگوریتم LCR و Peterson برای انتخابا رهبر را بنویسید و مقایسه کنید (کدام در چه شرایطی بهتر است؟ چرا؟) و پیچیدگی پیام و زمان آن را هم حساب کنید.
۵- سوال 7.11 کتاب (تکراری از میان ترم)
۶- سوال 7.17 کتاب (تکراری از تمرین‌ها)

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

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

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

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

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

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

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

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

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

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

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

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

O(n log n) unidirectional distributed algorithm for leader election in a ring

https://www.cs.huji.ac.il/~dolev/pubs/n-log-n.pdf

HS algorithm

http://cse.iitkgp.ac.in/~agupta/distcomp/LeaderElection-HirschbergSinclair.pdf

الگوریتم توزیع‌شده‌ی انتخاب رهبر روی حلقه یک طرفه

http://www.cs.rug.nl/~eirini/DS_slides/leader_election.pdf

Leader Election in rings - All nodes are equal, but some are more equal than others

حل تمرین‌های کتاب لینچ فصل ۳

۳.۱ جزئیات دقیق‌تر اثبات درستی الگوریتم LCR را بنویسید.

الگوریتم LCR برای انتخاب رهبر در یک حلقه در مدل سنکرون است. اسم الگوریتم از اول اسم آدمهایی که پیدایش کردند می‌آید و معنی خاصی ندارد. این الگوریتمی است که با O(n^2) پیام رهبر را پیدا می‌کند.

اولین جای خالی که در اثبات کتاب هست استقرا برای اثبات این است که در راند r پردازنده‌ی (i_max+r) mod n شناسه‌ی u_max را دارد.

پایه استقرا: در راند ۰ شناسه‌ی u_max در i_max است پس حکم برقرار است.

فرض استقرا: برای راند r حکم برقرار است.

حکم استقرا: برای راند r+1 که r+1<n است حکم برقرار است.

اثبات: در راند r پردازنده‌ی (i_max+r) mod n شناسه بزرگترین را داشته است که در آن راند روی خروجی خودش قرار داده است. پس در شروع راند r+1 در ورودی پردازنده‌ی بعدی آن یعنی (i_max+r+1) mod n هست. در راند r+1 این پردازنده ورودی‌اش را دریافت می‌کند پس شناسه‌ی ماکسیمم در این پردازنده خواهد بود.

البته فکر کنم منظورش فرمال بوده که در این صورت:

incoming = u_max است. طبق تابع انتقال مقدار آن با u پردازنده (i_max+r+1) mod n مقایسه می‌شود چون u_max است حتماً بزرگتر خواهد بود پس send این پردازنده مقدار u_max را می‌گیرد.

اثبات قسمت دیگر: در راند r=n-1 چه اتفاقی می‌افتد که باعث می‌شود در راند n جواب پیدا شده باشد.

طبق لم ۲ (که الآن اثبات کردیم) در راند n-1 پردازنده‌ی (i_max+n-1( mod n شناسه‌ی ماکسیمم را در send اش دارد. در راند n پردازنده‌ی (i_max+n-1+1( mod n یعنی همان i_max شناسه‌ی u_max را دریافت می‌کند. طبق تابع transition با تشخیص مساوی بودن این شناسه با شناسه‌ی خودش، خودش را به عنوان رهبر انتخاب می‌کند (status خودش را leader می‌کند).

لم ۳: پس از r راند، اگر i <> i_max باشد و j هر پردازنده در بازه‌ی [i_max,i) باشد (بازه برعکس افتاد به دلیل تایپ، ولی مساوی i_max می‌تواند باشد و شامل i نیست)، آنگاه send پردازنده j شامل u_i نیست.

اثبات با استقرا.

پایه استقرا: در راند ۰، هیچ پردازنده‌ای به جز i مقدار u_i در send اش نیست. (شناسه‌ها متمایزند)

فرض استقرا: برای راند r

حکم استقرا: برای راند r+1

طبق فرض استقرا در راند r هیچ پردازنده‌ j در بازه‌ی [i_max,i) در send اش u_i نبوده است. در راند r+1 در send هر پردازنده [i_max,i+1