اجماع (علوم کامپیوتر)

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

شرح مشکل

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

مشکل اجماع یک مشکل اساسی در کنترل سیستم‌های چند عاملی است. یک رویکرد برای تولید اجماع این است که همه فرایندها (نمایندگان) بر روی مقدار اکثریت توافق کنند. در این زمینه، اکثریت به حداقل یک رای بیشتر از نیمی از آرای موجود نیاز دارد (که در آن به هر فرایند رای داده می‌شود). هرچند، یک یا چند فرایند معیوب ممکن است نتیجه حاصل را منحرف کند به طوری که ممکن است اجماع به دست نیاید یا به اشتباه حاصل شود.

پروتکل‌هایی که مشکلات اجماع را حل می‌کنند برای مقابله با تعداد محدودی از فرآیندهای معیوب طراحی شده‌اند. این پروتکل‌ها برای مفید بودن باید تعدادی از الزامات را برآورده کنند. به عنوان مثال، یک پروتکل بی‌اهمیت می‌تواند خروجی تمام فرایندها مقدار باینری ۱ را داشته باشد. این مفید نیست و بنابراین نیاز به گونه ای اصلاح می‌شود که خروجی به نحوی به ورودی بستگی داشته باشد؛ یعنی مقدار خروجی یک پروتکل اجماعی باید مقدار ورودی یک فرایند باشد. الزام دیگر این است که یک فرایند می‌تواند فقط یک بار در مورد مقدار خروجی تصمیم بگیرد و این تصمیم غیرقابل برگشت است. در صورتی که فرآیندی در اجرا با شکست مواجه نشود، صحیح نامیده می‌شود. یک پروتکل توافقی که خرابی‌های رخ داده را تحمل می‌کند باید ویژگی‌های زیر را برآورده کند.

پایان دهی

در نهایت، هر فرایند صحیح مقادیر را تعیین می‌کند.

تمامیت

اگر همه فرآیندهای صحیح یک مقدار $v$ را پیشنهاد کنند، پس هر فرایند صحیح باید تصمیمش مقدار $v$ باشد.

توافق

هر فرایند صحیح باید بر روی یک مقدار واحد توافق کنند.

طبق کاربرد، تغییرات در تعریف یکپارچگی می‌تواند مناسب باشد. به عنوان مثال، نوع ضعیف‌تر یکپارچگی می‌تواند این گونه تعریف شود که ارزش تصمیم برابر با مقداری باشد که برخی از فرآیندهای صحیح پیشنهاد کرده‌اند - نه لزوماً همه آنها. شرط یکپارچگی به عنوان اعتبار در ادبیات شناخته می‌شود.

پروتکلی که بتواند به درستی اجماع بین n فرایند، که حداکثر t فرایند از آن‌ها با شکست مواجه می‌شوند، را تضمین کند، t-مقاوم نامیده می‌شود.

در ارزیابی عملکرد پروتکل‌های اجماع دو عامل مورد علاقه زمان اجرا و پیچیدگی پیام است. زمان اجرا با نماد O بزرگ، در تعداد دورهای مبادله پیام به عنوان تابعی از برخی پارامترهای ورودی (معمولا تعداد فرایندها و/یا اندازه دامنه ورودی) نمایش داده می‌شود. پیچیدگی پیام به میزان ترافیک پیامی که توسط پروتکل ایجاد می‌شود اشاره دارد. عوامل دیگر ممکن است شامل استفاده از حافظه و اندازه پیام‌ها باشد.