الگوریتم Paxos

الگوریتم paxos یک الگوریتم به منظور رسیدن به اجماع است. اجماع در شبکه‌ به معنای توافق بر یک نتیجه در میان گروهی از افراد است.

مسائل اجتماع در سیستم‌های سنکرون قابل حل است. میتوان نشان داد که در سیستم‌های آسنکرون، اجماع قابل حل نیست. در واقع برای هر الگوریتم یا پروتکل، حالتی به عنوان worst case وجود دارد که در آن سیستم به اجماع نمیرسد که به flp proof معروف است. دلیل این موضوع این است که امکان تشخیص یک نود که خراب شده‌است از یک نود خیلی کند ممکن نیست.

برای همین به عنوان راه جایگزین، به سمت الگوریتم‌های امن و احتمالاتی برای حل اجماع رفته‌ایم. الگوریتم Paxos معروف‌ترین الگوریتم اجماع است.

این الگوریتم توسط اقای لزلی لمپورت اختراع شد. این الگوریتم دو ویژگی دارد:

• Safety
• Eventual Liveness

امن بودن الگوریتم به این معنی است که در صورتی که الگوریتم به نتیجه برسد، قطعا همه گره‌ها روی یک مقدار به اجماع رسیده‌اند و اصول اجماع تقض نشده است. همچنین Eventual Liveness به این معنی است که در صورتی که همه چیز به خوبی پیش برود ( خرابی پیش نیاید) شانس خوبی وجود دارد که الگوریتم به نتیجه برسد اما هیچ گارانتی وجود نداد.

الگوریتم شامل راندهایی است. هر راند به صورت آسنکرون است و یک آیدی یکتا به نام ballot id دارد. هر راند شامل سه فاز آسنکرون است.

• انتخاب رهبر
• ارائه‌ی یک مقدار پیشنهادی برای اجماع
• اجماع روی یک مقدار و ارسال مقدار نهایی اجماع‌شده برای همه‌ی گره‌ها

فاز اول: Election

گره‌هایی که در این فاز هستند در شروع فاز یک Potential leader خواهند بود. برای این که به leader تبدیل شوند یک ballot id بزرگتر از هر id که تا الان دیده‌اند را انتخاب میکنند و این id را به همه‌ی گره‌ها ارسال می‌کند. سپس منتظر گرفتن id بقیه گره‌ها می‌مانند. اگر یک Potential leader یک id بزرگتر از id خودش را بگیرد، نمیتواند به leader تبدیل شود و به گره که id بزرگتر برایش ارسال کرده‎است پیغام ok به معنی تایید رهبری او میفرستد که در این پیام بزرگترین مقدار که قبلا رویش توافق کرده هم وجود دارد. همچنین، هر نود بیشترین id که تا به حال دیده را در خود ذخیره میکند.

در صورتی که یک نود، از بیشتر از نصف نودها پیغام ok را بگیرد به leader ان راند تبدیل میشود و به فاز بعد می‌رود. اگر هیچ گرهی به این مرحله نرسه باشد یک راند از اول شروع میشود. چون هر Potential leader برای تبدیل شدن به leader به بیش از نصف پیغام ok نیاز دارد، هر راند نمیتواند بیشتر از یک leader داشته باشد.

فاز دوم: Proposal

نود رهبر مقدار متنساب با بزرگترین id که گرفته است را به عنوان v برای همه‌ی گره‌ها میفرستد. هر گره با گرفتن v، آن را ذخیره میکند و سپس پیغام ok را به سمت leader ارسال میکند. در صورتی که leader در زمان مشخص به نصف بیشتر تعداد گره‌ها، پیغام ok گرفت وارد فاز بعد میشود تا روی این گره اجماع شود.

فاز سوم: Decision

در صورتی که leader وارد این فاز شود مقدار v خود را این بار به عنوان مقدار مورد نظر برای اجماع برای تمام نودها میفرستد.