اجماع توزیع شده (Distributed Consensus) چطور کار می‌کند؟

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

0 288

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

بلاکچین‌ها مهندسین و دانشمندان را مجبور کرده است تا الگوهای تثبیت شده در رایانش توزیع شده را مجددا بررسی کرده و جدا مورد بحث قرار دهند.

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

سیستم‌های توزیع شده به هیچ وجه جدید نیستند. دانشمندان و مهندسان ده‌ها سال را صرف تحقیق در مورد این موضوع کرده‌اند. اما بلاکچین‌ها چه ارتباطی با آن‌ها دارند؟ بدون وجود سیستم‌های توزیع شده بلاکچین‌ها و تحولات مربوط به آن‌ها ممکن نبودند.

اساسا، بلاکچین یک نوع سیستم توزیع شده جدید است. بلاکچین با ظهور بیت کوین کار خود را آغاز کرده و از آن زمان تاثیر پاینده‌ای بر حوزه رایانش توزیع شده گذاشته است. بنابراین، اگر واقعا تمایل دارید تا بدانید بلاکچین‌ها چگونه کار می‌کنند، باید پیش از آن درک مناسبی از اصول سیستم‌های توزیع شده داشته باشید.

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

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

  • پس از خواندن این مقاله، شما درک قوی‌تری در مورد موضوعات زیر خواهید داشت:
  • سیستم توزیع شده چیست،
  • خواص یک سیستم توزیع شده،
  • معنای داشتن اجماع در یک سیستم توزیع شده،
  • درکی از الگوریتم‌های اجماع پایه‌ای (مانند DLS و PBFT)
  • چرا اجماع ناکاموتو اهمیت زیادی دارد.

امیدوارم آماده یادگیری باشید، چرا که کلاس درس از هم‌اکنون آغاز می‌شود.

سیستم توزیع شده چیست

یک سیستم توزیع شده مجموعه‌ای از فرآیندهای متمایزی (به عنوان مثال: رایانه‌ها) است که پیام‌ها را به یکدیگر انتقال داده و برای رسیدن به یک هدف مشترک (یعنی حل یک مسئله محاسباتی) با یکدیگر هماهنگ می‌شوند.

یک سیستم توزیع شده، گروهی از کامپیوترها هستند که برای دستیابی به یک هدف واحد همکاری می‌کنند.

به بیان ساده‌تر، یک سیستم توزیع شده، گروهی از کامپیوترها هستند که برای دستیابی به یک هدف واحد همکاری می‌کنند. و اگرچه فرآیندها از یکدیگر جدا هستند، سیستم برای کاربر نهایی به عنوان یک کامپیوتر واحد به نظر می‌رسد.

همانطور که اشاره کردم، صدها معماری برای یک سیستم توزیع شده وجود دارد. به عنوان مثال، یک کامپیوتر نیز می‌تواند به عنوان یک سیستم توزیع شده در نظر گرفته شود: واحد کنترل مرکزی، واحدهای حافظه و کانال‌های ورودی-خروجی فرآیندهای جداگانه‌ای هستند که برای رسیدن به یک هدف همکاری می‌کنند.

در یک هواپیما، این واحدهای مجزا با هم همکاری می‌کنند تا شما را از نقطه A به نقطه B برسانند:

سیستم توزیع شده

منبع: https://www.weetech.de/en/news-info/tester-abc/distributed-system-1/

در مقاله حاضر، بر روی سیستم‌های توزیع شده‌ای تمرکز خواهیم کرد که در آن‌ها فرآیندها به صورت فضایی مجزا شده‌اند.

سیستم توزیع شده

شکل توسط نگارنده ترسیم شده است.

نکته: ممکن است از اصطلاحات «نود»، «کامپیوتر» یا «جزء» به جای «فرآیند» استفاده کنم. این عبارات همگی در این زمینه معنایی یکسان دارند. به طور مشابه، ممکن است از اصطلاح «شبکه» به جای «سیستم» استفاده کنم.

خواص یک سیستم توزیع شده

هر سیستم توزیع شده دارای خواص مشخصی است. این خواص عبارتند از:

الف) همزمانی

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

این کار مستلزم هماهنگی است.

 همزمانی

لامپورت (Lamport)، ۱۹۷۸ زمان، ساعت‌ها و ترتیب رویدادها در یک سیستم توزیع شده

