راه‌حل براي مسئله توافق Byzantine

فهرست عناوین اصلی در این پاورپوینت

فهرست عناوین اصلی در این پاورپوینت

● سیستم های عامل توزیع شده
● مقدمه
● مدل
● ازريابي كارايي
● دسته‌بندي مسائل توافقي
● دسته‌بندي مسائل توافقي(ادامه)
● راه‌حل براي مسئله توافق Byzantine
● راه‌حل براي مسئله توافق Byzantine(ادامه)
● الگوريتم Lamport-Shostak-Pease
● الگوريتم Lamport-Shostak-Pease (ادامه)
● الگوريتم Delov
● الگوريتم Delov (ادامه)
● شرح الگوريتم Delov توسط 4 قاعده زير:
● دو ويژگي الگوريتم
● الگوريتم Delov (ادامه)
● كابردهاي الگوريتم توافق
● الگوريتم Interactive Convergence( براي همگامي ساعت)
● الگوريتم Interactive Convergence(ادامه)

عبارات مهم استفاده شده در این مطلب

عبارات مهم استفاده شده در این مطلب

بی خطا, مقدار اولیه, راه حل, مسیله توافق, دسته بندی, پردازنده مبدا, پردازنده های بی, پردازنده مقدار, حل مسیله توافق, بی خطا مقدار, حضور خطا, پردازنده,

نوع زبان: فارسی حجم: 0.25 مگا بایت
نوع فایل: اسلاید پاورپوینت تعداد اسلایدها: 25 صفحه
سطح مطلب: نامشخص پسوند فایل: ppt
گروه موضوعی:  زمان استخراج مطلب: 2019/05/16 05:14:54

لینک دانلود رایگان لینک دانلود کمکی

اسلایدهای پاورپوینت مرتبط در پایین صفحه

توجه: این مطلب در تاریخ 2019/05/16 05:14:54 به صورت خودکار از فضای وب آشکار توسط موتور جستجوی پاورپوینت جمع آوری شده است و در صورت اعلام عدم رضایت تهیه کننده ی آن، طبق قوانین سایت از روی وب گاه حذف خواهد شد. این مطلب از وب سایت زیر استخراج شده است و مسئولیت انتشار آن با منبع اصلی است.

http://ce.sharif.edu/courses/86-87/1/ce534/resources/root/Slides/Agreement.ppt

در صورتی که محتوای فایل ارائه شده با عنوان مطلب سازگار نبود یا مطلب مذکور خلاف قوانین کشور بود لطفا در بخش دیدگاه (در پایین صفحه) به ما اطلاع دهید تا بعد از بررسی در کوتاه ترین زمان نسبت به حدف با اصلاح آن اقدام نماییم. جهت جستجوی پاورپوینت های بیشتر بر روی اینجا کلیک کنید.

عبارات پرتکرار و مهم در این اسلاید عبارتند از: بی خطا, مقدار اولیه, راه حل, مسیله توافق, دسته بندی, پردازنده مبدا, پردازنده های بی, پردازنده مقدار, حل مسیله توافق, بی خطا مقدار, حضور خطا, پردازنده,

مشاهده محتوای متنیِ این اسلاید ppt

مشاهده محتوای متنیِ این اسلاید ppt

