پاورپوینت مدل محاسبات توزیعشده در حضور خطا (pptx) 58 اسلاید
دسته بندی : پاورپوینت
نوع فایل : PowerPoint (.pptx) ( قابل ویرایش و آماده پرینت )
تعداد اسلاید: 58 اسلاید
قسمتی از متن PowerPoint (.pptx) :
بنام خدا
1
مقدمه
طراحي و وريف کاربردهاي توزيع شده متحمل خطا به عنوان يک کار پيچيده تلقي مي شود. پديدههايي که براي ساده سازي اين کار مطرح شدهاند شامل اجماع (Consensus ) و چند نوع Reliable Broadcast است.
اجماع (Consensus):
امکان رسيدن پردازهها به يک تصميم مشترک که براساس وروديهاي اوليه و عليرغم خطا اخذ ميشود.
کاربردها: انتخاب رهبر و يا توافق روي مقدار يک سنسور تکرار شده.
پخش همگاني (Reliable Broadcast):
پخش همگاني در خيلي از کاربردهاي لازم است تا همه روي پيغامهاي تحويل گرفته توافق داشته باشند. يا روي ترتيب پيغامها توافق داشته باشند.
2
مقدمه - ادامه
برمبناي اين پديدهها، کاربردهاي زير مطرح هستند:
SIFT، Isis، Psync، Amoeba، Delta-4، Transis، HAS، FAA و Atomic Commitment
کلا تحقيقات زيادي انجام شده است ولي فرضيات و علامتگذاري متفاوت مانع از همسازي آنهاست.
براي بيان دقيق و ساده مطالب:
خط دقيق و مشخصي بين Specification و Algorithm کشيده ميشود.
استفاده زياد از مفهوم Reduction بين مسائل، درنتيجه کلاسهبندي مسائل براساس پيچيدگيشان.
امکان ارائه Specification وAlgorithm با يک بيان خيلي سطح بالا
3
مدل محاسبات توزیعشده در حضور خطا
مدل ارتباطي:
Message-Passing
از بين دو مدل مرسوم Message-Passing و Shared Memory
موارد:
همگامي پردازهها و ارتباطات
نوع خطاي پردازهها
نوع خطاي ارتباطي
همبندي شبکه
مشخص يا تصادفي بودن پردازهها
4
همگامی:
قابل اعمال هم در مورد پردازهها و هم سيستم ارتباطي
سيستمي را همگام گوئيم (در اين بخش) که شرايط زير را برآورده کند.
محدوده بالا (مشخص) مثل براي تأخير پيغامها وجود داشته باشد (ارسال، انتقال، دريافت).
هر پردازه P ساعت محلي Cp دارد که حداکثر اختلاف 0 را با ساعت واقعي دارد. براي همه پردازه هاي P و همه tt:
يک سقف و يک کف براي زمان اجراي يک مرحله از کار توسط يک پردازه وجود دارد.
بنابراين ميتوان Time-Out را براي هر پيغام اندازه گرفت.
روشي براي تشخيص خطا
5
همگامی – ادامه:
همچنين ميتوان ساعتهاي تقريبا همگام را پيادهسازي کرد. يعني ساعتهايي که علاوه بر محدودبودن فاصله آنها با ساعت واقعي (Drift)، شرط زير را برآورده ميکنند:
چنين ساعتهايي، حتي در حضور خطا هم ميتوانند پيادهسازي شوند.
کاربرد ساعتهاي تقريبا همگام (Approximately Sync.):
کنترل فرآيندهاي بيدرنگ، مديريتفايل، سازگاري Cache، Authentication ... .
در خيلي از مسائل نيز ميتواند ساعتهاي واقعي را شبيهسازي کند يعني =0 و لذا طرح الگوريتم توزيع شده را آسان ميکند.
6
سیستم ناهمگام
سيستمي ناهمگام خوانده ميشود اگر محدودهاي براي تاخير پيغامي، Clock Drift، زمان اجراي يک مرحله از يک کار وجود نداشته باشد. هيچ فرضي در مورد Timing وجود ندارد.
توجه: همگامي و ناهمگامي دو حد افراطي براي سيستمهاي واقعي هستند. مثلا روي بخشي از ويژگيها (تاخير، Drift، ...) محدوديت وجود دارد و روي بخشي نه.
7
خطای پردازه
مدلهاي خطا براي پردازه شامل:
Crash
Send Omission
Receive Omission
General Omission
Byzantine(نامعلوم)
نامعلوم همراه با Message Authentication
رفتار اختياري پردازه ولي مکانيزمي براي Authentication پيغامها وجود دارد. يعني پردازه خطادار نميتواند که از فلان پردازه درست پيغام دريافت کرده است حتي اگر چنين پيغامي ارسال نشده باشد.
اين دسته از خطا هم در مورد سيستمهاي همگام و هم سيستمهاي ناهمگام مطرح هستند. معهذا، خطاهاي زماني تنها در مورد سيستمهاي همگام مورد دارند.
8
خطای پردازه – ادامه:
پردازهاي را درمعرض خطاهاي زماني (Timing) ميدانيم که به يکي از روشهاي زير خطا کند:
خطاهاي General Omission را تاييد کند (مرتکب شود).
Drift ساعت محلياش از محدوده مشخص شده تجاوز کند.
محدوده زماني لازم براي اجراي يک مرحله از کاري را نقض کند.
از لحاظ جدي بودن:
General Omission < Timing < Byzantine
به نوع خطاهايي که جديتر از خطاي Timing نباشند Benign (ملايم) گويند:: پردازهها رفتار اختياري ندارند و يا پيغام غيرپيشبيني شدهاي در الگوريتم را نميفرستند.
9