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

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

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

شرح مشکل [ ویرایش ]

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

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

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

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

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

گفته می شود که پروتکلی که بتواند به طور صحیح اجماع بین n فرآیندهایی را که حداکثر t آنها شکست می خورند ، t-elastic باشد ، تضمین می کند .

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

مدلهای محاسبه [ ویرایش ]

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

کانال های ارتباطی با احراز هویت مستقیم یا قابل انتقال [ ویرایش ]

در اکثر مدلهای پروتکل ارتباطی ، شرکت کنندگان از طریق کانالهای تأیید شده ارتباط برقرار می کنند . این بدان معناست که پیامها ناشناس نیستند و گیرندگان منبع هر پیامی را که دریافت می کنند می دانند. برخی از مدل ها تصدیق هویتی قوی تر و قابل انتقال را در نظر می گیرند ، جایی که هر پیام توسط فرستنده امضا می شود ، به طوری که گیرنده نه تنها منبع فوری هر پیام را بلد است ، بلکه مشارکت کننده ای است که در ابتدا پیام را ایجاد کرده است. این نوع احراز هویت قوی تر با امضای دیجیتالی به دست می آید و هنگامی که این فرم احراز هویت قوی تر موجود باشد ، پروتکل ها می توانند تعداد بیشتری از خطاها را تحمل کنند. [2]

دو مدل مختلف احراز هویت اغلب مدلهای ارتباط شفاهی و ارتباطات کتبی نامیده می شوند . در یک مدل ارتباط شفاهی ، منبع فوری اطلاعات شناخته می شود ، در حالی که در مدلهای ارتباطی قوی تر و مکتوب ، هر مرحله از گیرنده نه تنها منبع فوری پیام ، بلکه تاریخ ارتباط پیام را می آموزد. [3]

ورودی و خروجی اجماع [ ویرایش ]

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

یک مورد خاص از مسئله اجماع تک ارزش ، که اجماع دوتایی نامیده می شود ، ورودی و از این رو حوزه خروجی را به یک رقم دوتایی {0 /1} محدود می کند. اگرچه به خودی خود چندان مفید نیستند ، اما پروتکل های اجماع دوتایی اغلب به عنوان اجزای سازنده پروتکل های اجماع عمومی تر ، به ویژه برای اجماع ناهمزمان ، مفید هستند.

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

تصادف و شکست های بیزانس [ ویرایش ]

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

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

نسخه قوی تری از اجماع برای تحمل شکست های بیزانس با تقویت محدودیت صداقت ارائه می شود:

تمامیت
اگر یک روند صحیح تصمیم بگیرد ، سپس باید با فرایند صحیح پیشنهاد شده باشد

سیستمهای ناهمزمان و همزمان [ ویرایش ]

مشکل اجماع ممکن است در مورد سیستمهای ناهمزمان یا همزمان در نظر گرفته شود. در حالی که ارتباطات دنیای واقعی غالباً ذاتاً ناهمزمان هستند ، مدل سازی سیستم های همزمان بسیار کاربردی تر و اغلب آسان تر است ، [4] با توجه به اینکه سیستم های ناهمزمان به طور طبیعی مسائل بیشتری را نسبت به سیستم های همزمان شامل می شوند.

در سیستم های همزمان ، فرض بر این است که همه ارتباطات به صورت دور انجام می شود . در یک دور ، یک فرآیند ممکن است تمام پیامهای مورد نیاز را ارسال کند ، در حالی که همه پیامها را از سایر فرآیندها دریافت می کند. به این ترتیب ، هیچ پیامی از یک دور نمی تواند بر پیام های ارسال شده در همان دور تأثیر بگذارد.

نتیجه عدم امکان FLP برای اجماع قطعی ناهمزمان [ ویرایش ]

در یک سیستم توزیع شده پیام کاملا ناهمزمان ، که در آن حداقل یک فرایند ممکن است دچار خرابی شود ، در نتیجه ناممکن FLP ثابت شده است که الگوریتم قطعی برای دستیابی به اجماع غیرممکن است. [5] این نتیجه غیرممکن از بدترین سناریوهای زمانبندی نشأت می گیرد ، که بعید است در عمل اتفاق بیفتد ، مگر در موقعیتهای خصمانه مانند یک مهاجم هوشمند انکار سرویس در شبکه. در اغلب شرایط عادی ، برنامه ریزی فرایند دارای درجه تصادفی طبیعی است. [4]

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