سیستم های عامل توزیع شده قراردادهای توافق agreement protocols مقدمه در مواردی سایت‌ها باید با هم به توافقی برسند. مثلاً تصمیم به abort یا commit در dbss. هر سایت باید از مقادیر سایت‌های دیگر مطلع باشد. تصمیم در غیاب خطا  تصمیم در حضور خطا  چرا که سایت‌های خطادار مقادیر غلطی می‌فرستند. فرض وجود یک مدل عمومی از خطا ارسال پیغام مشکوک به دیگران، پایین بودن سایت، پاسخ درست ندادن به پیغام‌ها. نکته پردازه‌های سالم خبری از پردازه‌های خراب ندارند. قرارداد توافق پردازه رسیدن به تصمیم در حضور خطا به وسیله رله کردن چندباره‌ی اطلاعات پردازه‌ها به یکدیگر به منظور محو اثر پردازه‌های خطادار. مدل n تا‌ پردازنده در سیستم وجود دارد که m تای آنها خطادار هستند. سیستم منطقاً کاملاً مرتبط است. تنها خطای پردازنده مطرح است و خطای رسانه ارتباطی نداریم. برای سادگی فرض بر توافق روی مقدار صفر و یک است. محاسبات همگام پردازنده‌های سیستم در یک حالت قفلی مرحله‌ای عمل می‌کنند. هر پردازه پیغامی که در مرحله قبل ارسال شده بود را دریافت می‌کند، محاسبه‌ای انجام می‌دهد و پیغام‌هایی را ارسال می‌کند. هر مرحله را یک round می‌نامیم.  تأخیر پیغامی یا سرعت کند یک پردازنده کل محاسبات را کند می‌کند. پیغام‌ها non authenticated‌ هستند پردازنده‌ای می‌تواند پیغامی را جعل کند و یا محتویات ان را عوض کند و سپس آن را رله کند. ازریابی کارایی زمان تعداد دور ترافیک پیغامی سربار حافظه‌ای دسته‌بندی مسائل توافقی ۱ توافق byzantine مقدار اولیه‌ای که قرار است روی آن توافق شود توسط پردازنده‌ای بی‌خطا اعلام و همه پردازنده‌های بی‌خطا مجبور به توافق روی آن مقدار هستند. راه‌حل این مسئله باید ۱ توافق توافق همه پردازنده‌های بی‌خطا روی آن مقدار مشترک. ۲ اعتبار اگر پردازنده مبدأ بی‌خطاست، مقدار توافق شده همان مقدار اولیه باشد. نکته اگر مبدأ خطادار باشد، پردازنده‌های بی‌خطا روی هر مقدار مشترکی می‌توانند توافق کنند. مهم نیست که پردازنده‌های خطادار روی چه مقدار مشترکی توافق کرده‌اند و یا اصلاًً توافق کرده‌اند. دسته‌بندی مسائل توافقی ادامه ۲ اجماع هر پردازنده مقدار اولیه خود را منتشر می‌کند. همه پردازنده‌های بی‌خطا باید روی مقدار مشترکی توافق کنند. ۳ سازگاری محاوره‌ای interactive consistency هر پردازنده مقدار اولیه خاص خود را دارد. همه پردازنده‌ها روی مجموعه یکسانی توافق می کنند. اگر پردازنده‌ای خطا دارد مثل j ، سپس همه پردازنده های بی‌خطا می‌توانند روی هر مقدار مشترک برای j توافق داشته باشند . vj راه‌حل برای مسئله توافق byzantine اولین بار توسط لمپورت پردازنده‌ها مقادیرشان را می‌فرستند و مقادیر دریافت شده را رله می‌کنند. پردازنده‌های خطادار ممکن است بقیه را گیج کنند به خاطر فرستادن مقادیر گمراه کننده یا رله مقادیر جعلی . مهم است که پردازنده‌های بی‌خطا از خطادارها در امان باشند. تعداد خطادارها نباید از سقفی تجاوز کند. pease و همکارانش نشان دادند که اگر m تعداد خطادارها از تجاوز کند نمی‌توان به توافق رسید. راه‌حل برای مسئله توافق byzantine ادامه نتیجه غیرممکن توافق byzantine نمی‌تواند بین سه پردازنده که یکی از آنها خطادار است حاصل شود. اگر سه پردازنده p ، p۱ و p۲ را در نظر بگیریم که هر یک دو مقدار صفر و یک دارند p آغاز می‌کند. دو حالت ۱ p بدون خطا و مثلاً p۲ خطادار است. p مقدار خود را پخش می‌کند. p۱ p۲ p ۱ ۱ ۱ نمی تواند به توافق برسد. راه‌حل برای مسئله توافق byzantine ادامه ۲ p خطادار است و p۱ و p۲ سالم.  با سه پردازنده که یکی خطادار است نمی‌توان توافق داشت. p۱ p۲ p ۱ ۱ نمی تواند به توافق برسد. الگوریتم lamport shostak pease مشهور به الگوریتم پیغام‌های شفاهی oral msgs om m که مسئله را برای ۳m ۱ یا بیشتر پردازنده در حضور حداکثر m پردازنده خطادار حل می‌کند. om ۱ پردازنده مبدأ مقدار اولیه‌اش را برای همه می‌فرستد. ۲ هر پردازنده، مقداری را که از مبدأ گرفته است استفاده می‌کند اگر مقداری دریافت نکرد صفر در نظر می گیرد . الگوریتم lamport shostak pease ادامه om m m پردازنده مبدأ مقدار اولیه‌اش را برای همه می‌فرستد. برای هر i، اگر vi مقداری باشد که پردازنده از مبدأ دریافت می‌کند اگر دریافت نکند پیش فرض صفر است ، پردازنده i به عنوان مبدأ جدید عمل کرده و om m ۱ را آغاز می‌کند که vi را به n ۲ پردازنده دیگر می‌فرستد به جز مبدأ و خودش . برای هر i و j ij اگر vj مقداری باشد که i از j دریافت کرده است با استفاده از om m ۱ در قدم ۲ ، سپس پردازنده i مقدر زیر را محاسبه می کند و به کار می‌برد به عنوان تصمیم . majoroty v۱ v۲ … vn ۱ الگوریتم lamport shostak pease ادامه الگوریتم بازگشتی است و پردازنده‌ها پی در پی به گروه‌های کوچکتر شکسته می‌شوند و توافق بین انها انجام می‌شود. توافق در مرحله ۳ پس از بازگشت از recursion با تابع majority انجام می‌شود. اجرای om m باعث اجرای om m ۱ به تعداد n ۱ بار به طور جداگانه می‌شود که هر یک n ۲ بار اجرای om m ۲ را به دنبال خواهد داشت.  n ۱ n ۲ … n m ۱ بار اجرای جداگانه الگوریتم om k که k m ۱ … ۱ پیچیدگی پیغامی است. الگوریتم lamport shostak pease ادامه مثال فرض کنید ۴ پردازده p p۱ p۲ p۳ داریم که p۲ خطادار است. مثال اگر p هم خطادار باشد، مانند مثال بالاست. شکل ۵ ۸ کتاب p۱ p۲ p ۱ p۳ ۱ ۱ p ، om ۱ را اجرا می کند. p۱ p۲ p ۱ p۳ ۱ ۱ ۱ ۱ ۱ ۱ ۱ p۱وp۲وp۳، om را اجرا می کند. الگوریتم delov الگوریتم چندجمله‌ای polynomial برای توافق. الگوریتم به ۲m ۳ دور برای رسیدن به توافق لازم دارد. ساختمان داده‌ها وجود دو آستانه low m ۱، high ۲m ۱ ایده اصلی هر زیر مجموعه از پردازنده‌ها به اندازه low حداقل یک پردازنده بدون خطا دارند می‌توان پردازنده‌های خطادار را از معرفی یک مقدار خطا مانع شد چرا که حداقل low‌ تا پردازنده باید روی یک مقدار تفاهم داشته باشند. به علاوه هر زیرمجموعه high تایی شامل یک حداکثر m ۱ تایی پردازنده بدون خطاست.  هر ادعایی که به وسیله high تا پردازنده تأئید شود می‌توان گفت روی آن توافقی وجود دارد. الگوریتم delov ادامه دو نوع پیغام ‘ ’ …

کلمات کلیدی پرکاربرد در این اسلاید پاورپوینت: بی خطا, مقدار اولیه, راه حل, مسیله توافق, دسته بندی, پردازنده مبدا, پردازنده های بی, پردازنده مقدار, حل مسیله توافق, بی خطا مقدار, حضور خطا, پردازنده,

این فایل پاورپوینت شامل 25  اسلاید و به زبان فارسی و حجم آن 0.25 مگا بایت است. نوع قالب فایل ppt بوده که با این لینک قابل دانلود است. این مطلب برگرفته از سایت زیر است و مسئولیت انتشار آن با منبع اصلی می باشد که در تاریخ 2019/05/16 05:14:54 استخراج شده است.

http://ce.sharif.edu/courses/86-87/1/ce534/resources/root/Slides/Agreement.ppt

  • جهت آموزش های پاورپوینت بر روی اینجا کلیک کنید.
  • جهت دانلود رایگان قالب های حرفه ای پاورپوینت بر روی اینجا کلیک کنید.

رفتن به مشاهده اسلاید در بالای صفحه


پاسخی بگذارید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *