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

۳.۱ جزئیات دقیق‌تر اثبات درستی الگوریتم 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