الگوریتم های اجماعی تصادفی می توانند نتیجه غیرممکن FLP را با دستیابی به ایمنی و زنده ماندن با احتمال زیاد ، حتی در بدترین سناریوهای برنامه ریزی مانند حمله کننده انکار سرویس در شبکه ، دور بزنند. [6]

اجازه در مقابل اجماع بدون اجازه [ ویرایش ]

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

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

برابری مشکلات توافق [ ویرایش ]

سه مشکل توافق مورد علاقه به شرح زیر است.

خاتمه پخش قابل اعتماد [ ویرایش ]

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

  1. اگر فرآیند درست است ، سپس هر فرآیند صحیح دریافت می کند
  2. برای هر دو فرایند صحیح ، هر فرآیند مقدار یکسانی را دریافت می کند.

همچنین به عنوان مشکل ژنرال معروف است.

اجماع [ ویرایش ]

الزامات رسمی برای یک پروتکل اجماع ممکن است شامل موارد زیر باشد:

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

سازگاری ضعیف تعاملی [ ویرایش ]

برای n فرآیندها در یک سیستم تا حدی همزمان (سیستم بین دوره های خوب و بد هماهنگ متناوب است) ، هر فرآیند یک مقدار خصوصی را انتخاب می کند. فرآیندها برای تعیین ارزش عمومی و ایجاد بردار اجماع با الزامات زیر ، به صورت دور به دور با یکدیگر ارتباط برقرار می کنند: [7]

  1. اگر یک فرایند صحیح ارسال شود ، سپس همه فرآیندهای صحیح یا دریافت می کنند یا هیچ چیز (ویژگی یکپارچگی)
  2. همه پیام های ارسال شده در یک دور توسط یک فرایند صحیح در یک دور توسط همه فرآیندهای صحیح (ویژگی سازگاری) دریافت می شوند.

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

نتایج حل پذیری برخی مشکلات توافق [ ویرایش ]

یک پروتکل همزمان ناشناس انعطاف پذیر t وجود دارد که مشکل ژنرالهای بیزانس را حل می کند ، [10] [11] اگر و پرونده ژنرالهای ضعیف بیزانس [8] در آنجا تعداد شکست ها است و تعداد فرایندها است.

برای سیستم های با پردازنده ها ، که از آنها بیزانسی هستند ، نشان داده شده است که هیچ الگوریتمی وجود ندارد که مشکل اجماع را حل کند در مدل دهان و پیام . [12] اثبات به این صورت است که ابتدا عدم امکان برای مورد سه گره ای نشان داده می شودو از این نتیجه برای بحث در مورد پارتیشن پردازنده ها استفاده کنید. در مدل پیام های مکتوب پروتکل هایی وجود دارد که می توانند تحمل کنندبه [2]

در یک سیستم کاملاً ناهمزمان هیچ راه حل اجماعی وجود ندارد که بتواند یک یا چند خرابی تصادف را تحمل کند حتی زمانی که فقط به ویژگی بی اهمیتی نیاز دارد. [5] این نتیجه است که گاهی اوقات اثبات FLP عدم امکان پس از نویسندگان به نام به نام مایکل جی فیشر ، نانسی لینچ ، و مایک پاترسون که اهدا شد جایزه دیکسترا برای این کار قابل توجه است. نتیجه FLP به صورت مکانیکی تأیید شده است که حتی در فرض انصاف نیز وجود دارد . [13] با این حال ، FLP بیان نمی کند که هرگز نمی توان به اجماع رسید: صرفاً طبق مفروضات مدل ، هیچ الگوریتمی نمی تواند همیشه در زمان محدود به اجماع برسد. در عمل احتمال وقوع آن بسیار کم است.

برخی پروتکل های اجماع [ ویرایش ]

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

