فهرست مطالب
مقدمه................................................................. 1
فصل اول: تشخیص بن بست در سیستمهای توزیع شده.......................... 2
1-1- مفاهیم پایه......................................................... 3
1-2- انواع مدلهای بن‌بست بر اساس سیستم تبادل پیام.......................... 3
1-3- انواع مدلهای بن‌بست بر اساس نوع درخواست............................ 3
1-4- شرایط وجود بن‌بست.................................................. 5
1-5- طبقه‌بندی الگوریتم‌های تشخیص بن‌بست................................ 5
فصل دوم: مروری بر الگوریتم‌های تشخیص بن‌بست............................. 9
مقدمه....................................................................10
2-1- نمونه‌ای از الگوریتم متمرکز جهت تشخیص بن‌بست در سیستمهای توزیع‌شده..... 10
2-1-1- الگوریتم هو- رامامورتی........................................... 10
2-2- نمونه‌ای از الگوریتم‌های تشخیص بن‌بست سلسله‌مراتبی................... 11
2-2-1- الگوریتم منساس – مانتر............................................ 11
2-2-2- الگوایتم هو – رامامورثی....................................... 11
2-3- نمونه‌هایی از الگوریتم‌های توزیع‌شده............................... 11
2-3-1- الگوریتم تشخیص بن‌بست چندی – مسیرا – هاس...................... 11
2-3-2- الگوریتم محاسبه پخش کردن چندی – مسیرا – هاس..................... 12
2-3-3- الگوریتم براچا – توگ............................................. 13
2-3-4- الگوریتم منساس و مانتز2-3-5- الگوریتم ابرمارک..................... 13
2-3-5- الگوریتم ابرمارک................................................ 14
2-3-6- الگوریتم بدالض...................................................... 15
فصل سوم: مروری بر الگوریتم‌های تشخیص بن‌بست توزیع شده تعقیب یال.......... 20
مقدمه............................................................... 21
3-1- بررسی الگوریتم‌های تشخیص بن‌بست تعقیب یال......................... 22
3-1-1- الگوریتم میچل و مریت........................................... 22
3-1-2- الگوریتم سینها و ناتارجان......................................... 23
3-1-3- الگوریتم چودهاری – کوهلر – استنکویچ و توسلی................... 23
3-1-4- الگوریتم سینقال و شمکالیانی........................................ 24
3-1-5- تشخیص بن‌بست توزیع شده و حل آن بر اساس ساعتهای سخت‌افزاری....... 24
3-2- ارائه روشی برای حذف بن‌بست نادرست در الگوریتم‌های تشخیص بن‌بست...... 25
3-3- نتیجه‌گیری........................................................... 27
فصل چهارم: الگوریتم‌های تشخیص بن‌بست توزیع شده تحمل خطاپذیر............. 29
مقدمه........................................................ 30
4-1- مروری بر الگوریتم‌های تحمل‌پذیر خطا جهت تشخیص بن‌بست.............. 31
4-2- معرفی مدل سیستم تشخیص خرابی بر اساس شاخص زمان اتصال.............. 33
4-3- یک الگوریتم تشخیص بن‌بست توزیع شده تحمل‌پذیر خطا................... 34
4-4- اثبات درستی الگوریتم.............................................. 37
4-5- نتیجه‌گیری......................................................... 38
فصل پنجم: تشخیص و حل بن‌بست در سیستمهای نماینده موبایل................. 39
مقدمه............................................................... 40
5-1- معرفی سیستمهای نماینده موبایل(نسل آینده سیستمهای توزیع شده)............... 41
5-2- تشخیص بن‌بست توزیع‌شده در سیستمهای نماینده موبایل.................. 41
5-3- معایب الگوریتم اصلی و مشکلات کارایی الگوریتم...................... 44
5-4- الگوریتم تشخیص بن‌بست توزیع شده مبتنی بر اولویت بهبودیافته................. 47
5-4-1- آنالیز کارایی الگوریتم بهبودیافته.................................... 48
5-4-2- اثبات درستی الگوریتم............................................ 49
5-5- نتیجه‌گیری....................................................... 50
نتیجه‌گیری.............................................................. 51
فهرست منابع............................................................... 53
پیوست‌ها................................................................ 55
جدول 2-1- مقایسه الگوریتم های بررسی شده تشخیص بن بست.................... 17
جدول 2-2- مقایسه کارایی الگوریتم های بررسی شده........................... 19
جدول 3-1- مقایسه مدل های الگوریتم های بررسی شده کلاس تعقیب یال......... 27
جدول3-2- بررسی صحت الگوریتم های بررسی شده.......................... 28
