الگوریتم اسنپ‌شات

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

الگوریتم Snapshot الگوریتمی است که در رایانش توزیع‌شده برای ضبط کردن حالت سازگار عمومی یک سیستم آسنکرون، از آن استفاده می‌شود. این الگوریتم همچنان به نام الگوریتم چاندی-لامپورت برای محاسبهٔ حالات سازگار عمومی و بدست آوردن کاهش‌های سازگار توسط لزلی لامپورت و مانی چاندی مطرح شد.

تاریخچه[ویرایش]

طبق مطالب وب سایت لزلی لامپورت "الگوریتم توزیع شده که در اینجا توضیح داده شد، از آنجا پدید آمد که من چاندی را ملاقات کردم که در آن زمان در دانشگاه تگزاس در آستین بود. او موضوع را به من در هنگام صرف شام مطرح کرد، ولی به اندازه‌ای مشروب مصرف کرده بودیم که امکان فکر بر روی آن موضوع را نداشتیم. فردا صبح آن شب، در حمام، راه حل آن موضوع را یافتم. وقتی وارد دفتر کار چاندی شدم او نیز منتظر من بود تا همان راه حل را به من ارائه کند"

آن راه حل در مقاله‌ای به نام «Snapshot توزیع شده: محاسبهٔ حالات عمومی یک سیستم توزیع شده» توضیح داده شده‌است.

تعریف[ویرایش]

فرضیات الگوریتم به شرح ذیل است:

  • هیچ شکستی نداریم و تمامی پیام‌ها دست نخورده و فقط یک بار می‌رسند.
  • کانال‌های ارتباطی غیر مستقیم هستند و به ترتیب خروج به ترتیب ورود (رایانه) هستند.
  • بین هر ۲ فرآیند در سیستم، یک راه ارتباطی وجود دارد.
  • هر فرآیندی می‌تواند یک الگوریتم Snapshot را شروع کند.
  • الگوریتم Snapshot با اجرای معمولی فرآیندها، تداخلی ندارد.
  • هر فرآیندی در سیستم حالت محلی آن و حالت کانال‌هایی که می‌آیند، را ضبط میکند.

الگوریتم مورد نظر با استفاده از پیام‌های نشانگر کار میکند. هر فرآیندی که می‌خواهد Snapshot ای را آغاز نماید، حالت محلی خود را ضبط کرده و نشانگری را به هر کدام از کانال‌های خروجی میفرستد. تمامی فرآیند های دیگر تا دریافت یک نشانگر، حالت فعلی خودشان، که در واقع همان حالت کانالی است که نشانگر از آن امده، را حفظ کرده و سپس پیام های نشانگر را بر تمامی کانال های خروجی خود قرار میدهد. اگر فرآیندی پس از ضبط حالت قبلی خود، نشانگری دریافت کرد، حالت کانال دریافتی را که نشانگر برای ارسال پیام به آن آمده را نیز ضبط میکند. برخی از فرضیات این الگوریتم، میتوانند ساده تر شوند به شرط آن که از پروتوکل های ارتباطی مطمئن تری استفاده شود مانند پروتوکل مجموعه پروتکل اینترنت. اگر بخواهیم اسنپ شات های مختلف به طور همزمان اتفاق بیفتند، این الگوریتم میتواند به کار گرفته شود.

کارکرد[ویرایش]

الگوریتم اسنپ شات به طور مقابل کار می کند:

1.فرآیند ناظر (فرآیندی که اسنپ شات میگیرد)

  1-1.حالت فعلی خود را ذخیره می کند.
  2-1.پیام حاوی درخواست اسنپ شات را به تمامی فرآیند های ارسال می کند.

2.فرآیند دریافت اسنپ شات که برای بار در تمامی پیام ها دریافت شده است.

  1-2.به فرآیند ناظر حالت ذخیره شده ی خود را ارسال میکند.
  2-2.اسنپ شات را به تمامی پیام های مربوطه متصل می کند.

3.هر فرآیند پیامی دارد که نشان می دهد اسنپ شات را دریافت کرده است یا خیر. این پیام قبل از این که اسنپ شات ارسال شود، فرستاده شده است و باید در اسنپ شات وجود داشته باشد.

با توجه به مراحل فوق، یک ناظر، اسنپ شات کاملی را درست می کند.

منابع[ویرایش]

وب سایت لزلی لامپورت

پیوندها[ویرایش]

  • [۱]توضیحی بر الگوریتم های اسنپ شات در محاسبات توزیع شده
  • [۲]حالت عمومی و الگوریتم های ضبط اسنپ شات
  • [۳]وب سایت لزلی لامپورت