ب) عدم وجود یک ساعت جهانی

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

لزلی لامپورت در مقاله «زمان، ساعت‌ها و ترتیب رویدادها در یک سیستم توزیع شده» نشان می‌دهد که چگونه با به یاد داشتن عوامل زیر‌ می‌توان دریافت که رویدادی پیش از دیگری اتفاق افتاده است:

  1. پیام‌ها قبل از دریافت ارسال می‌شوند.
  2. هر کامپیوتر دارای ترتیبی از اتفاقات است.

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

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

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

اما صبر کنید! مشکل بزرگی وجود دارد: هماهنگ کردن ساعت‌های مستقل یک مساله بسیار پیچیده علم کامپیوتر است. حتی اگر در ابتدا تعدادی از ساعت‌ها را به طور دقیق تنظیم کنید، ساعت‌ها بعد از گذشت مدت زمانی تفاوت پیدا خواهند کرد. این به دلیل «راندگی ساعت» است: پدیده‌ای که در آن ساعت‌ها نرخ‌های زمان را کمی متفاوت شمارش می‌کنند.

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

ج) ناکامی مجزای اجزا

یکی از جنبه‌های مهم درک سیستم‌های توزیع شده، اذعان این است که اجزای یک سیستم توزیع شده دارای خطا هستند. به همین دلیل است که آن را «رایانش تحمل‌ خطا» نامیده‌اند.

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

داشتن سیستمی بدون خطا غیرممکن است.

این ناکامی‌ها را می‌توان به سه دسته تقسیم کرد:

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

با توجه به این موضوع، هدف طراحی پروتکل‌هایی است که به سیستمی با اجزای خطاکار اجازه می‌دهد تا همچنان به هدف مشترک رسیده و خدمات مفیدی ارائه دهند.

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

به طور کلی، هنگام ساختن یک سیستم توزیع شده دو مدل وجود دارد

۱) تحمل خطای ساده

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

۲ الف) تحمل خطای بیزانسی

یک سیستم ساده تحمل خطا مناسب یک محیط کنترل نشده نیست. در یک سیستم غیر متمرکز که در آن نودها توسط عاملان مستقلی کنترل می‌شوند که در اینترنت باز و بدون پرمیشن (permission) تماس برقرار می‌کنند، باید نودهایی را نیز در نظر داشته باشیم که مخرب یا «بیزانسی» هستند. بنابراین، در یک سیستم متحمل خطای بیزانسی، فرض می‌کنیم که ممکن است نودها شکست خورده و یا مخرب باشند.

۲ ب) تحمل خطای BAR

با وجود این که اکثر سیستم‌های واقعی برای مقاومت در برابر خطاهای بیزانسی طراحی شده‌اند، بعضی از کارشناسان معتقدند که این طرح‌ها بیش از حد کلی بوده و خطاهای «منطقی» را در نظر نمی‌گیرند، خطاهایی که در آن‌ها نودها می‌توانند برای منفعت شخصی خود از مسیر منحرف شوند. به عبارت دیگر، نودها می‌توانند بسته به انگیزه خود درستکار بوده و یا نباشند. اگر اندازه کافی انگیزه داشته باشند، حتی ممکن است اکثریت نودها درستکارانه عمل نکنند.

این به عنوان به طور رسمی‌تر مدل BAR نامگذاری شده است؛ مدلی که برای هر دو خطای بیزانسی و منطقی به کار برده می‌شود. مدل BAR سه نوع از عاملین را در نظر می‌گیرد:

  • بیزانسی: نودهای بیزانسی مخرب هستند و سعی دارند به شما آسیب بزنند.
  • نوع‌دوست: نودهای درستکار همیشه از پروتکل پیروی می‌کنند.
  • منطقی: نودهای منطقی تنها زمانی از پروتکل پیروی می‌کنند که به نفع آن‌ها باشد.

د) انتقال پیام

همانطور که قبلا اشاره کردم، کامپیوترهای یک سیستم توزیع شده با «انتقال پیام» بین یک یا چند کامپیوتر دیگر ارتباط برقرار کرده و هماهنگ می‌شوند. پیام‌ها می‌توانند از طریق هر پروتکل پیام‌رسانی مانند HTTP، RPC، و یا یک پروتکل سفارشی انتقال داده شوند که برای کاربردی خاص ساخته شده است. دو نوع محیط انتقال پیام وجود دارد:

۱) همگام

در یک سیستم همگام، فرض می‌شود که پیام‌ها در مدت زمانی ثابت و معین تحویل داده می‌شوند.

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

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

۲) ناهمگام

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

معنای داشتن اجماع در یک سیستم توزیع شده

تاکنون، در مورد صفات زیر یک سیستم توزیع شده آموختیم:

  • همزمانی فرآیندها
  • عدم وجود یک ساعت جهانی
  • فرایندهای خطاکار
  • انتقال پیام

سپس، بر درک منظور از رسیدن به «اجماع» در یک سیستم توزیع شده تمرکز می‌کنیم. اما در ابتدا، باید چیزی را تکرار کنیم که قبلا به آن اشاره کردیم: صدها معماری سخت‌افزاری و نرم‌افزاری برای رایانش توزیع شده وجود دارد.

رایج‌ترین شکل آن دستگاه وضعیت تکثیر شده نامیده می‌شود.

دستگاه وضعیت تکثیر شده (Replicated State Machine)

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

دستگاه وضعیت تکثیر شده

شکل توسط نگارنده ترسیم شده است.

در یک دستگاه وضعیت تکثیر شده، اگر یک تراکنش معتبر باشد، مجموعه‌ای از ورودی‌ها وضعیت سیستم را به وضعیت بعدی منتقل می‌کند. تراکنش عملیاتی اتمی در یک پایگاه داده است. این به این معنی است که عملیات یا کامل انجام می‌شود و یا هرگز کامل نمی‌شود. مجموعه از تراکنش‌هایی که در دستگاه وضعیت تکثیر شده نگهداری می‌شود به عنوان «گزارش تراکنش» شناخته می‌شود.

منطق انتقال از یک وضعیت معتبر به وضعیت بعدی «منطق انتقال وضعیت» نامیده می‌شود.

دستگاه وضعیت تکثیر شده

شکل توسط نگارنده ترسیم شده است.

به عبارت دیگر، یک دستگاه وضعیت تکثیر شده مجموعه‌ای از کامپیوترهای توزیع شده است که همه با یک مقدار اولیه شروع به کار می‌کنند. برای هر انتقال وضعیت، هر یک از فرآیندها در مورد مقدار بعدی تصمیم می‌گیرد. رسیدن به «اجماع»‌ به این معنی است که همه رایانه‌ها باید جمعا در مورد خروجی این مقدار به توافق برسند.

این امر باعث داشتن یک گزارش انتقال یکدست در تمامی کامپیوترهای سیستم می‌گردد (به عبارت دیگر، کامپیوترها «به یک هدف مشترک» می‌رسند). دستگاه وضعیت تکثیر شده باید به طور مداوم تراکنش‌های جدید را به این گزارش وارد کند (یعنی «خدمتی مفید ارائه دهد»). دستگاه باید این کار را علی‌رغم موارد زیر انجام دهد:

  1. بعضی از کامپیوترها خطاکار هستند.
  2. شبکه قابل اعتماد نیست و ممکن است پیام‌ها ممکن است تحویل نشده، تأخیر داشته و یا خارج از ترتیب باشند.
  3. هیچ ساعت جهانی برای تسهیل تعیین ترتیب رویدادها وجود ندارد.

و این، هدف اصلی هر الگوریتم اجماع است.

دستگاه وضعیت تکثیر شده

شکل توسط نگارنده ترسیم شده است.

تعریف مساله اجماع

یک الگوریتم زمانی به اجماع می‌رسد که شرایط زیر احراز شده باشد:

  • توافق‌ها: تمام نودهای غیرخطاکار در مورد مقدار خروجی یکسان تصمیم‌گیری می‌کنند.
  • خاتمه دادن:‌ تمام نودهای غیرخطاکار در نهایت در مورد یک مقدار خروجی تصمیم‌گیری می‌کنند.

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

به طور کلی، الگوریتم های توافق معمولا سه دسته عمل را برای یک سیستم در نظر می‌گیرند:

  1. پیشنهاددهندگان، که اغلب به نام رهبران یا هماهنگ‌کنندگان شناخته می‌شوند.
  2. پذیرندگان، فرآیندهایی که به درخواست‌های پیشنهاددهدنگان گوش می‌دهند و مقادیر را به آن‌ها پاسخ می‌دهند.
  3. آموزندگان، فرآیندهای دیگر سیستم که مقادیر نهایی تصویب شده را می‌آموزند.

به طور کلی، می‌توانیم یک الگوریتم اجماع را در سه مرحله تعریف کنیم:

گام اول: انتخاب

  • فرآیندها یک فرآیند واحد (یعنی یک رهبر) را برای تصمیم‌گیری انتخاب می‌کنند.
  • رهبر مقدار خروجی معتبر بعدی را پیشنهاد می‌کند.

گام دوم: رای‌گیری

  • فرآیندهای غیر خطاکار به مقدار پیشنهاد شده توسط رهبر را شنیده، آن را تایید کرده و به عنوان مقدار معتبر بعدی پیشنهاد می‌کنند.

گام سوم: تصمیم‌گیری

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

https://cdn-images-1.medium.com/max/800/1*UsUuzM_AiTZbNHdnB2o0XA.png

https://cdn-images-1.medium.com/max/800/1*qG2MtVoQowMwFQjw6iezRQ.png

https://cdn-images-1.medium.com/max/800/1*i CT_kmTI1fL3LtrDqVQ.png

سیستم توزیع شده

سیستم توزیع شده

نمودارها توسط نگارنده ترسیم شده است.

باید توجه داشته باشید که هر الگوریتم اجماع در موارد زیر متفاوت است:

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

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

ساده است، اینطور نیست؟

عدم امکان FLP

اینطور نیست… اما احتمالا منتظر آن بودید!

به یاد بیاورید که چگونه تفاوت بین یک سیستم همگام و یک سیستم ناهمگام را شرح دادیم:

  • در محیط‌های همگام، پیام‌ها در یک مدت زمان ثابت تحویل می‌شوند
  • در محیط‌های ناهمگام، هیچ تضمینی برای تحویل یک پیام وجود ندارد.

این وجه تمایز اهمیت دارد.

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

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

در حقیقت، اکثر محیط‌ها اجازه نمی‌دهند تا همگام بودن جز مفروضات باشد. بنابراین ما باید محیط را ناهمگام در نظر بگیریم.

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

این موضوع به صورت رسمی به عنوان «نتیجه عدم امکان FLP» شناخته می‌شود. این نام از کجا آمده است؟ چه خوب که پرسیدید!

حتی یک فرآیند خطاکار باعث می‌شود که رسیدن به اجماع در میان فرآیندهای غیرهمگام قطعی غیر ممکن باشد.

محققان فیشر (Fischer)، لینچ (Lynch) و پیترسون (Paterson) (به طور خلاصه FLP) در مقاله سال ۱۹۸۵ خود نشان دادند که چگونه که حتی یک فرایند خطاکار باعث می‌شود که رسیدن به اجماع در میان فرآیندهای ناهمگام قطعی غیرممکن باشد. اساسا، از آن‌جایی که ممکن است فرآیندها در زمان‌های غیر قابل پیش‌بینی شکست بخورند، همچنین ممکن است که آن‌ها در دقیقا یک زمان شکست بخورند این مانع اجماع می‌گردد.

سیستم توزیع شده

شکل توسط نگارنده ترسیم شده است.

این نتیجه برای حوزه رایانش توزیع شده ناامیدکننده بود. با این وجود، دانشمندان همچنان به دنبال یافتن راهی برای دور زدن عدم امکان FLP بودند.

در سطوح بالا، دو راه برای دور زدن عدم امکان FLP وجود دارد:

  1. استفاده از مفروضات همگام.
  2. استفاده از عدم قطعیت.

بیایید تا نگاهی عمیق به این دو داشته باشیم.

روش ۱: استفاده از مفروضات همگام

می‌دانم به چه فکر می‌کنید. اصلا معنی این عبارت چیست؟

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

اما ما چگونه می‌توانیم تضمین کنیم که هر فرآیند غیر خطاکار در مورد یک مقدار نظری خواهد داشت اگر به دلیل ناهمگام بودن شبکه ندانیم که چه زمانی پیام تحویل خواهد شد؟

