در دنیای امروز که همه جا صحبت از رمزارزها و پردازش‌های ابری و توزیع شده است الگوریتم اجماع (consensus algorithms) نقش مهمی را ایفا می‌کنند و انجام کار ها به صورت توزیع شده با چالش هایی روبه‌رو است که در ادامه سعی داریم به زبانی ساده و دور از ریاضیات سخت آن را بیان کنیم. در نوشتن این مقاله از کتاب های الگوریتم های توزیع شده نانسی لینچ و ون فوکینک استفاده شده است.
یک الگوریتم اجماع در واقع یک مکانیزم است که این امکان را فراهم می‌کند که چند ماشین بتوانند بر سر یک موضوع به توافق برسند بدون اینکه یک ناظر کلی در اجرای الگوریتم تاثیری داشته باشد. الگوریتم اجماع باید در مقابل خطاها از خود انعطاف نشان دهد که این خطا ها می‌توانند خراب شدن یکی از ماشین ها، نرسیدن پیام و … باشد.
در الگوریتم هایی که به صورت سنتی در بحث‌های رای گیری و اجماع استفاده می‌شود یک ناظر کلی وجود دارد که همه اعضای سیستم و حالتی که هر کدام در آن هستند را مشاهده می‌کند و بر اساس این حالت ها تصمیم گیری صورت می‌گیرید و بقیه اعضا باید تصمیم گرفته شده را بپذیرند.
اما سختی کار در الگوریتم‌های توزیع شده این است که دیگر ناظر کلی وجود ندارد و هر گره بر اساس حالت اولیه خودش و پیغام هایی که به او رسیده یک تصمیم را در آن لحظه می‌گیرید و این باعث می‌شود که مثلا در صورتی که دو پیام در یک لحظه به یک گره فرستاده شود در صورتی که ترتیب آنها عوض شود تصمیمی که گره گیرنده می‌گیرد نیز متفاوت باشد به همین دلیل باعث می‌شود تا این سیستم ها به طور ذاتی غیر قطعی(nondeterministic) باشند.
قبل از شروع بحث نیاز است برخی از اصطلاحات توضیح داده شود تا در ادامه فهم موضوعات ساده‌تر باشد.
گره متخاصم (Byzantine node): گره‌ای است که قصد خراب کردن سیستم را دارد و نمی‌توان از آن انتظار هیج کار صحیحی داشت.
ازکار افتادن گره (node failure):گره‌ای است که تا به حال به درستی کار می‌کرده است اما کرش کرده و خراب شده است و دیگر درخواستی را پاسخ نمی‌دهد و پیامی نمی‌فرستد.
از کار افتادن مسیر ارتباطی (link failure): در صورتی که این اتفاق رخ بدهد و لینک ارتباطی بین دو یا چند گره قطع شود دیگر امکان تبادل پیام بین آن دو یا چند گره وجود ندارد.
سیستم سنکرون (synchronous): زمانی که بتوانیم برای رسیدن پیام گره‌ها به هم یک حد بالا تعریف کنیم یا به عبارت ساده‌تر بتوانیم تضمین کنیم که پیام ها حداکثر با یک تاخیر مشخص از گره فرستنده به گیرنده می‌رسند سیستم سنکرون است. در این صورت در سیستم سنکرون به دلیل وجود این حداکثر تاخیر می‌توان مراحل یا اپیزود برای سیستم در نظر گرفت.
سیستم آسنکرون (asynchronous): درست برخلاف سیستم بالا یعنی نمی‌توان حاکثری برای رسیدن پیام‌ها متصور شد.
برای شروع از یک مثال معروف و ساده شروع می‌کنیم تا بیشتر با یکی از انواع الگوریتم های اجماع که الگوریتم های Electionهستند آشنا شویم.
در مسئله انتخاب رهبر (leader election) بیان می‌شود که درصورتی که ما چندین گره یکسان داشته باشیم که از هر لحاظی با هم یکسان باشند و هر گره‌ای تنها با گره سمت راست خود در ارتباط باشد(مانند شکل زیر). و سیستم نیز یک سیستم سنکرون و بدون گره متخاصم و خرابی راه ارتباطی باشد در این صورت با هیچ الگوریتمی نمی‌توان یک گره را به عنوان رهبر انتخاب کرد.
شاید در هنگام خواندن این مسئله ( در صورتی که قبلا آن را ندیده باشید) از جواب شوکه شده باشید و منتظر یک الگوریتم ساده برای انتخاب رهبر بوده‌اید. اما نکته‌ای که در این مسئله وجود دارد این است که تمام گره‌ها یکسان هستند پس در ابتدا در یک حالت بوده اند و یک پیام خاص را فرستاده اند و همه یک پیام خاص را دریافت کرده اند و در این صورت اگر گره ای به صورت رهبر انتخاب شود بقیه نیز خود را رهبر می‌دانند.
اما شاید با خود بگویید هر کدام یک عدد رندوم تولید کنند یا یک از نودها یک پیغام را در اول به نود دیگر بدهد اما باید در نظر گرفت اگر بتوان کاری کرد که یکی از نود ها عددی رندوم تولید کند یا پیغامی خاص بدهد عملا مسئله حل شده است و آن گره به عنوان رهبر می‌توانست انتخاب شود.
اما مسئله در صورتی که هرکدام از این گره‌ها یک کد منحصر به فرد داشته باشند قابل حل است. فرض کنید که هر گره یک آیدی منحصر به فرد داشته باشد و الگوریتمی را در نظر بگیرید که هر گره در هر مرحله یک آیدی خاص را به گره‌ای که با آن در ارتباط است می‌فرستد این آیدی خاص به این صورت فرستاده می‌شود که در صورتی که تا به حال هیج آیدی نگرفته باشد (مرحله اول و شروع الگوریتم) هر گره آیدی خود را به گره همسایه خود می‌فرستد و از مرحله یک به بعد بزرگترین آیدی درمیان آیدی‌هایی که تا کنون دریافت کرده و آیدی خود گره به گره همسایه ارسال می‌کند.
در این صورت اگر ما n گره در این شبکه داشته باشیم پس از n مرحله همه گره‌ها آیدی بزرگترین گره را برای نود همسایه خود ارسال می‌کنند و شرط پایان این الگوریتم این است که یک گره آیدی خودش را دریافت کند در این صورت می‌فهمد که هیج گره‌ای با آیدی بزرگتر از آیدی خودش در این گراف وجود ندارید و بقیه گره‌ها نیز بزرگترین آیدی را دارند به همین با O(n^2) پیام ( n راند و در هر راند n پیام رد و بدل می‌شود) به اجماع رسیده اند.
تاکنون درباره اهمیت و تعاریف ساده الگوریتم های اجماع صحبت کردیم در قسمت بعدی به سراغ الگوریتم‌های اجماع یکی در سیستم‌های سنکرون و دیگری در سیستم‌های آسنکرون می‌رویم.