الگوریتم Phase King [14] توسط گارای و برمن ، نمونه ای از پروتکل اجماع زمان چند جمله ای دوتایی است که شکست های بیزانس را تحمل می کند . این الگوریتم در یک مدل انتقال پیام همزمان با n فرآیندها و تا f شکست ، با شرط n > 4 f ، اجماع را حل می کند . در الگوریتم فاز کینگ ، f وجود دارد+ 1 فاز ، با 2 دور در هر فاز. هر فرآیند خروجی ترجیحی خود (در ابتدا برابر با مقدار ورودی خود فرآیند) را پیگیری می کند. در دور اول هر مرحله ، هر فرآیند مقدار ترجیحی خود را برای سایر فرآیندها پخش می کند. سپس مقادیر را از تمام فرآیندها دریافت می کند و تعیین می کند که مقدار اکثریت و تعداد آن کدام است. در دور دوم مرحله ، فرآیندی که شناسه آن با شماره فاز فعلی مطابقت دارد ، پادشاه مرحله تعیین می شود. پادشاه ارزش اکثریتی را که در دور اول مشاهده کرده بود ، پخش می کند و به عنوان برنده کراوات عمل می کند. سپس هر فرآیند مقدار مورد نظر خود را به صورت زیر به روز می کند. اگر شمارش مقدار اکثریت ، فرایند مشاهده شده در دور اول بیشتر از n /2 + f باشد، فرآیند ترجیح خود را به آن مقدار اکثریت تغییر می دهد. در غیر این صورت از ارزش پادشاه فاز استفاده می کند. در پایان مراحل f + 1 ، فرآیندها مقادیر دلخواه خود را خروجی می دهند.

گوگل یک کتابخانه خدمات قفل توزیع شده به نام Chubby را پیاده سازی کرده است . [15] Chubby اطلاعات قفل را در پرونده های کوچک ذخیره می کند که در پایگاه داده تکراری ذخیره می شوند تا در صورت خرابی در دسترس باشند. پایگاه داده در بالای یک لایه ورود به سیستم مقاوم در برابر خطا که بر اساس الگوریتم اجماع Paxos اجرا شده است ، پیاده سازی شده است . در این طرح ، کلاینت های چاق با استاد Paxos ارتباط برقرار می کنند تا به گزارش تکراری دسترسی پیدا کنند/به روز کنند. به عنوان مثال ، خواندن/نوشتن در پرونده ها. [16]

بسیاری از بازیهای آنلاین استراتژی همتا به همتا از پروتکل اصلاح شده Lockstep به عنوان یک پروتکل اجماعی برای مدیریت وضعیت بازی بین بازیکنان در یک بازی استفاده می کنند. هر عمل بازی منجر به پخش دلتا حالت بازی برای همه بازیکنان دیگر بازی به همراه یک هش از کل وضعیت بازی می شود. هر بازیکن با اعمال دلتا در حالت بازی خود و مقایسه هش های حالت بازی ، تغییر را تأیید می کند. اگر هش ها موافق نباشند رأی داده می شود و آن دسته از بازیکنانی که وضعیت بازی آنها در اقلیت است قطع می شوند و از بازی حذف می شوند (معروف به desync.)

یکی دیگر از روشهای شناخته شده ، الگوریتم های نوع MSR نام دارد که از علوم رایانه برای کنترل نظریه استفاده می شود. [17] [18] [19]

منبع همگام سازی احراز هویت آستانه دورها یادداشت
Pease-Shostak-Lamport [10] همزمان دهانی ارتباط کل
Pease-Shostak-Lamport [10] همزمان نوشته شده است ارتباط کل
بن اور [20] نامتقارن دهانی (انتظار می رود) انتظار می رود دور زمانی که
دولف و همکاران [21] همزمان دهانی ارتباط کل
Dolev-Strong [2] همزمان نوشته شده است ارتباط کل
Dolev-Strong [2] همزمان نوشته شده است ارتباط کل
فلدمن میکالی [22] همزمان دهانی (انتظار می رود)
کاتز کو [23] همزمان نوشته شده است (انتظار می رود) به PKI نیاز دارد
PBFT [24] ناهمزمان (ایمنی)- همزمان (زنده بودن) دهانی
HoneyBadger [25] نامتقارن دهانی (انتظار می رود) در ارتباط tx - نیاز به رمزگذاری کلید عمومی دارد
ابراهیم و همکاران [26] همزمان نوشته شده است
توافق بیزانس بی اهمیت شد [27] [28] همزمان امضا (انتظار می رود) نیاز به امضای دیجیتالی دارد

پروتکل های اجماع بدون اجازه [ ویرایش ]

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

