تجزیه و تحلیل قابلیت دسترسی
تجزیه و تحلیل قابلیت دسترسی یک راه حل برای مشکل قابلیت دسترسی در زمینه خاص سیستم های توزیع شده است. برای تعیین اینکه به کدام کشورهای جهانی می توان از طریق یک سیستم توزیع شده متشکل از تعداد مشخصی از نهادهای محلی که با تبادل پیام ارتباط برقرار می کنند ، دسترسی پیدا کرد، استفاده می شود.
تجزیه و تحلیل قابلیت دسترسی در مقاله ای از سال 1978 برای تجزیه و تحلیل و تأیید پروتکل های ارتباطی معرفی شد . این مقاله با الهام از مقاله ای توسط بارتلت و همکاران ارائه شده است. از 1968 که پروتکل بیت متناوب را با استفاده از مدل سازی حالت محدود موجودیت های پروتکل ارائه داد و همچنین اشاره کرد که پروتکل مشابهی که قبلاً شرح داده شد دارای نقص طراحی است. این پروتکل به لایه پیوند تعلق دارد و تحت برخی مفروضات ، تحویل صحیح داده ها بدون از دست دادن و یا کپی برداری را ، علی‌رغم وجود برخی اوقات خرابی یا از بین رفتن پیام، به عنوان سرویس ارائه می دهد.
برای تجزیه و تحلیل قابلیت دستیابی ، نهادهای محلی با حالت ها و انتقال های خود مدل سازی می شوند. موجودیت با ارسال پیام ، مصرف پیام دریافتی یا انجام تعامل در رابط خدمات محلی خود ، حالت را تغییر می دهد. دولت جهانی formula_1 یک سیستم با n موجودیت توسط ایالات تعیین می شود formula_2 (من = 1 ، ... n) از موجودیت ها و وضعیت ارتباطات formula_3. در ساده ترین حالت ، محیط بین دو موجودیت توسط دو صف FIFO در جهت مخالف ، که حاوی پیام های در حال انتقال است (که ارسال می شود ، اما هنوز مصرف نشده است) مدل می شود. تجزیه و تحلیل قابلیت دسترسی با تجزیه و تحلیل تمام توالی های احتمالی انتقال حالت موجودیت ها و وضعیت جهانی مربوطه ، رفتار احتمالی سیستم توزیع شده را در نظر می گیرد.
نتیجه تجزیه و تحلیل قابلیت دستیابی ، نمودار انتقال وضعیت جهانی است (همچنین نمودار قابلیت دستیابی نیز نامیده می شود) که تمام حالت های جهانی سیستم توزیع شده را که از حالت اولیه جهانی قابل دسترسی هستند ، و همه توالی های ممکن ارسال ، مصرف و تعاملات خدماتی که توسط محلی انجام می شود را نشان می دهد موجودیت ها. با این حال ، در بسیاری از موارد ، این نمودار انتقال نامحدود است و نمی توان آن را به طور کامل جستجو کرد. نمودار انتقال می تواند برای بررسی نقایص کلی طراحی پروتکل (به زیر را ببینید) ، بلکه همچنین برای بررسی اینکه توالی تعاملات سرویس توسط نهادها با الزامات ارائه شده توسط مشخصات سرویس جهانی سیستم مطابقت دارد.
"محدودیت:" نمودار انتقال وضعیت جهانی محدود است اگر تعداد پیام هایی که ممکن است در حال انتقال باشند محدود است و تعداد ایالات همه موجودات محدود است. این سوال که آیا تعداد پیام ها در مورد اشخاص محدود دولت محدود باقی می ماند ، به طور کلی مسئله تصمیم‌ناپذیر است . وقتی تعداد پیام های منتقل شده به یک آستانه مشخص می شود ، یکی معمولاً نمودار انتقال را کوتاه می کند.
موارد زیر نقایص طراحی است:
به عنوان مثال ، ما سیستم دو موجود پروتکل را در نظر می گیریم که پیام های "ma" ، "mb" ، "mc" و "md را" با یکدیگر مبادله می کنند ، همانطور که در نمودار اول نشان داده شده است. پروتکل با رفتار دو موجودیت تعریف می شود ، که در نمودار دوم به صورت دو ماشین حالت ارائه می شود. در اینجا نماد "!" به معنای ارسال پیام است ، و "؟" به معنای مصرف پیام دریافتی است. حالتهای اولیه حالتهای "1" هستند.
نمودار سوم نتیجه تجزیه و تحلیل قابلیت دستیابی برای این پروتکل را در قالب یک ماشین حالت جهانی نشان می دهد. هر دولت جهانی دارای چهار م componentsلفه است: وضعیت نهاد پروتکل A (چپ) ، حالت نهاد B (راست) و پیام های در حال انتقال در وسط (قسمت بالایی: از A به B ؛ قسمت پایین: از B به A ) هر انتقال این دستگاه حالت جهانی مربوط به یک انتقال موجودیت پروتکل A یا نهاد B است. حالت اولیه [1 ، - - ، 1] است (بدون ارسال پیام در حال انتقال).
یکی می بیند که این مثال دارای یک فضای جهانی محدود است - حداکثر تعداد پیام هایی که ممکن است همزمان حمل و نقل شوند دو پیام است. این پروتکل دارای یک بن بست جهانی است که این حالت است [2 ، - - ، 3]. اگر کسی انتقال A را در حالت 2 برای مصرف پیام "mb حذف کند" ، در ایالات جهانی [2 ، "ma mb" ، 3] و [2 ، - "mb" ، 3] استقبال نامشخصی صورت می گیرد.
طراحی یک پروتکل باید با خواص محیط ارتباطی زمینه ای ، با احتمال عدم موفقیت شریک ارتباطی و سازوکار مورد استفاده توسط نهادی برای انتخاب پیام بعدی برای مصرف ، سازگار شود. رسانه ارتباطی برای پروتکل ها در لایه پیوند به طور معمول قابل اعتماد نیست و امکان دریافت اشتباه و از دست دادن پیام را فراهم می کند (به عنوان انتقال حالت رسانه مدلسازی می شود). پروتکل های استفاده شده از سرویس IP اینترنت نیز باید امکان تحویل خارج از سفارش را داشته باشند. پروتکل های سطح بالاتر معمولاً از یک سرویس حمل و نقل جلسه محور استفاده می کنند که به این معنی است که رسانه انتقال FIFO قابل اطمینان از پیام ها را بین هر جفت موجودیت فراهم می کند. با این حال ، در تجزیه و تحلیل الگوریتم های توزیع شده ، اغلب این احتمال وجود دارد که برخی موجودیت ها به طور کامل از کار بیفتند ، که به طور معمول (از دست دادن پیام در رسانه) با رسیدن یک پیام مورد انتظار توسط مکانیزم مهلت شناسایی نمی‌شود.
در مورد اینکه آیا یک نهاد می تواند پیام خاصی را برای مصرف انتخاب کند ، وقتی چندین پیام از راه رسیده و آماده مصرف است ، فرض های مختلفی ارائه شده است. مدل های اصلی به شرح زیر است:
مقاله اصلی که مشکل پذیرایی های نامشخص را مشخص می کند ، و بیشتر کارهای بعدی ، یک صف ورودی واحد در نظر گرفته است. بعضی اوقات ، پذیرش های نامشخص توسط یک وضعیت رقابتی ای معرفی می شوند ، به این معنی که دو پیام دریافت می شود و ترتیب آنها تعریف نمی‌شود (که این امر معمولاً در صورت دریافت از طرف شرکای مختلف صورت می گیرد). با استفاده از صف های مختلف یا استخرهای پذیرایی ، بسیاری از این نقایص طراحی از بین می روند. با استفاده منظم از استخرهای پذیرش ، تجزیه و تحلیل قابلیت دسترسی باید بن بست های جزئی و پیام هایی را که برای همیشه در استخر باقی مانده اند بررسی کند (بدون اینکه توسط نهاد مصرف شود)
بیشتر کارها در زمینه مدل سازی پروتکل از مدلهای ماشین حالات متناهی (FSM) برای مدل سازی رفتار موجودات توزیع شده استفاده می شود (همچنین به برقراری ارتباط ماشینهای حالت محدود مراجعه کنید). با این حال ، این مدل برای مدل سازی پارامترهای پیام و متغیرهای محلی به اندازه کافی قدرتمند نیست. بنابراین اغلب به اصطلاح از مدلهای FSM توسعه یافته استفاده می شود ، مانند پشتیبانی از زبانهایی مانند ماشین حالت یو.ام.ال یا SDL . متأسفانه ، تجزیه و تحلیل قابلیت دستیابی برای چنین مدلهایی بسیار پیچیده تر می شود.
یک مسئله عملی تجزیه و تحلیل قابلیت دسترسی به اصطلاح "حالت انفجار فضای" است. اگر دو موجودیت یک پروتکل هر کدام 100 حالت داشته باشند ، و محیط ممکن است شامل 10 نوع پیام باشد که در هر جهت حداکثر دو مورد را نشان می دهد ، بنابراین تعداد حالت های جهانی در نمودار قابلیت دسترسی به عدد 100 100 100 x محدود می شود (10x10) x (10 x 10) که 100 میلیون است. بنابراین تعدادی ابزار برای انجام خودکار تجزیه و تحلیل قابلیت دستیابی و بررسی مدل در نمودار قابلیت دستیابی تولید شده است. ما فقط به دو نمونه اشاره می کنیم: جستجوگر مدل SPIN و یک جعبه ابزار برای ساخت و تحلیل فرایندهای توزیع شده .