باید گفته شود که، این یافته به معنای غیر قابل دسترس بودن اجماع نیست. در عوض، به دلیل ناهمگام بودن، رسیدن به اجماع در یک زمان مشخص ممکن نیست. «عدم امکان» اجماع به این معنی است که اجماع «هیچ وقت ممکن نیست». این نکته‌ای ظریف اما حیاتی است.

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

Paxos

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

Paxos به این شکل عمل می‌کند:

فاز ۱: درخواست آماده‌سازی
  1. پیشنهاددهنده یک پیشنهاد جدید با شماره نسخه (n) انتخاب می‌کند و یک «درخواست آماده‌سازی» برای پذیرندگان ارسال می‌کند.
  2. اگر پذیرندگان یک درخواست آماده‌سازی ((“prepare,” n) با n بزرگتر درخواست‌هایی دریافت کنند که قبلا به آن‌ها پاسخ داده‌اند، (“ack,” n, n’, v’) یا (“ack,” n, ^ , ^) ارسال می‌کنند .
  3. پذیرندگان وعده می‌دهند که به پیشنهادهای دیگری با شماره کمتر از n را نپذیرند.
  4. پذیرندگان مقدار (V) پیشنهادی را پیشنهاد می‌کنند که دارای بالاترین شماره در میان پیشنهادهایی است که پذیرفته‌اند (در صورت وجود). یا در غیر این صورت، آن‌ها با ^ پاسخ می‌دهند.
فاز ۲: درخواست پذیرش
  1. اگر پیشنهاددهنده از اکثریت پذیرندگان پاسخ دریافت کند، می‌تواند درخواست پذیرشی را (“accept,” n, v) با شماره n و مقدار v صادر کند.
  2. n شماره‌ای است که در درخواست آماده‌سازی وجود داشت.
  3. v مقدار پیشنهاد دارای بالاترین شماره در میان پاسخ‌ها است.
  4. اگر پذیرنده یک پذیرش درخواست (“accept,” n, v) کند، پیشنهاد را قبول می‌کند، مگر اینکه قبلا به یک درخواست آماده‌سازی با شماره بالاتر از n پاسخ داده باشد.
فاز ۳: فاز آموزش
  1. هرگاه یک پذیرنده پیشنهادی را بپذیرد، به تمام آموزندگان پاسخ می‌دهد (“accept,” n, v).
  2. آموزندگان (“accept,” n, v) را از اکثر پذیرندگان دریافت کرده، در مورد v تصمیم گرفته و (“decide,” v) را به سایرآموزندگان ارسال می‌کنند.
  3. آموزندگان (“decide,” v) را دریافت کرده و در مورد V تصمیم می‌گیرند.

استفاده از مفروضات همگام

منبع: https://www.myassignmenthelp.net/paxos-algorithm-assignment-help

گیج شدید؟ می‌دانم که اطلاعات زیادی ارائه شد و شاید هضم آن‌ها کمی مشکل باشد.

اما صبر کنید… هنوز تمام نشده است!

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

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

دلیل اصلی سخت بودن درک Paxos این است که بسیاری از جزئیات پیاده‌سازی به تفسیر خواننده واگذار شده‌اند: چگونه متوجه می‌شویم که یک پیشنهاددهنده در حال شکست خوردن است؟ آیا زمانی که یک پیشنهاد دهنده در حال واماندگی است و باید به رتبه بعدی برویم از ساعت‌های همگام برای تعیین مهلت استفاده کنیم؟

در راستای فراهم آوردن انعطاف‌پذیری در پیاده‌سازی، چند صفت در زمینه‌های کلیدی با پایان باز رها شده‌اند. مواردی نظیر انتخاب رهبر، شناسایی خطا و مدیریت گزارش یا کاملا نامشخص و یا مبهم هستند.

این انتخاب در نهایت به یکی از بزرگترین معایب Paxos تبدیل شد. نه تنها درک آن، بلکه پیاده‌سازی آن نیز فوق‌العاده دشوار است. در نهایت، این امر باعث شد که فهم سیستم‌های توزیع شده به طرزی باورنکردنی مشکل باشد.

در حال حاضر شما احتمالا انتظار دارید تا ببینید فرض همگامی کجا وارد عمل می‌شود.

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

Raft

در سال ۲۰۱۳، Ongaro و Ousterhout الگوریتم اجماعی جدید برای یک دستگاه وضعیت تکثیر شده به نام Raft منتشر کردند، که در آن هدف اصلی (برخلاف Paxos) قابل درک بودن بود.

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

اما صبر کنید! محیط‌های «بیزانسی» چه می‌شود؟

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

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

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

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

به عنوان مثال، اگر رهبر منتخب بیزانسی باشد و با نودهای دیگر ارتباطات شبکه‌ای قوی داشته باشد، می‌تواند سیستم را به خطر بیندازد. به یاد بیاورید که گفتیم چگونه باید سیستم خود را مدل کنیم تا بتواند خطاهای ساده یا خطاهای بیزانسی را تحمل کند. Raft و Paxos متحمل خطای ساده هستند، اما تحمل خطای بیزانسی را ندارند. آن‌ها برای تحمل رفتارهای مخرب طراحی نشده‌اند.

«مسئله ژنرال بیزانسی»

تلاش برای ساخت یک سیستم کامپیوتری قابل اعتماد که می‌تواند به فرایندهایی رسیدگی کند که اطلاعات متناقض ارائه می‌کنند به طور رسمی به عنوان «مشکل ژنرال بیزانسی» شناخته می‌شود. پروتکلی که تحمل خطای بیزانس را دارد باید حتی در برابر رفتار مخرب نودها قادر به دستیابی به هدف مشترک خود باشد.

مقاله «مسئله ژنرال بیزانسی» نوشته لسلی لامپورت، رابرت شوستاک (Robert Shostak) و مارشال پیز (Marshall Pease) اولین اثبات برای حل مساله ژنرال بیزانسی را ارائه داد: در مقاله نشان داده شد که سیستمی با x نود بیزانسی باید حداقل 3x + 1 نود در مجموع داشته باشد تا بتواند به اجماع دست پیدا کند.

دلیل آن این است:

اگر x نود خطاکار باشند، سیستم باید پس از هماهنگی با n منهای x نود (به دلیل اینکه x نود ممکن است خطاکار/ بیزانسی باشند و پاسخ ندهند) صحیح عمل کند. اما ما باید برای این امکان آماده باشیم که شاید x بدون پاسخ خطاکار نباشد،‌ x دارای پاسخ خطاکار باشد. اگر بخواهیم تعداد نودهای غیرخطاکار بیشتر از تعداد نودهای خطاکار باشد، باید حداقل n منهای x منهای x بزرگتر از x داشته باشیم. از این رو، n> 3x + 1 بهینه است.

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

چرا؟

به طور خلاصه، ساخت یک الگوریتم اجماع که می‌تواند هم محیط ناهمگام و هم بیزانسی را تحمل کند مانند یک معجزه است.

الگوریتم‌هایی مانند Paxos و Raft به خوبی شناخته شده و به طور گسترده مورد استفاده قرار گرفته‌اند. اما همچنین کار زیادی محیط‌های آکادمیک برای حل همزمان مساله اجماع در محیط‌های هم ناهمگام و هم بیزانسی انجام شده است.

آیا «معجزه»‌ای که قبلا مورد آن صحبت کردیم را به خاطر دارید؟ ما قصد داریم نگاهی به دو الگوریتم (DLS و PBFT) بیاندازیم که ما را از هر زمان دیگری به شکستن مانع ناهمگام + بیزانسی نزدیک‌تر می‌کند.

الگوریتم DLS

مقاله «اجماع در حضور همگامی جزیی» نوشته دورک (Dwork)، لینچ (Lynch) و استاکمایر (Stockmeyer) (مبنای نام الگوریتم DLS) پیشرفتی عمده در اجماع متحمل خطار بیزانسی را به همراه داشت: این مقاله مدلی برای نحوه دستیابی به اجماع در «سیستم همگام جزیی» تعریف می‌کرد.

شاید به خاطر داشته باشید که در یک سیستم همگام، سقف ثابت شناخته‌شده‌ای برای زمان لازم برای ارسال یک پیام از یک پردازنده به یک دیگری وجود دارد. در یک سیستم ناهمگام، هیچ سقف ثابتی وجود ندارد. همگامی جزئی جایی بین این دو اکستریم است.

  •  این مقاله دو نسخه از فرض همگامی جزئی را شرح می‌دهد:
  • فرض کنید که سقف‌های ثابتی برای مدت زمان مورد نیاز برای تحویل پیام‌ها وجود دارد. اما این سقف‌ها به عنوان یک احتمال اولیه شناخته نمی‌شوند. هدف این است که بدون در نظر گرفتن سقف‌های واقعی به اجماع برسیم.
  • فرض کنید سقف تحویل پیغام شناخته‌شده است، اما تنها تضمین شده است که آن‌ها از زمانی ناشناخته شروع می‌شوند («زمان استانداردسازی جهانی»، GST). هدف این است که سیستمی طراحی کنیم که می‌تواند بدون در نظر گرفتن هنگام رخ دادن این زمان به اجماع برسد.

نحوه کار الگوریتم DLS این‌گونه است:

تعدادی دوره به مراحل «تلاش» و «قفل-آزاد» تقسیم می‌شوند.

  1. هر دور دارای یک پیشنهاددهنده است و اینگونه آغاز می‌شود که فرآیندها مقداری را اعلام می‌کنند که به باور آن‌ها صحیح است.
  2. اگر حداقلN-x فرایند این مقداری را اعلام کرده باشند پیشنهاددهنده این مقدار را «پیشنهاد» می‌دهد.
  3. هنگامی که یک فرآیند مقدار پیشنهادی را از پیشنهاددهنده دریافت می‌کند، باید مقدار بر روی آن مقدار قفل کرده و سپس این اطلاعات را پخش کند.
  4. اگر پیشنهاددهنده پیام‌هایی را ازx + 1 فرآیند دریافت کند که بر روی مقداری قفل کرده‌اند، آن مقدار را به عنوان مقدار نهایی تثبیت می‌کند.

DLS یک پیشرفت بزرگ بود، چرا که دسته‌ای جدید از فرض‌های شبکه را ایجاد کرد (مانند همگامی جزئی) و ثابت کرد که اجماع با این فرض ممکن است. دیگر ایده مهم مقاله DLS، جداسازی نگرانی‌ها برای رسیدن به اجماع در یک محیط بیزانسی و ناهمگام به دو ظرف بود: ایمنی و زنده بودن.

ایمنی

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

زنده بودن

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

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

بنابراین، این مقاله ثابت کرد که الگوریتم‌ها برای دستیابی به شرایط ایمنی نیازی به استفاده از فرض همگامی ندارند.

ساده است، اینطور نیست؟ نگران نباشید اگر اینطور فکر نمی‌کنید. بیایید نگاهی عمیق‌تر داشته باشیم.

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

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

موضوع اصلی طراحی یک سیستم توزیع شده همواره موازنه است.

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

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

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

الگوریتم PBFT

یکی دیگر از الگوریتم‌های متحمل خطای بیزانسی که در سال ۱۹۹۹ توسط میگل کاسترو (Miguel Castro) و باربارا لیسکوف (Barbara Liskov) منتشر شد، «تحمل خطای بیزانسی عملی» (PBFT) نام دارد. قرار بود این الگوریتم برای سیستم‌هایی است که رفتار بیزانسی نشان می‌دهند عملی‌تر باشد.

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

و همانطور که شرح دادیم، این امر می‌تواند در محیط ناهمگام بسیار خطرناک باشد.

به طور خلاصه، الگوریتم PBFT نشان داد که می‌تواند با فرض این کهn-1)/3) نود خطاکار هستند ایمنی و زنده بودن به ارمغان بیاورد. و همانطور که قبلا مورد بحث کردیم، این حداقل تعداد نودهایی است که برای تحمل خطاهای بیزانسی نیاز داریم. بنابراین، تاب‌آوری الگوریتم بهینه بود.

