الگوریتم اسنپ‌شات
الگوریتم Snapshot الگوریتمی است که در رایانش توزیع‌شده برای ضبط کردن حالت سازگار عمومی یک سیستم آسنکرون، از آن استفاده می‌شود. این الگوریتم همچنان به نام الگوریتم چاندی-لمپورت برای محاسبهٔ حالات سازگار عمومی و بدست آوردن کاهش‌های سازگار توسط لزلی لمپورت و مانی چاندی مطرح شد.
تاریخچه ویرایش
طبق مطالب وب سایت لزلی لامپورت "الگوریتم توزیع شده که در اینجا توضیح داده شد، از آنجا پدید آمد که من چاندی را ملاقات کردم که در آن زمان در دانشگاه تگزاس در آستین بود. او موضوع را به من در هنگام صرف شام مطرح کرد، ولی به اندازه‌ای مشروب مصرف کرده بودیم که امکان فکر بر روی آن موضوع را نداشتیم. فردا صبح آن شب، در حمام، راه حل آن موضوع را یافتم. وقتی وارد دفتر کار چاندی شدم او نیز منتظر من بود تا همان راه حل را به من ارائه کند"
آن راه حل در مقاله‌ای به نام «Snapshot توزیع شده: محاسبهٔ حالات عمومی یک سیستم توزیع شده» توضیح داده شده‌است.
تعریف ویرایش
فرضیات الگوریتم به شرح ذیل است:
- هیچ شکستی نداریم و تمامی پیام‌ها دست نخورده و فقط یک بار می‌رسند.
- کانال‌های ارتباطی غیرمستقیم هستند و به ترتیب خروج به ترتیب ورود (رایانه) هستند.
- بین هر ۲ فرآیند در سیستم، یک راه ارتباطی وجود دارد.
- هر فرآیندی می‌تواند یک الگوریتم Snapshot را شروع کند.
- الگوریتم Snapshot با اجرای معمولی فرآیندها، تداخلی ندارد.
- هر فرآیندی در سیستم حالت محلی آن و حالت کانال‌هایی که می‌آیند، را ضبط می‌کند.
الگوریتم مورد نظر با استفاده از پیام‌های نشانگر کار می‌کند. هر فرآیندی که می‌خواهد Snapshot ای را آغاز نماید، حالت محلی خود را ضبط کرده و نشانگری را به هر کدام از کانال‌های خروجی میفرستد. تمامی فرآیندهای دیگر تا دریافت یک نشانگر، حالت فعلی خودشان، که در واقع همان حالت کانالی است که نشانگر از آن امده، را حفظ کرده و سپس پیام‌های نشانگر را بر تمامی کانال‌های خروجی خود قرار می‌دهد. اگر فرآیندی پس از ضبط حالت قبلی خود، نشانگری دریافت کرد، حالت کانال دریافتی را که نشانگر برای ارسال پیام به آن آمده را نیز ضبط می‌کند. برخی از فرضیات این الگوریتم، می‌توانند ساده‌تر شوند به شرط آن که از پروتوکل‌های ارتباطی مطمئن تری استفاده شود مانند پروتوکل مجموعه پروتکل اینترنت. اگر بخواهیم اسنپ شات‌های مختلف به‌طور هم‌زمان اتفاق بیفتند، این الگوریتم می‌تواند به کار گرفته شود.
کارکرد ویرایش
الگوریتم اسنپ شات به‌طور مقابل کار می‌کند:
1. فرآیند ناظر (فرآیندی که اسنپ شات میگیرد)
1-1. حالت فعلی خود را ذخیره می‌کند. 2-1. پیام حاوی درخواست اسنپ شات را به تمامی فرآیندهای ارسال می‌کند.
2. فرآیند دریافت اسنپ شات که برای بار در تمامی پیام‌ها دریافت شده‌است.
1-2. به فرآیند ناظر حالت ذخیره شدهٔ خود را ارسال می‌کند. 2-2. اسنپ شات را به تمامی پیام‌های مربوطه متصل می‌کند.
3. هر فرآیند پیامی دارد که نشان می‌دهد اسنپ شات را دریافت کرده‌است یا خیر. این پیام قبل از این که اسنپ شات ارسال شود، فرستاده شده‌است و باید در اسنپ شات وجود داشته باشد.
با توجه به مراحل فوق، یک ناظر، اسنپ شات کاملی را درست می‌کند.