دانلود پاورپوینت تجزیه و تحلیل سیستم عامل های  توزیع شده در قراردادهای توافق  Agreement Protocols

\n

عنوان قبلی : سیستم های عامل توزیع شده

\n

\n

عنوان های پاورپوینت  : 

\n

\n

\n

مقدمه

\n

مدل

\n

ازریابی کارایی

\n

دستهبندی مسائل توافقی

\n

دستهبندی مسائل توافقی(ادامه)

\n

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

\n

راهحل برای مسئله توافق Byzantine(ادامه)

\n

راهحل برای مسئله توافق Byzantine(ادامه)

\n

الگوریتم Lamport-Shostak-Pease

\n

الگوریتم Lamport-Shostak-Pease (ادامه)

\n

الگوریتم Lamport-Shostak-Pease (ادامه)

\n

الگوریتم Lamport-Shostak-Pease (ادامه)

\n

الگوریتم Delov

\n

الگوریتم Delov (ادامه)

\n

الگوریتم Delov (ادامه)

\n

الگوریتم Delov (ادامه)

\n

الگوریتم Delov (ادامه)

\n

شرح الگوریتم Delov توسط 4 قاعده زیر:

\n

دو ویژگی الگوریتم

\n

الگوریتم Delov (ادامه)

\n

الگوریتم Delov (ادامه)

\n

کابردهای الگوریتم توافق

\n

الگوریتم  Interactive Convergence( برای همگامی ساعت)

\n

الگوریتم Interactive Convergence(ادامه)

\n \n\n \n\n

---

