بخشی از پاورپوینت
--- پاورپوینت شامل تصاویر میباشد ----
اسلاید 1 :
مقدمه
در مواردي سايت‌ها بايد با هم به توافقي برسند. مثلاً تصميم به Ab rt يا C mmit در DBSs.
هر سايت بايد از مقادير سايت‌هاي ديگر مطلع باشد.
تصميم در غياب خطا ::
تصميم در حضور خطا û؟ چرا كه سايت‌هاي خطادار مقادير غلطي مي‌فرستند.
فرض: وجود يك مدل عمومي از خطا: ارسال پيغام مشكوك به ديگران، پايين بودن سايت، پاسخ درست ندادن به پيغام‌ها.
نكته: پردازه‌هاي سالم خبري از پردازه‌هاي خراب ندارند.
اسلاید 2 :
مدل
تا پردازنده در سيستم وجود دارد كه m تاي آنها خطادار هستند.
سيستم منطقاً كاملاً مرتبط است.
تنها خطاي پردازنده مطرح است و خطاي رسانه ارتباطي نداريم.
براي سادگي فرض بر توافق روي مقدار صفر و يك است.
محاسبات همگام: پردازنده‌هاي سيستم در يك حالت قفلي/مرحله‌اي عمل مي‌كنند. هر پردازه پيغامي كه در مرحله قبل ارسال شده بود را دريافت مي‌كند، محاسبه‌اي انجام مي‌دهد و پيغام‌هايي را ارسال مي‌كند.
هر مرحله را يك r u d مي‌ناميم. تأخير پيغامي يا سرعت كند يك پردازنده كل محاسبات را كند مي‌كند.
پيغام‌ها -Authe ticated هستند: پردازنده‌اي مي‌تواند پيغامي را جعل كند و يا محتويات ان را عوض كند و سپس آن را رله كند.
اسلاید 3 :
ازريابي كارايي
زمان : تعداد دور
ترافيك پيغامي
سربار حافظه‌اي
اسلاید 4 :
دسته‌بندي مسائل توافقي
1- توافق Byza ti e
مقدار اوليه‌اي كه قرار است روي آن توافق شود توسط پردازنده‌اي بي‌خطا اعلام و همه پردازنده‌هاي بي‌خطا مجبور به توافق روي آن مقدار هستند.
راه‌حل اين مسئله بايد:
1- توافق: توافق همه پردازنده‌هاي بي‌خطا روي آن مقدار مشترك.
2- اعتبار: اگر پردازنده مبدأ بي‌خطاست، مقدار توافق شده همان مقدار اوليه باشد.
نكته: اگر مبدأ خطادار باشد، پردازنده‌هاي بي‌خطا روي هر مقدار مشتركي مي‌توانند توافق كنند.
مهم نيست كه پردازنده‌هاي خطادار روي چه مقدار مشتركي توافق كرده‌اند و يا اصلاًً توافق كرده‌اند.
اسلاید 5 :
دسته‌بندي مسائل توافقي(ادامه)
2- اجماع
هر پردازنده مقدار اوليه خود را منتشر مي‌كند. همه پردازنده‌هاي بي‌خطا بايد روي مقدار مشتركي توافق كنند.
3- سازگاري محاوره‌اي(I teracti e C siste cy)
هر پردازنده مقدار اوليه خاص خود را دارد. همه پردازنده‌ها روي مجموعه يكساني توافق مي كنند.
اگر پردازنده‌اي خطا دارد (مثل j )، سپس همه پردازنده هاي بي‌خطا مي‌توانند روي هر مقدار مشترك براي j توافق داشته باشند (.( j
اسلاید 6 :
راه‌حل براي مسئله توافق Byza ti e
اولين بار توسط لمپورت
پردازنده‌ها مقاديرشان را مي‌فرستند و مقادير دريافت شده را رله مي‌كنند.
پردازنده‌هاي خطادار ممكن است بقيه را گيج كنند ( به خاطر فرستادن مقادير گمراه كننده يا رله مقادير جعلي).
مهم است كه پردازنده‌هاي بي‌خطا از خطادارها در امان باشند. تعداد خطادارها نبايد از سقفي تجاوز كند.
Pease و همكارانش نشان دادند كه اگر m (تعداد خطادارها) از تجاوز كند نمي‌توان به توافق رسيد.
اسلاید 7 :
نتيجه غيرممكن:
توافق Byza ti e نمي‌تواند بين سه پردازنده كه يكي از آنها خطادار است حاصل شود. اگر سه پردازنده P0، P1 و P2 را در نظر بگيريم كه هر يك دو مقدار صفر و يك دارند:
P0 آغاز مي‌كند. دو حالت:
1- P0 بدون خطا و مثلاً P2 خطادار است. P0 مقدار خود را پخش مي‌كند.
اسلاید 8 :
2- P0 خطادار است و P1 و P2 سالم.
با سه پردازنده كه يكي خطادار است نمي‌توان توافق داشت.
اسلاید 9 :
الگوريتم Lamp rt-Sh stak-Pease
مشهور به الگوريتم پيغام‌هاي شفاهي ral Msgs ( M(m)) كه مسئله را براي 3m+1( يا بيشتر) پردازنده در حضور حداكثر m پردازنده خطادار حل مي‌كند.
M(0)
1- پردازنده مبدأ مقدار اوليه‌اش را براي همه مي‌فرستد.
2- هر پردازنده، مقداري را كه از مبدأ گرفته است استفاده مي‌كند (اگر مقداري دريافت نكرد صفر در نظر مي گيرد).
اسلاید 10 :
الگوريتم Lamp rt-Sh stak-Pease (ادامه)
M(m) (m>0)
.1پردازنده مبدأ مقدار اوليه‌اش را براي همه مي‌فرستد.
.2براي هر i، اگر i مقداري باشد كه پردازنده از مبدأ دريافت مي‌كند (اگر دريافت نكند پيش فرض صفر است)، پردازنده i به عنوان مبدأ جديد عمل كرده و M(m-1) را آغاز مي‌كند كه i را به -2 پردازنده ديگر مي‌فرستد (به جز مبدأ و خودش).
.3براي هر i و j (i¹j) اگر j مقداري باشد كه i از j دريافت كرده است (با استفاده از M(m-1) در قدم 2)، سپس پردازنده i مقدر زير را محاسبه مي كند و به كار مي‌برد (به عنوان تصميم).
Maj r ty( 1, 2, …, -1)
