نظریه سیستم‌های توزیع‌شده

Theory of Distributed Systems

شماره درس: ۴۰۶۶۱	تعداد واحد: ۳
مقطع: کارشناسی ارشد	نوع درس: نظری
پیش‌نیاز: –	هم‌نیاز: –

اهداف درس

هدف از ارائه این درس آشنایی دانشجویان با اصول نظری و مفاهیم اساسی توزیع‌شدگی به ویژه توصیف، طراحی و تحلیل الگوریتم‌های مورد نیاز برای حل مسائل مطرح در مدل‌های مختلف سیستم‌های توزیع شده شامل مدل‌های هم‌گام یا نا‌هم‌گام و مدل‌های ارتباطی مبتنی بر حافظه مشترک یا مبتنی بر تبادل پیغام است. برخی از مسائل اصلی که به بررسی و تحلیل الگوریتم‌های آن پرداخته می‌شود عبارتند از: مساله انتخاب رهبر در انواع مدل‌های توزیع‌شده‌گی، حل توزیع شده برخی مسائل پایه گراف مانند مسایل کوتاه‌ترین مسیر، درخت پوشای کمینه، مجموعه مستقل بیشینه و جستجوی عرضی گراف، انواع مسئله توافق (مانند Agreement و Commitment)، مساله اجماع (Consensus)، انواع روشهای برآوردن نیازمندی انحصار متقابل (Mutual Exclusion). همچنین به مسائل مرتبط با زمانمندی سیستم‌ها مانند هم‌گام کردن ساعت‌ها (Clock Synchronization) به ویژه با فرض وجود شکست (Failure) یا اشکال (Fault) در سیستم توزیع‌شده می‌پردازد. علاوه بر مباحث الگوریتمی فوق، این درس همچنین به موضوع اثبات صوری درستی عملکرد الگوریتم‌ها و پروتکل‌های توزیع شده و به خصوص روش‌های اثبات آن که ویژگی‌های لازم مانند ویژگی‌های سرزندگی (Liveness)، انصاف (Fairness) و فارغ از بن‌بست بودن (Deadlock Freeness) را ارضا می‌کنند می‌پردازد. بنابراین به عنوان ابزاری برای این گونه اثبات‌ها، این درس به روش‌های صوری مدل‌سازی سیستم‌های توزیع شده نیز می‌پردازد. در نهایت، به عنوان مطالب به روز و موضوعات پژوهشی، می‌توان به کاربرد تحلیلی الگوریتم‌ها و روش‌های فرمال فوق در برخی سیستم‌های توزیع شده بر بستر‌های ارتباطی جدید مانند سیستم‌های بی‌سیم به خصوص شبکه‌های موبایل و ad hoc پرداخت.

ریز مواد