الگوریتم بدون توجه به تعداد نودهای خطاکار، ایمنی فراهم می‌کرد. به عبارت دیگر، برای ایمنی همگامی مفروض نمی‌شد. اما این الگوریتم برای زنده بودن بر همگامی تکیه می‌کرد. در بدترین حالت، n-1)/3) نود می‌توانستند خطاکار باشند و تاخیر پیام سریعتر یک محدوده زمانی مشخص رشد نمی‌کرد. بنابراین، PBFT عدم توانایی FLP را با استفاده از یک فرض همگامی برای تضمین زنده بودن دور می‌زد.

الگوریتم از میان یک سلسله «نما» حرکت می‌کرد که هر نما یک نود «اصلی» داشت (یعنی رهبر) و بقیه «پشتیبان‌» بودند. نحوه کار قدم به قدم این الگوریتم به این شکل است:

  1. تراکنش جدید در یک کلاینت اتفاق افتاده به نود اصلی اطلاع داده شده است.
  2. نود اصلی آن را به پشتیبان‌ها ارسال می‌کند.
  3. پشتیبان‌ها تراکنش را اجرا کرده و پاسخی را به کلاینت ارسال می‌کنند.
  4. کلاینت خواستارx + 1 پاسخ از پشتیبان‌ها با همان نتیجه است. این نتیجه نهایی بود و گذار وضعیت اتفاق افتاد.