دیگر cryptocurrencies (یعنی DASH، NEO، Stratis خیلی، ...) استفاده اثبات سهام ، که در آن گره رقابت برای اضافه بلوک ها و کسب پاداش در ارتباط به نسبت سهام ، و یا cryptocurrency به موجود اختصاص داده و قفل شده است و یا بنا برای برخی از زمان. یکی از مزایای "اثبات سهام" نسبت به سیستم "اثبات کار" ، مصرف بالای انرژی مورد نیاز این دومی ، حداقل با فناوری فعلی است. به عنوان مثال ، تخمین زده می شود که استخراج بیت کوین (2018) از منابع انرژی تجدید ناپذیر به میزان کل کشورهای جمهوری چک یا اردن استفاده می کند. [29]

برخی ارزهای رمزنگاری شده مانند ریپل از سیستم اعتبار سنجی گره ها برای اعتبار سنجی دفتر کل استفاده می کنند. این سیستم که توسط Ripple مورد استفاده قرار می گیرد و Ripple Protocol Consensus Algorithm (RPCA) نامیده می شود ، به صورت دور کار می کند: مرحله 1: هر سرور لیستی از معاملات نامزد معتبر را تهیه می کند. مرحله 2: هر سرور تمام نامزدها را که از لیست گره های منحصر به فرد (UNL) خود ادغام شده اند و به صحت آنها رأی می دهد. مرحله 3: معاملات با عبور از حداقل آستانه به دور بعدی منتقل می شود. مرحله 4: دور نهایی نیاز به توافق 80٪ دارد [30]

سایر قوانین مشارکت که در پروتکل های اجماع بدون مجوز برای تحمیل موانع ورود و مقاومت در برابر حملات سیبیل استفاده می شود شامل اثبات قدرت ، اثبات فضا ، اثبات سوختگی یا اثبات زمان سپری شده است. این جایگزین ها مجدداً به دلیل مقدار زیاد انرژی محاسباتی مصرف شده توسط اثبات کار ایجاد می شوند. [31] اثبات فضا توسط cryptocoins مانند Burstcoin استفاده می شود.

برخلاف قوانین مشارکت بدون مجوز فوق ، که همه آنها متناسب با میزان سرمایه گذاری در برخی اقدامات یا منابع به شرکت کنندگان پاداش می دهند ، اثبات پروتکل های شخصیتی این است که به هر شرکت کننده انسانی واقعی دقیقاً یک واحد قدرت رأی با اجماع بدون مجوز ، صرف نظر از سرمایه گذاری اقتصادی ، اعطا شود. به [32] [33] رویکردهای پیشنهادی برای دستیابی به توزیع قدرت به ازای هر فرد برای اثبات شخصیت شامل احزاب مستعار فیزیکی ، [34] شبکه های اجتماعی ، [35] هویت های مستعار دولتی صادر شده ، [36] و بیومتریک است. [37]

شماره اجماع [ ویرایش ]

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

تعداد اجماع از یک جسم همزمان است تعریف می شود حداکثر تعداد فرآیندها در سیستم که می تواند اجماع شده توسط شی داده شده در یک برنامه رایگان برای اجرای صبر برسد. [38] اشیاء با تعداد اجماع از می تواند هر شی را با تعداد اجماع پیاده سازی کند یا پایین تر ، اما نمی تواند هیچ شیئی با تعداد اجماع بیشتر پیاده سازی کند. اعداد اجماعی آنچه سلسله مراتب اشیاء همگام سازی هرلیه نامیده می شود را تشکیل می دهد. [39]

شماره اجماع اشیاء
ثبت های خواندن/نوشتن اتمی ، mutex
تست و تنظیم ، مبادله ، واکشی و افزودن ، صف یا پشته بدون انتظار
... ...
تکلیف n-register
... ...
مقایسه و مبادله ، بارگذاری پیوند/فروشگاه شرطی ، [40] حرکت و تعویض حافظه به حافظه ، صف با عمل نگاه کردن ، واکشی و منفی ، بایت چسبنده

طبق سلسله مراتب ، ثبت های خواندن/نوشتن حتی در یک سیستم 2 فرآیند نمی توانند اجماع را حل کنند. ساختارهای داده مانند پشته و صف فقط می توانند اجماع بین دو فرایند را حل کنند. با این حال ، برخی از اشیاء همزمان جهانی هستند (در جدول با نشان داده شده است) ، به این معنی که آنها می توانند اجماع بین هر تعداد فرآیند را حل کنند و می توانند هر شی دیگری را از طریق دنباله عملیات شبیه سازی کنند. [38]