معرفی نظریه سیستم‌های توزیع‌شده، مدل‌ها و روش‌های تحلیل آن‌ها، دسته‌بندی انواع مدل‌های مختلف سیستم‌های توزیع شده شامل مدل‌های هم‌گام یا نا‌هم‌گام و مدل‌های ارتباطی مبتنی بر حافظه مشترک یا مبتنی بر تبادل پیغام، مروری بر روش‌های مدل‌سازی ریاضی انواع سیستم‌های بالا. (۲ جلسه)
مدل‌سازی شبکه‌های هم‌گام، روش‌های اثبات ویژگی‌های مدل، ملاک‌های پیچیدگی الگوریتم‌ها و سیستم‌های توزیع‌شده. (۱ جلسه)
مدل‌سازی شبکه‌های ناهم‌گام، آتوماتای ورودی- خروجی (Lynch’s I/O Automata)، روش‌های اثبات درستی و ویژگی‌های لازم پروتکل‌های ارتباطی توزیع شده. (۱ جلسه)
مدل‌سازی شبکه‌های ناهم‌گام مبتنی بر حافظه مشترک (Shared Memory) یا مبتنی بر ارتباط با تبادل پیغام (Message Passing). (۱ جلسه)
الگوریتم‌های انتخاب رهبر در: (۳ جلسه)
- شبکه Ring هم‌گام
- شبکه‌های هم‌گام عمومی
- شبکه‌های ناهم‌گام با تبادل پیغام
- شبکه‌های ناهم‌گام با حافظه مشترک
الگوریتم‌های توزیع‌شده پایه مبتنی بر گراف مانند جستجوی عرضی، کوتاهترین مسیر و درخت پوشای کمینه در: (۳ جلسه)
- شبکه‌های هم‌گام.
- شبکه‌های ناهم‌گام با تبادل پیغام.
- شبکه‌های ناهم‌گام با حافظه مشترک.
الگوریتم‌‌های اجماع (Consensus) در: (۳ جلسه)
- شبکه‌های هم‌گام با فرض امکان شکست ارتباط (Communication Failure).
- شبکه‌های هم‌گام با فرض امکان شکست پردازه (Process Failure).
- شبکه‌های ناهم‌گام با فرض امکان شکست ارتباط (Communication Failure).
- شبکه‌های ناهم‌گام با فرض امکان شکست پردازه (Process Failure).
مسایل و الگوریتم‌های انحصار متقابل در شبکه‌های ناهم‌گام مبتنی بر حافظه مشترک. (۲ جلسه)
مسایل و الگوریتم‌های انحصار متقابل در شبکه‌های ناهم‌گام مبتنی بر تبادل پیغام. (۲ جلسه)
سایر الگوریتم‌ها برای شبکه‌های ناهم‌گام مبتنی بر حافظه مشترک شامل الگوریتم‌های تخصیص منابع (Recourses Allocation ) و الگوریتم‌های اجماع. اثباتی برای عدم امکان اجماع در شبکه‌های ناهم‌گام مبتنی بر حافظه مشترک که دارای پردازه مشکل‌دار (شبکه‌های Fault Prone) هستند. (۲ جلسه)
مفاهیم اشیای اتمی و مسایل مرتبط با تصویر‌های لحظه‌ای اتمی (Atomic Snapshots). (۳ جلسه)
مروری بر مسایل مطرح شده بالا برای سیستم‌های توزیع‌شده مبتنی بر زمان‌بندی (Timing) به خصوص مسائل انحصار متقابل در این گونه سیستم‌ها، مسائل هم‌گام‌سازی ساعت‌ها (Clock Synchronization) و مساله اجماع. (۲ جلسه)
(معرفی برخی زمینه‌های پژوهشی منتخب) کاربرد تحلیلی الگوریتم‌ها و روش‌های فرمال فوق درسیستم‌های توزیع شده بر بستر‌های ارتباطی جدید مانند سیستم‌های بی‌سیم به خصوص شبکه‌های موبایل و ad hoc. مختصری پیرامون حساب پای (π-Calculus)، حساب عامل‌های متحرک (Ambient Calculus) و مدل‌های مبتنی بر اکتور (Actor)، زنجیره های بلوکی (Block-Chain) و ارزهای دیجیتال، مسایل خود پایدارسازی (Self-Stabilization)، رابطه نظریه بازی و نظریه سیستم‌های توزیع شده. (۵ جلسه)

ارزیابی

آزمون: آزمون‌های میان‌نیم‌سال (۲۵ درصد نمره) و پایان‌نیم‌سال (۴۰ درصد نمره)
تمرین: چند سری تمرین بر اساس متون معرفی شده (۱۵ درصد نمره)
گزارش پژوهشی: ارائه‌ مقاله‌ای در موضوعات مرتبط که حداقل مستلزم مطالعه پنج مقاله به‌روز باشد (۲۰ درصد نمره).
ارائه: ارائه یک موضوع منتخب در کلاس (±۱۰ درصد نمره)

مراجع

N. Lynch. Distributed Algorithms. Morgan Kaufmann, 1996.
H. Attiya and J. Welch. Distributed Computing: Fundamentals, Simulations, and Advanced Topics. 2nd edition, Wiley, 2004.
G. Tel. Introduction to Distributed Algorithms. 2nd edition, Cambridge University Press, 2000.