\n\nقسمت ها و تکه های اتفاقی از فایل\n\n \n\nتجزیه و تحلیل سیستم عامل های  توزیع شده\n\nدر قراردادهای توافق\n\nAgreement Protocols\n\n \n\n \n\n2pro.ir\n\nسیستم های عامل توزیع شده\n\nقراردادهای توافق Agreement Protocols\n\nمقدمه\n\nدر مواردی سایت‌ها باید با هم به توافقی برسند. مثلاً تصمیم به Abort یا Commit در DBSs.\n\nهر سایت باید از مقادیر سایت‌های دیگر مطلع باشد.\n\nتصمیم در غیاب خطا :: \n\nتصمیم در حضور خطا ؟ چرا که سایت‌های خطادار مقادیر غلطی می‌فرستند.\n\n \n\n \n\n \n\n \n\nفرض: وجود یک مدل عمومی از خطا: ارسال پیغام مشکوک به دیگران، پایین بودن سایت، پاسخ درست ندادن به پیغام‌ها.\n\nنکته: پردازههای سالم خبری از پردازههای خراب ندارند.\n\n \n\nمدل\n\nn تا‌ پردازنده در سیستم وجود دارد که m تای آنها خطادار هستند.\n\nسیستم منطقاً کاملاً مرتبط است.\n\nتنها خطای پردازنده مطرح است و خطای رسانه ارتباطی نداریم.\n\nبرای سادگی فرض بر توافق روی مقدار صفر و یک است.\n\nمحاسبات همگام: پردازندههای سیستم در یک حالت قفلی/مرحلهای عمل می‌کنند. هر پردازه پیغامی که در مرحله قبل ارسال شده بود را دریافت می‌کند، محاسبهای انجام می‌دهد و پیغام‌هایی را ارسال می‌کند.\n\nهر مرحله را یک round می‌نامیم.  تأخیر پیغامی یا سرعت کند یک پردازنده کل محاسبات را کند می‌کند.\n\nپیغام‌ها non-Authenticated هستند: پردازندهای می‌تواند پیغامی را جعل کند و یا محتویات ان را عوض کند و سپس آن را رله کند.\n\n \n\nازریابی کارایی\n\nزمان : تعداد دور\n\n \n\nترافیک پیغامی\n\n \n\nسربار حافظهای\n\nدستهبندی مسائل توافقی\n\n1- توافق Byzantine\n\nمقدار اولیهای که قرار است روی آن توافق شود توسط پردازندهای بی‌خطا اعلام و همه پردازندههای بی‌خطا مجبور به توافق روی آن مقدار هستند.\n\nراهحل این مسئله باید:\n\n1- توافق: توافق همه پردازندههای بی‌خطا روی آن مقدار مشترک.\n\n2- اعتبار: اگر پردازنده مبدأ بی‌خطاست، مقدار توافق شده همان مقدار اولیه باشد.\n\nنکته: اگر مبدأ خطادار باشد، پردازندههای بی‌خطا روی هر مقدار مشترکی می‌توانند توافق کنند.\n\nمهم نیست که پردازندههای خطادار روی چه مقدار مشترکی توافق کردهاند و یا اصلاًً توافق کردهاند.\n\nدستهبندی مسائل توافقی(ادامه)\n\n2- اجماع\n\nهر پردازنده مقدار اولیه خود را منتشر می‌کند. همه پردازندههای بی‌خطا باید روی مقدار مشترکی توافق کنند.\n\n3- سازگاری محاورهای(Interactive Consistency)\n\nهر پردازنده مقدار اولیه خاص خود را دارد. همه پردازندهها روی مجموعه یکسانی توافق می کنند.\n\nاگر پردازندهای خطا دارد (مثل j )، سپس همه پردازنده های بی‌خطا می‌توانند روی هر مقدار مشترک برای j توافق داشته باشند (.(Vj\n\nراهحل برای مسئله توافق Byzantine\n\nاولین بار توسط لمپورت\n\nپردازندهها مقادیرشان را می‌فرستند و مقادیر دریافت شده را رله می‌کنند.\n\nپردازندههای خطادار ممکن است بقیه را گیج کنند ( به خاطر فرستادن مقادیر گمراه کننده یا رله مقادیر جعلی).\n\nمهم است که پردازندههای بی‌خطا از خطادارها در امان باشند. تعداد خطادارها نباید از سقفی تجاوز کند.\n\nPease و همکارانش نشان دادند که اگر m (تعداد خطادارها) از           تجاوز کند نمی‌توان به توافق رسید.\n\nراهحل برای مسئله توافق Byzantine(ادامه)\n\nنتیجه غیرممکن:\n\nتوافق Byzantine نمی‌تواند بین سه پردازنده که یکی از آنها خطادار است حاصل شود. اگر سه پردازنده P0، P1 و P2 را در نظر بگیریم که هر یک دو مقدار صفر و یک دارند:\n\nP0 آغاز می‌کند. دو حالت:\n\n1-  P0 بدون خطا و مثلاً P2 خطادار است. P0 مقدار خود را پخش می‌کند.\n\n \n\nراهحل برای مسئله توافق Byzantine(ادامه)\n\n2-  P0 خطادار است و P1 و P2 سالم.\n\n \n\n \n\n \n\n \n\n \n\n \n\n با سه پردازنده که یکی خطادار است نمی‌توان توافق داشت.\n\nالگوریتم Lamport-Shostak-Pease\n\nمشهور به الگوریتم پیغام‌های شفاهی Oral Msgs (OM(m)) که مسئله را برای 3m+1( یا بیشتر) پردازنده در حضور حداکثر m پردازنده خطادار حل می‌کند.\n\n \n\nOM(0)\n\n1- پردازنده مبدأ مقدار اولیهاش را برای همه می‌فرستد.\n\n2- هر پردازنده، مقداری را که از مبدأ گرفته است استفاده می‌کند (اگر مقداری دریافت نکرد صفر در نظر می گیرد).\n\nالگوریتم Lamport-Shostak-Pease (ادامه)\n\nOM(m) (m>0)\n\nپردازنده مبدأ مقدار اولیهاش را برای همه می‌فرستد.\n\nبرای هر i، اگر vi مقداری باشد که پردازنده از مبدأ دریافت می‌کند (اگر دریافت نکند پیش فرض صفر است)، پردازنده i به عنوان مبدأ جدید عمل کرده و OM(m-1) را آغاز می‌کند که vi را به n-2 پردازنده دیگر می‌فرستد (به جز مبدأ و خودش).\n\nبرای هر i و j (ij) اگر vj مقداری باشد که i از j دریافت کرده است (با استفاده از OM(m-1) در قدم 2)، سپس پردازنده i مقدر زیر را محاسبه می کند و به کار می‌برد (به عنوان تصمیم).\n\nMajoroty(v1, v2, …, vn-1)\n\n \n\nالگوریتم Lamport-Shostak-Pease (ادامه)\n\nالگوریتم بازگشتی است و پردازندهها پی در پی به گروههای کوچکتر شکسته می‌شوند و توافق بین انها انجام می‌شود. توافق در مرحله 3 (پس از بازگشت از recursion با تابع majority) انجام می‌شود.\n\nاجرای OM(m) باعث اجرای OM(m-1) به تعداد n-1 بار (به طور جداگانه) می‌شود که هر یک n-2 بار  اجرای OM(m-2) را به دنبال خواهد داشت.\n\n(n-1)(n-2)…(n-m+1)\n\nبار اجرای جداگانه الگوریتم OM(k) که k=m-1, …,1,0\n\nالگوریتم Lamport-Shostak-Pease (ادامه)\n\nمثال: فرض کنید 4 پردازده P0, P1, P2, P3 داریم که p2 خطادار است.\n\n \n\n \n\n \n\n \n\n \n\n \n\n \n\n \n\n \n\n \n\nمثال: اگر P0 هم خطادار باشد، مانند مثال بالاست. (شکل 5-8 کتاب)\n\nالگوریتم Delov\n\nالگوریتم چندجملهای (polynomial) برای توافق. الگوریتم به 2m+3 دور برای رسیدن به توافق لازم دارد.\n\nساختمان دادهها\n\nوجود دو آستانه Low=m+1، High=2m+1\n\n \n\nایده اصلی\n\nهر زیر مجموعه از پردازندهها به اندازه Low حداقل یک پردازنده بدون خطا دارند می‌توان پردازندههای خطادار را از معرفی یک مقدار خطا مانع شد چرا که حداقل Low تا پردازنده باید روی یک مقدار تفاهم داشته باشند.\n\nبه علاوه هر زیرمجموعه High تایی شامل یک حداکثر m+1 تایی پردازنده بدون خطاست.  هر ادعایی که به وسیله High تا پردازنده تأئید شود می‌توان گفت روی آن توافقی وجود دارد.\n\nالگوریتم Delov (ادامه)\n\nدو نوع پیغام:\n\n‘*’ مشخص کننده ارسال ‘1’ توسط فرستنده.\n\n \n\nپیغام حاوی نام پردازنده: معرف این که فرستنده پیغام ‘*’ را از پردازنده مشخص شده در پیغام دریافت کرده است.\n\n(در هر دو نوع پیغام، نام فرستنده پیغام وجود دارد.)\n\n \n\nهر پردازنده رکوردی از همه پیغام‌های دریافت شدهاش را نگه می‌دارد.\n\nالگوریتم Delov (ادامه)\n\nفرض           مجموعه پردازندههایی باشد که x را به i فرستادهاند.  هر پردازنده n+1 تا مجموعه W نگه می‌دارد (یکی برای ‘*’ و n تا برای پردازندهها).\n\n \n\n \n\n \n\n \n\nپردازنده j یک پشتیبان مستقیم پردازنده k است اگر j مستقیماً یک ‘*’ از k دریافت کرده باشد.\n\nوقتی j (بی‌خطا)،   ‘*’ را مستقیماً از k دریافت کند، پیغام “k” را به همه دیگر پردازهها می‌فرستد.\n\nوقتی i، پیغام “k” را از j دریافت کرد، j را به می‌افزاید چرا که j شاهدی است برای “k”.\n\nپردازنده j یک پشتیبان غیرمستقیم k است اگر                           . یعنی j پیغام “k” را از حداقل Low تا پردازنده دریافت کرده است.\n\nپردازنده j، پردازنده k را تأئید می‌کند (Confirm) اگر\n\nپردازنده i، مجموعه Ci را از پردازندههای تآئید شدهاش نگه می‌دارد.\n\n \n\n \n\n \n\nالگوریتم Delov (ادامه)\n\nالگوریتم:\n\nدر دور اول، اگر مقدار مبدأ یک است، مبدأ “*” را به همه (حتی خودش) می‌فرستد. در غیر این صورت چیزی نمی‌فرستد.\n\nاگر در نهایت پردازندهها روی ”*“ تفاهم کردند مقدار توافق شده 1  و در غیر این صورت صفر است.\n\nالگوریتم Delov (ادامه)\n\nالگوریتم(ادامه):\n\nدر دورهای بعدی، پردازندهها پیغام‌های خود را برای دیگران می‌فرستند، دریافت هم می‌کنند و تصمیم می‌گیرند چه پیغامی را بفرستند( در دور بعدی).\n\nوقتی j (بی‌خطا) پیغام “*”‌ را از k دریافت می‌کند پیغام “k” را در دور بعدی به همه دیگر پردازهها می‌فرستد. مشخص می‌کند که پشتیبان مستقیم “k” است.\n\nیک پردازنده تحت شرایط زیر initiation می‌کند، یعنی پیغام “*” را به دیگران می‌فرستد:\n\nیک پردازنده در دور دوم initiate می‌کند اگر یک “*” در دور اول از مبدأ دریافت کرده باشد.\n\nیک پردازنده در دور k+1ام initiateمی‌کند اگر در انتهای دور kام تعداد پردازندههای تأئید شده (غیر از مبدأ) حداقل LOW+max(0,k/2-2) باشد. شرط آغازیندهی\n\n \n\nشرح الگوریتم Delov توسط 4 قاعده زیر:\n\nدر دور اول مبدأ مقدار خودرا به همه دیگر پردازهها منتشر می‌کند.\n\nدر دور K>1،  یک پردازنده نام همه پردازندههایی که این پردازنده پشتیبان مستقیم یا غیر مستقیم آنهاست را به همه (به جز آنها که قبلاً منتشر کرده است) منتشر می‌کند. اگر در انتهای دور قبلی شرایط آغازین درست باشد و قبلاً پیغام “*” منتشر نکرده باشد، پیغام “*”‌را منتشر می‌کند.\n\nاگر پردازندهای تعداد HIGH تا از پردازندهها را تأئید کرد، مقدار 1 را به عنوان مقدار committed در نظر می‌گیرد.\n\nبعد از 2m+3 دور، اگر مقدار commit شده 1 باشد همه پردازندهها روی 1 و گرنه روی صفر توافق می‌کنند.\n\n \n\nدو ویژگی الگوریتم\n\nآغاز\n\nCommit :: شرطش HIGH تا پردازنده را تأئید کند :: هر یک از این HIGH تا شاهد بودهاند که HIGH تا پردازنده “*” را ارسال کردهاند.\n\nدر هر HIGH تا پردازنده، حداقل m+1 تا پردازنده بدون خطا وجود دارد : پردازندهای commit می‌کند اگر مشخص کند که حداقل m+1 پردازنده بدون خطا شاهد بودهاند که حداقل m+1 پردازنده بدون خطای تأئید شده یک “*” فررستاده اند :: m+1 پردازنده بدون خطا initiate شدهاند.\n\nآغازیندهی مکرر باعث تفوق پردازندههای بی‌خطا بر پردازندههای خطادار می‌شود. چنانچه پردازندهای در دور اول “*” را از مبدأ دریافت کند در دور دوم initiate می‌کند.\n\nدر صورتی یک پردازنده می‌تواند در دور >1، initiate کند که که تعداد قابل توجهی پردازنده را تأئید کرده باشد. این عدد برای چهار دور اول LOW است و سپس به ازاء هر دو دور یک واحد به آن عدد اضافه می‌شود.\n\nالگوریتم Delov (ادامه)\n\nمثال: اگر 3m+1 تا پردازنده داشته باشیم که mتای آنها خطادار باشند و فرض کنیم که مبدأ بی‌خطاست :: در دور اول مبدأ “*” را منتشر می‌کند.\n\nدر دور دوم 2m تا پردازنده بی‌خطا “*” را منتشر می‌کنند.\n\nدر دور سوم 2m+1 تا پردازنده بی‌خطا (شامل مبدأ) پیغام‌هایی پخش می‌کنند که نام آن پردازندهها (پشتیبان مستقیم) را پخش می‌کند.  اطلاع می‌دهند که انها شاهد بودهاند ارسال “*” به وسیله 2m پردازنده بی‌خطای دیگر را.  در چهارمین دور، مجموعه شاهدین همهی 2m+1 پردازنده بی‌خطا، شامل همهی 2m+1پردازنده بی‌خطا خواهد بود.  همه در دور چهارم به ”!“ commit خواهند کرد.\n\nالگوریتم Delov (ادامه)\n\nاگر مبدأ خطادار باشد، ممکن است “*” را به تعداد کمی پردازنده بفرستد.  همه کسانی که “*” را دریافت کردهاند (بی‌خطاها)، در دور دوم initiate خواهند کرد. مادام که LOW تا بی‌خطا initiate نکرده باشند تضمینی وجود ندارد که Confirm Set یک پردازنده به LOW برسد و باعث initialization در دیگر بی‌خطاها بشود.\n\nکابردهای الگوریتم توافق\n\nهمگامی متحمل خطای ساعت فیزیکی : هر ساعت محلی یک انحرافی دارد که مرتباً باید این همگامی تجدید شود.\n\nفرض در مورد سیستم:\n\nA1- در آغاز همه ساعت‌ها با مقدار یکسانی همگام شدهاند.\n\nA2- ساعت یک پردازنده بی‌خطا تقریباً با نرخ درستی کار می‌کند.\n\nA3- پردازنده بی‌خطا، ساعت دیگری را با حداکثر یک خطای  می‌تواند بخواند.\n\nدو شرط برای یک الگوریتم همگامی ساعت:\n\n1- در هر زمان مقادیر ساعت‌های پردازندههای بی‌خطا تقریباً مساوی باشد.\n\n2- در طی هر همگامی، ساعت‌های پردازندههای بی‌خطا در یک محدودهی کوچک تغییر می‌کنند.\n\nالگوریتم  Interactive Convergence( برای همگامی ساعت)\n\nقرار است همگامی طوری صورت گیرد که دو ساعت بی‌خطا هیچگاه اختلافی بیش از   نداشته باشند.\n\nهر پردازنده مقدار ساعت دیگران را می‌خواند و ساعت خود را به عنوان میانگین آنها تنظیم می‌کند. اگر مقدار ساعتی اختلافی بیش از  با ساعت خودش داشت ساعت خودش را جایگزین می‌کند.\n\nاگر       و         مقدار ساعت r در پردازندههای p و q در حین معدل‌گیری باشد،\n\nاگر r پردازندهای بی‌خطا باشد       =       .\n\nاگر r خطادار باشد                          .\n\nالگوریتم Interactive Convergence(ادامه)\n\nوقتی p و q میانگین مقادیر را حساب می‌کنند مقادیر یکسانی را برای n-m تا بی‌خطا استفاده می‌کنند و تفاوت بین مقادیر m تا خطادار نیز محدود به 3 است.          جمعاً (3m)\n\n \n\nمیانگین محاسبه شده حداکثر (3m/n) اختلاف دارند.\n\n \n\nچون 3m<n است پس میانگین جدید هر بار مقدار ساعت‌ها را به هم نزدیکتر می‌کند.\n\nبا تشکر از توجه شما\n\nتو پروژه\n\n2\n\n \n\n \n\n۳۰ تا ۷۰ درصد پروژه / پاورپوینت / پاور پوینت / سمینار / طرح های کار افرینی / طرح توجیهی /  پایان نامه/  مقاله ( کتاب ) های اماده   به صورت رایگان میباشد