مطالبی که در این بخش آمده نیاز دارد تا بخش قبلی را مطالعه کرده باشید.
در این نوشته سعی داریم با یکی از معروف‌ترین الگوریتم‌هایی که در زمینه اجماع در سیستم‌های آسنکرون داریم آشنا شویم و سپس مطالعه کنیم این الگوریتم‌ها در کجا کاربرد دارند.
در ابتدا باید بررسی کنیم تحت چه شرایطی می‌توان گفت که گرهها توسط یک الگوریتم اجماع به اجماع رسیده اند. سه شرط زیر برای رسیدن به اجماع لازم است:
توافق (agreement): یعنی تمام گرهها یک مقدار را به عنوان خروجی انتخاب کنند.
خاتمه (termination): یعنی تمام گرهها در یک زمان محدود به یک نتیجه برسند. (این شرط باعث می‌شود تا الگوریتم تا زمان بی‌نهایت اجرا نشود.)
اعتبار (validity): الگوریتم های باید بگونه باشد که خروجی براساس مقدار گره‌های راستگو مشخص شوند. برای مثال الگوریتمی که فقط یک یا فقط صفر را در یک مجموعه باینزی فارغ از مقدار گرهها خروجی می‌دهد هم توافق دارند هم می‌تواند در اولین مرحله خاتمه یابد زیرا مثلا همه گرهها در مرحله اول مقدار صفر را انتخاب می‌کنند و مسئله تمام می‌شود.
با دانستن سه شرط بالا حال ما مسئله رسیدن به اجماع در زمانی که گره‌های متخاصم در شبکه داریم را بررسی می کنیم که این مسئله تعمیم یافته شبکه است که گرهها می‌توانند در آن از کار بی‌افتند. در زیر سعی داریم که بدون ورود به ریاضیات مسئله، اجماع در سیستم‌های سنکرون در زمانی که بعضی از نود‌ها متخاصم هستند (یعنی دروغگو هستند و می‌توانند اطلاعات غلط داشته باشند.) را بررسی کنیم. در صورت نیاز به مطالعات بیشتر می‌توانید به این مقاله یا کتاب نانسی لینچ که در نوشته قبلی آورده شده بود مراجعه کنید.
فرض کنید ما n گره که در شبکه داریم f تا از آنها متخاصم هستند و می‌خواهیم الگوریتمی را اجرا کنیم که پس از اجرای آن تمام گره‌های درستکار (n-f گره) به یک تصمیم واحد برسند. در ابتدا چند مفهوم را تعریف می‌کنیم.
کلید خصوصی و عمومی (Public Key and Private Key): یک جفت کلید هستند که برای اجراز هویت و رمز کردن محتوای یک پیام به کار می‌روند. به طور کلی به این صورت عمل می‌کنند که متنی که توسط کلید عمومی قفل شود تنها توسط کلید خصوصی شخص می‌توانند دوباره به متن درست تبدیل شود. و از این ویژگی می‌توان به عنوان امضای دیجیتال استفاده کرد. برای انجام این کار به صورت زیر عمل می‌شود
شخص ابتدا یک کلید جفت عمومی و خصوصی تولید می‌کند و هر پیامی را که می‌فرستد با کلید خصوصی خود قفل می‌کند و کلید عمومی را نیز در اختیار همه قرار می‌دهد در نتیجه هر کس با در اختیار داشتن کلید عمومی شخص می‌تواند متن را رمزگشایی کند و مطمئن باشد که پیام از شخص مورد نظر دریافت شده است زیرا در غیر این صورت پیام با کلید عمومی آن شخص رمزگشایی نمی‌شد. ما از این ویزگی در ادامه برای احراز هویت پیام های ارسال شده استفاده می‌کنیم.
درخت EIG : این درخت، درختی است که برای جمع آوری اطلاعت استفاده می‌شود و به شکل زیر است
ابتدا برای آشنایی با این شبکه بیاید شبکه از گره ها را در نظر بگیریم که با هم پیام تبادل می‌کنند این درخت یک نمایش پیام های ارسال شده در این شبکه است. که در لایه اول و اولین گره مقدار اولیه این گره قرار دارد که در بعد مقدار گره یک که از خود گره ۲ دریافت شده است در گره ۱ ذخیره می‌شود و مقدار گره ۲ که از خود ۲ دریافت شده است در گره ۲ ذخیره می‌شود و به همین صورت تا آخر.
در لایه های بعدی مقدار گرهها با توجه به گره‌های واسطه ذکر شده‌اند برای مثال گره‌ای با تگ ۱۲۳۴ به این معنی است که مقدار گره ۱ با واسطه از طریق گره ۲ به گره ۳ و از طریق گره ۳ به گره ۴ رسیده است. و در آن گره مقداری که گره ۳ در مورد مقدار گره ۱ گفته است آورده شده است.
حال با استفاده از دو مفهوم بالا می‌توان به سراغ مسئله رفت و آن را حل کرد.
در ابتدا ثابت می‌شود که برای اینکه الگوریتم اجماع در شبکه سنکرون با گره‌های متخاصم به نتیجه برسد باید کمتر از یک سوم گرهها متخاصم باشند و در غیر این صورت این الگوریتم جواب نمی‌دهد. پس تعداد نود های متخاصم، f کمتر از یک سوم تعداد کل گرهها است.(n>3f)
در این مسئله همانطور که در ابتدا گفته شد گره‌های متخاصم می‌توانند درباره مقدار اولیه خودشان و بقیه گره ها دروغ بگویند و یا مقدار های مختلفی را به نود های متفاوت بدهند. برای مثال اگر گره ۲ متخاصم باشد می‌تواند به گره ۱ مقدار اولیه خود را ۰ و به گره ۳ مقدار اولیه خود را ۱ گزارش کند. یا حتی در صورتی که گره ۱ یک گره درستکار باشد و مقدار اولیه ۰ داشته باشد گره ۲ مقدار اولیه گره ۱ را ۱ به گره ۳ اعلام کند.
با در نظر گرفتن فرض های بالا و استفاده از درخت EIG برای حمع آوری پیام ها و کلید عمومی و خصوصی برای احراز هویت پیام ها می‌توان به صورت زیر عمل کرد.
چون سیستم سنکرون است پس پیام ها حداکثر تا یک تاخیر t به مقصد می‌رسند و پس می‌توان اجرای شبکه را به مراحل یا ایپزودهایی تقسیم بندی کرد. و همچنین فرض کی کنیم گراف کامل است یعنی تمام گره ها به همدیگر متصل هستند. در این صورت در مرحله اول اجرا لایه اول درخت EIG گره ها مقدار دهی می‌شود زیرا در مرحله اول هر گره تنها مقدار گره خود را به تمام گره ها می‌فرستد در فرستادن پیام‌ها گره ها پیام ها را توسط کلید خصوصی خود قفل می‌کنند تا گره‌های گیرنده با تطبیق کلید خصوصی و عمومی هر یک از آنها از درست بودن فرستنده مطمئن شوند .
در مراحل بعد هر گره علاوه بر مقدار اولیه خود مقدار هایی که تاکنون به آن دست یافته است را برای بقیه گرهها ارسال می‌کند در نتیجه لایه دوم هر گره نیز پر می‌شود برای مثال فرض کنید گره یک در راند ۱ به ترتیب مقدار های ۰، ۰ ، ۱ را از نود های ۲، ۳ ، ۴ گرفته است و در مرحله بعد این مقدار ها را برای هر ۳ گره ۲، ۳ و ۴ ارسال می‌کند. حال گره ۲ را در نظر بگیرید در این راند این گره در شبکه، گره های ۱۲، ۱۳، ۱۴ را در درخت خود اپدیت می‌کند معنی ۱۲ همانطور که پیشتر اشاره شده بود آن است که مقدار گره ۲ که توسط گره یک گزارش شده است.
با اجرای این الگوریتم به تعداد f+1 بار تمام f+2 لایه درخت تمام پر می‌شود.
زمانی که درخت به صورت کامل پر شد به این صورت عمل می‌کنیم که از لایه آخر شروع می‌کنیم و مقدار گره های پدر آن را بر اساس اکثریت آرا در لایه پایین‌تر آپدیت می‌کنیم و در صورتی که آرا نصف نصف بود یک مقدار از پیش تعیین شده مانند ۰ را قرار می‌دهیم. و به همین صورت درخت را تا ریشه لایه به لایه به روزرسانی می‌کنیم. با این کار مقدار ریشه یک عدد به دست می‌آید که آن تصمیم گره درست کار خواهد بود.
در قسمت بعدی ما یک الگوریتم اجماع در سیستم‌های آسنکرون را بررسی خواهیم کرد.