همچنین ببینید [ ویرایش ]

مراجع [ ویرایش ]

  1. ^ a b c Coulouris، George؛ ژان دولیمور ؛ تیم کیندبرگ (2001) ، سیستم های توزیع شده: مفاهیم و طراحی (چاپ سوم) ، ادیسون وسلی ، ص. 452 ، شابک 978-0201-61918-8
  2. ^ a b c d Dolev، D .؛ قوی ، منابع انسانی (1983). "الگوریتم های معتبر برای توافق بیزانس". مجله محاسبات SIAM . 12 (4): 656-666. doi : 10.1137/0212045 .
  3. ^ گونگ ، لی ؛ لینکلن ، پاتریک ؛ راشبی ، جان (1995). "توافق بیزانس با احراز هویت" . اعتماد رایانه برای برنامه های کاربردی مهم . 10 .
  4. ^ a b Aguilera، MK (2010). "سرپوش گذاشتن بر تحقیقات اجماعی: سوء تفاهم ها و مسائل". تکرار . نکات سخنرانی در علوم کامپیوتر. 5959 . صص 59-72. doi : 10.1007/978-3-642-11294-2_4 . شابک 978-3-642-11293-5به
  5. ^ a b فیشر ، MJ ؛ لینچ ، NA ؛ پترسون ، MS (1985). "عدم امکان اجماع توزیع شده با یک فرایند معیوب" (PDF) . مجله ACM . 32 (2): 374-382. doi : 10.1145/3149.214121 . S2CID 207660233 .  
  6. ^ آسپنز ، جیمز (مه 1993). "اجماع تصادفی کارآمد در زمان و مکان" . مجله الگوریتم ها . 14 (3): 414-431. doi : 10.1006/jagm.1993.1022 .
  7. ^ میلوسویچ ، زارکو ؛ مارتین هاتل ؛ آندره شیپر (2009). وحدت بیزانس اجماع الگوریتم با ضعیف تعاملی سازگاری . اصول سیستم های توزیع شده ، یادداشت های سخنرانی در علوم کامپیوتر . نکات سخنرانی در علوم کامپیوتر. 5293 . صص  300-314 . CiteSeerX 10.1.1.180.4229 . doi : 10.1007/978-3-642-10877-8_24 . شابک  978-3-642-10876-1به
  8. ^ a b Lamport، L. (1983). "مشکل ژنرالهای ضعیف بیزانس". مجله ACM . 30 (3): 668. doi : 10.1145/2402.322398 . S2CID 1574706 . 
  9. ^ فیشر ، مایکل ج. "مشکل اجماع در سیستم های توزیع نشده غیرقابل اعتماد (یک بررسی مختصر)" (PDF) . بازبینی شده در 21 آوریل 2014 .
  10. ^ a b c Lamport، L .؛ شوستاک ، آر. پیز ، م. (1982). "مشکل ژنرالهای بیزانس" (PDF) . معاملات ACM در زبانها و سیستمهای برنامه نویسی . 4 (3): 382-401. CiteSeerX 10.1.1.64.2312 . doi : 10.1145/357172.357176 .  
  11. ^ لامپورت ، لزلی ؛ مارشال پیز ؛ روبرت شوستاک (آوریل 1980). "دستیابی به توافق در حضور خطاها" (PDF) . مجله ACM . 27 (2): 228–234. CiteSeerX 10.1.1.68.4044 . doi : 10.1145/322186.322188 . S2CID 6429068 . بازیابی شده 2007-07-25 .   
  12. ^ Attiya، Hagit (2004). Computing Distributed 2nd Ed . ویلی صص 101-103. شابک 978-0-471-45324-6به
  13. ^ بیسپینگ ، بنیامین ؛ و همکاران (2016) ، بلانشت ، جاسمین کریستین ؛ مرز ، استفان (ویراستاران) ، تأیید مکانیکی اثبات سازنده برای FLP ، یادداشت های سخنرانی در علوم کامپیوتر ، 9807 ، نشر بین المللی اسپرینگر ، doi : 10.1007/978-3-319-43144-4_7 ، ISBN 978-3-319-43144-4
  14. ^ برمن و Piotr؛ خوان A. Garay (1993). "آرای لخته شدن: اجماع توزیع شده با انعطاف پذیری n/4 در دورهای t + 1". نظریه سیستم های محاسباتی . 2. 26 : 3-19. doi : 10.1007/BF01187072 . S2CID 6102847 . 
  15. ^ Burrows، M. (2006). سرویس قفل چوبی برای سیستم های توزیع شده (PDF) . مجموعه مقالات هفتمین سمپوزیوم طراحی و پیاده سازی سیستم عامل ها . انجمن USENIX برکلی ، کالیفرنیا ، ایالات متحده صص 335–350.
  16. ^ C. ، Tushar ؛ گریسمر ، آر. Redstone J. (2007). Paxos Made Live - یک دیدگاه مهندسی (PDF) . مجموعه مقالات بیست و ششم سمپوزیوم سالانه ACM مبانی محاسبات توزیع شده . پورتلند ، اورگن ، ایالات متحده: ACM Press نیویورک ، نیویورک ، ایالات متحده صص 398–407. doi : 10.1145/1281100.1281103 . بایگانی شده از نسخه اصلی (PDF) در 2014-12-12 . بازیابی شده 2008-02-06 .
  17. ^ LeBlanc، Heath J. (آوریل 2013). "اجماع مقاومتی بدون علامت در شبکه های قوی". مجله IEEE در زمینه های منتخب در ارتباطات . 31 (4): 766-781. CiteSeerX 10.1.1.310.5354 . doi : 10.1109/JSAC.2013.130413 . S2CID 11287513 .  
  18. ^ دیباجی ، SM (مه 2015). "اجماع سیستم های چند عاملی مرتبه دوم در حضور گسل های محدود شده محلی". سیستم های کنترل و نامه . 79 : 23-29. doi : 10.1016/j.sysconle.2015.02.005 .
  19. ^ دیباجی ، SM (جولای 2017). "اجماع انعطاف پذیر شبکه های عامل مرتبه دوم: قوانین به روز رسانی ناهمزمان با تاخیر". اتوماتیکا . 81 : 123-132. arXiv : 1701.03430 . کد کتاب : 2017arXiv170103430M . doi : 10.1016/j.automatica.2017.03.008 . S2CID 7467466 . 
  20. ^ بن اور ، مایکل (1983). "مزیت دیگر انتخاب آزاد (چکیده گسترده): پروتکل های توافق کاملاً ناهمزمان". مجموعه مقالات دومین همایش سالانه ACM در زمینه اصول محاسبات توزیع شده . صص 27-30. doi : 10.1145/800221.806707 . S2CID 38215511 . 
  21. ^ دولف ، دنی ؛ فیشر ، مایکل جی. فاولر ، راب ؛ لینچ ، نانسی ؛ قوی ، اچ ریموند (1982). "یک الگوریتم کارآمد برای توافق بیزانس بدون احراز هویت". اطلاعات و کنترل . 52 (3): 257–274. doi : 10.1016/S0019-9958 (82) 90776-8 .
  22. ^ فلدمن ، پشیش ؛ میکالی ، سیلویو (1997). یک پروتکل احتمالی مطلوب برای توافق بیزانس همزمان . SIAM Journal on Computing (گزارش فنی). doi : 10.1137/S0097539790187084 .
  23. ^ کاتز ، جاناتان ؛ کو ، چیو-یوئن (2006). در مورد پروتکل های دور دائمی مورد انتظار برای توافق بیزانس . CRYPTO doi : 10.1007/11818175_27 .
  24. ^ کاسترو ، میگل ؛ لیسکوف ، باربارا (1999). تحمل گسل بیزانس عملی (PDF) . OSDI
  25. ^ میلر ، اندرو ؛ شیا ، یو ؛ کرمان ، کایل ؛ شی ، ایلین ؛ آهنگ ، سپیده دم (2016). نشانگر عسل پروتکل های BFT . CCS doi : 10.1145/2976749.2978399 .
  26. ^ ابراهیم ، ایتای ؛ Devadas ، Srinivas ؛ دولف ، دنی ؛ نایاک ، کارتیک ؛ رن ، لینگ (2017). اجماع کارآمد بیزانس (گزارش فنی).
  27. ^ Micali، Sylvio (2018). "توافق بیزانس بی اهمیت شد" (PDF) . مجله استناد نیاز دارد |journal=( کمک )
  28. ^ چن ، جینگ ؛ میکالی ، سیلویو (2016). "ALGORAND". arXiv : 1607.01341v9 [ cs.CR ].
  29. ^ عرفان، عمیر (2019 ژوئن 18). "بیت کوین یک گراز انرژی است. این همه برق از کجا می آید؟" به بورسی .
  30. ^ Schwartz D، YoungsN، Britto A. 2014 الگوریتم اجماع پروتکل Ripple
  31. ^ راهکارهای جایگزین برای اثبات کار چیست؟
  32. ^ ماریا بورگه، الفترویس Kokoris-Kogias، فیلیپ جووانوویچ، لینوس گاسر، نیکولا Gailly، برایان فورد (29 آوریل 2017). اثبات شخصیت: مردمی سازی مجدد ارزهای رمزنگاری شده بدون مجوز . امنیت و حریم خصوصی IEEE در بلاک چین (IEEE S&B) . doi : 10.1109/EuroSPW.2017.46 .حفظ CS1: از پارامتر نویسندگان استفاده می کند ( پیوند )
  33. ^ دیویا سیدارت ، سرگئی ایلیف ، سانتیاگو سیری ، پائولا برمن (13 اکتبر 2020). "چه کسی دیده بان ها را می بیند؟ مروری بر رویکردهای ذهنی برای مقاومت سیبیل در اثبات پروتکل های شخصیت". arXiv : 2008.05300 [ cs.CR ].CS1 maint: uses authors parameter (link)
  34. ^ فورد ، برایان ؛ اشتراوس ، یعقوب (1 آوریل 2008). بنیاد آفلاین برای نامهای مستعار حسابدار آنلاین . اولین کارگاه آموزشی سیستم های شبکه های اجتماعی - SocialNets '08 . صص 31-6. doi : 10.1145/1435497.1435503 . شابک 978-1-60558-124-8به
  35. ^ گال شهاف ، ایهود شاپیرو ، نمرود تالمون (اکتبر 2020). شناسه های شخصی واقعی و تضمین های متقابل برای رشد جامعه مقاوم در برابر سیبیل . کنفرانس بین المللی انفورماتیک اجتماعی . doi : 10.1007/978-3-030-60975-7_24 .CS1 maint: uses authors parameter (link)
  36. ^ دیپاک مرام ، هارجاسلین مالوائی ، فن ژانگ ، نرلا ژان لوئیس ، الکساندر فرولوف ، تایلر کل ، تایرون لوبن ، کریستین موی ، آری ژولز ، اندرو میلر (28 سپتامبر 2020). "CanDID: Can-Do هویت غیر متمرکز با سازگاری قدیمی ، Sybil-Resistance و مسئولیت پذیری" (PDF) . CS1 maint: uses authors parameter (link)
  37. ^ محمدجواد حاجیالی خانی ، محمد مهدی جهان آرا (20 ژوئن 2018). "UniqueID: اثبات غیرمتمرکز انسان منحصر به فرد". arXiv : 1806.07583 .CS1 maint: uses authors parameter (link)
  38. ^ a b Herlihy ، موریس. "همگام سازی بدون انتظار" (PDF) . بازبینی شده در 19 دسامبر 2011 .
  39. ^ ایمبس ، دامین ؛ رینال ، میشل (25 ژوئیه 2010). "قدرت ضرب اعداد اجماع" (PDF) . مجموعه مقالات بیست و نهمین همایش ACM SIGACT-SIGOPS در زمینه اصول محاسبات توزیع شده . انجمن ماشین آلات محاسباتی: 26-35. doi : 10.1145/1835698.1835705 . شابک  9781605588889به S2CID  3179361 . بازبینی شده در 22 آوریل 2021 .
  40. ^ ثروت ، ایمان ؛ هندلر ، دنی ؛ شویت ، نیر (25 ژوئیه 2004). "در مورد ضعف ذاتی اولیه های همگام سازی مشروط". مجموعه مقالات بیست و سومین سمپوزیوم سالانه ACM در زمینه اصول محاسبه توزیع شده . انجمن ماشین آلات محاسباتی: 80-87. CiteSeerX 10.1.1.96.9340 . doi : 10.1145/1011767.1011780 . شابک  1581138024به S2CID  9313205 .

خواندن بیشتر [ ویرایش ]