اگر رهبر خطاکار نباشد، پروتکل به درستی کار می‌کند. اما فرایند تشخیص یک نود اصلی نامناسب و انتخاب مجدد نود اصلی («تغییر نما») به شدت ناکارآمد بود. به عنوان مثال، برای دستیابی به اجماع، PBFT نیاز به تعداد درجه دویی از مبادلات پیام داشت، یعنی هر کامپیوتر باید با هر کامپیوتر دیگر در شبکه ارتباط برقرار می‌کرد.

نکته: توضیح الگوریتم PBFT به طور کامل مستلزم یک پست وبلاگ مختص خود است! آن را به روز دیگری واگذار می‌کنیم.

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

مهم است که سهم PBFT در تاریخ این عرصه را در نظر بگیریم. این الگوریتم از ایده‌های انقلابی مهمی استفاده کرد که پروتکل‌های اجماع جدیدتر (به ویژه در دنیای پسابلاکچین) از آن‌ها آموخته و آن‌ها را استفاده می‌کنند.

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

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

روش ۲: عدم قطعیت

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

به اجماع ناکاموتو وارد شوید

همانطور که آموختیم، در اجماع سنتی، (f (x به این شکل تعریف شده است که یک پیشنهاددهنده و چند پذیرنده باید همه برای تصمیم‌گیری در مورد مقدار بعدی هماهنگ شده و ارتباط برقرار کنند.

اجماع سنتی به خوبی مقیاس نمی‌شود.

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

درخشش اجماع ناکاموتو در محتمل کردن گزاره فوق است. به جای این که هر نود مورد یک مقدار توافق کند، (f (xبه گونه‌ای عمل می‌کند که تمام نودها در مورد احتمال صحت آن مقدار توافق می‌کنند.

این به چه معنا است؟

تحمل خطای بیزانسی

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

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

پاداش بلاکی

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

مقاومت در برابر حمله Sybil

گواه بر کار مورد نیاز برای حل این پازل باعث می‌شود این پروتکل به طور ذاتی در برابر حمله Sybil مقاوم باشد. نیازی به PKI و یا هر طرح احراز هویت دیگر وجود ندارد.

مخابره همتا به همتا (Peer-to-peer gossip)

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

این روش «از لحاظ فنی» در محیط‌های ناهمگام امن نیست

در اجماع ناکاموتو، تضمین ایمنی احتمالی است. ما در حال تولید طولانی‌ترین چین هستیم، و هر بلاک جدید احتمال احتمال سعی نودهای مخرب جهت در ایجاد یک چین معتبر دیگر را کاهش می‌دهد.

بنابراین، اجماع ناکاموتو از لحاظ فنی امنیت را در یک محیط ناهمگام تضمین نمی‌کند. بیایید ثانیه‌ای برای درک آن تامل کنیم.

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

اجماع ناکاموتو از لحاظ فنی امنیت را در یک محیط ناهمگام تضمین نمی‌کند.

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

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

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

اجماع ناکاموتو و اجماع سنتی

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

اجماع ناکاموتو امکان داشتن مشارکت آزاد را برای هر نود فراهم می‌کند و هیچ‌کس نیازی به شناختن مجموعه کامل شرکت‌کنندگان ندارد. اهمیت این پیشرفت شایسته تاکید بسیار است. ممنون، ناکاموتو!

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

این باعث می‌شود که این الگوریتم در محیط دنیای واقعی قابل استفاده باشد. این الگوریتم واقعا پسر عموی کاربردی PBFT است.

نتیجه‌گیری

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

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

منبع: Medium.com

شاید از این مطالب هم خوشتان بیاید.

ارسال پاسخ

آدرس ایمیل شما منتشر نخواهد شد.