سلام خدمت تمام مهندسان گرامی و انشالله همیشه سلامت باشین...
چندتا سوال داشتم خدمتتون اگه بتونین جواب بدین واقعا ممنون میشم.چون واقعا در این مبحث به مشکل خوردم ..(البته تعداد سوالات زیاد هستش با عرض پوزش)..اجرتون با الله
1:آیا در الگوریتم LCR در حالت میانگین تعداد پیام های ارسالی از مرتبه ی (n log n(O می باشد؟
2:چه تغییری در الگوریتم HSباعث میشود که برای حلقه ی یکطرفه با پیچیدگی پیام (n log n(O کار کند؟
3: آیا الگوریتم HS برای مدل هم گام با زمان های شروع گوناگون نیز به درستی کار می کند؟
4:در الگوریتم FLOODMAX OPT ، آیا خانواده ای از گراف های جهت دار وجود دارد که نیاز به (Ω(n 3 پیام دارد یا کران پایین بهتری برای آن سراغ دارید؟
5:نسخه ای از FLOODMAX OPT را در نظر بگیرید که تنها تغییر آن نسبت به الگوریتم اصلی در این است که از ارسال مجدّد uid − max به پروسه ای که از آن این مقدار را دریافت کرده است، خودداری می کند. با استفاده از روش رابطه ی شبیه سازی درستی این الگوریتم را اثبات کنید.
6: آیا در یک حلقه ی ناشناس که در آن پروسه ها کار را خود را با مقادیر دودویی آغار می کنند،الگوریتم یکنواختی برای محاسبه عمل بیتی AND وجود دارد؟
7: با فرض شرط غیریکواخت بودن، الگوریتمی ارائه دهید که عمل بیتی AND این مقادیر دودویی را محاسبه کند. این الگوریتم باید در بدترین حالت (n(O پیام ارسال کند.
8:یک حلقه ی دوطرفه ی یکنواخت را که در آن هر کدام از پروسه ها شناسه ی منحصر بفرد دارند را در نظر بگیرید. می خواهیم مسئله ی محاسبه ی 2 mod n را در حالت توزیع شده حل کنیم (منظور این است که در پایان هر کدام از پروسه ها این مقدار را بدانند). الگوریتم و کران پایینی برای تعداد پیام های ارسالی ارائه کنید. الگوریتم ارائه شده مجاز است که تنها از مقایسه استفاده کند.