कॉन्सेंसस (कंप्यूटर विज्ञान)

वितरित कंप्यूटिंग और बहु-एजेंट प्रणाली में एक मूलभूत समस्या कई दोषपूर्ण प्रक्रियाओं की उपस्थिति में समग्र सिस्टम विश्वसनीयता हासिल करना है। आम सहमति तक पहुंचने के लिए, या गणना के दौरान आवश्यक कुछ डेटा मान पर सहमत होने के लिए अक्सर समन्वय प्रक्रियाओं की आवश्यकता होती है। आम सहमति के उदाहरण अनुप्रयोगों में इस बात पर सहमति शामिल है कि डेटाबेस में किस क्रम में कौन से लेनदेन करने हैं, राज्य मशीन प्रतिकृति और परमाणु प्रसारण। वास्तविक दुनिया के अनुप्रयोगों में अक्सर आम सहमति की आवश्यकता होती है जिसमें क्लाउड कम्प्यूटिंग , घड़ी तुल्यकालन, पृष्ठ रैंक , राय गठन, समार्ट ग्रिड , राज्य अनुमान, मानव रहित हवाई वाहन (और सामान्य रूप से कई रोबोट/एजेंट), लोड संतुलन (कंप्यूटिंग), ब्लॉकचेन और अन्य शामिल हैं।

समस्या विवरण

सर्वसम्मति की समस्या के लिए एकल डेटा मान के लिए कई प्रक्रियाओं (या एजेंटों) के बीच सहमति की आवश्यकता होती है। कुछ प्रक्रियाएँ (एजेंट) अन्य तरीकों से विफल या अविश्वसनीय हो सकती हैं, इसलिए सर्वसम्मति प्रोटोकॉल दोष-सहिष्णु या लचीला होना चाहिए। प्रक्रियाओं को किसी तरह अपने उम्मीदवार मूल्यों को सामने रखना चाहिए, एक दूसरे के साथ संवाद करना चाहिए और एकल सर्वसम्मति मूल्य पर सहमत होना चाहिए।

मल्टी-एजेंट सिस्टम के नियंत्रण में सर्वसम्मति की समस्या एक मूलभूत समस्या है। सर्वसम्मति उत्पन्न करने का एक तरीका सभी प्रक्रियाओं (एजेंटों) के लिए बहुमत मूल्य पर सहमत होना है। इस संदर्भ में, बहुमत के लिए कम से कम आधे से अधिक उपलब्ध वोटों की आवश्यकता होती है (जहां प्रत्येक प्रक्रिया को एक वोट दिया जाता है)। हालाँकि, एक या अधिक दोषपूर्ण प्रक्रियाएँ परिणामी परिणाम को इस तरह बिगाड़ सकती हैं कि आम सहमति नहीं बन सकती है या गलत तरीके से पहुँच सकती है।

सर्वसम्मति की समस्याओं को हल करने वाले प्रोटोकॉल सीमित संख्या में दोषपूर्ण प्रक्रिया (कंप्यूटिंग) से निपटने के लिए डिज़ाइन किए गए हैं। उपयोगी होने के लिए इन प्रोटोकॉल को कई आवश्यकताओं को पूरा करना होगा। उदाहरण के लिए, एक तुच्छ प्रोटोकॉल में सभी प्रक्रियाओं का आउटपुट बाइनरी मान 1 हो सकता है। यह उपयोगी नहीं है और इस प्रकार आवश्यकता को इस तरह संशोधित किया गया है कि आउटपुट किसी तरह इनपुट पर निर्भर होना चाहिए। अर्थात्, सर्वसम्मति प्रोटोकॉल का आउटपुट मान किसी प्रक्रिया का इनपुट मान होना चाहिए। एक और आवश्यकता यह है कि एक प्रक्रिया केवल एक बार आउटपुट मूल्य पर निर्णय ले सकती है और यह निर्णय अपरिवर्तनीय है। किसी प्रक्रिया को निष्पादन में सही कहा जाता है यदि उसमें विफलता का अनुभव नहीं होता है। रुकने की विफलताओं को सहन करने वाले एक सर्वसम्मति प्रोटोकॉल को निम्नलिखित गुणों को पूरा करना चाहिए।^[1]

समाप्ति: अंततः, प्रत्येक सही प्रक्रिया कुछ मूल्य तय करती है।
अखंडता: यदि सभी सही प्रक्रियाएं समान मान प्रस्तावित करती हैं $v$ , तो कोई भी सही प्रक्रिया तय करनी होगी $v$ .
समझौता: प्रत्येक सही प्रक्रिया को समान मूल्य पर सहमत होना चाहिए।

आवेदन के अनुसार, अखंडता की परिभाषा में बदलाव उचित हो सकते हैं। उदाहरण के लिए, एक कमजोर प्रकार की अखंडता तब होगी जब निर्णय मूल्य किसी सही प्रक्रिया द्वारा प्रस्तावित मूल्य के बराबर हो - जरूरी नहीं कि सभी हों।^[1]साहित्य में वैधता के रूप में जानी जाने वाली एक शर्त भी है जो उस संपत्ति को संदर्भित करती है कि एक प्रक्रिया द्वारा भेजा गया संदेश वितरित किया जाना चाहिए।^[1]

एक प्रोटोकॉल जो एन प्रक्रियाओं के बीच आम सहमति की सही ढंग से गारंटी दे सकता है, जिनमें से अधिकांश टी विफल हो जाती है, उसे टी-लचीला कहा जाता है।

सर्वसम्मति प्रोटोकॉल के प्रदर्शन का मूल्यांकन करने में रुचि के दो कारक चल रहे समय और संदेश जटिलता हैं। बिग ओ अंकन में रनिंग टाइम कुछ इनपुट पैरामीटर्स (आमतौर पर प्रक्रियाओं की संख्या और/या इनपुट डोमेन के आकार) के फ़ंक्शन के रूप में संदेश एक्सचेंज के राउंड की संख्या में दिया जाता है। संदेश जटिलता प्रोटोकॉल द्वारा उत्पन्न संदेश ट्रैफ़िक की मात्रा को संदर्भित करती है। अन्य कारकों में मेमोरी उपयोग और संदेशों का आकार शामिल हो सकते हैं।

गणना के मॉडल

गणना के अलग-अलग मॉडल सर्वसम्मति की समस्या को परिभाषित कर सकते हैं। कुछ मॉडल पूरी तरह से जुड़े ग्राफ़ से निपट सकते हैं, जबकि अन्य छल्ले और पेड़ों से निपट सकते हैं। कुछ मॉडलों में संदेश प्रमाणीकरण की अनुमति है, जबकि अन्य में प्रक्रियाएँ पूरी तरह से गुमनाम हैं। साझा मेमोरी मॉडल जिसमें प्रक्रियाएं साझा मेमोरी में वस्तुओं तक पहुंच कर संचार करती हैं, वे भी अनुसंधान का एक महत्वपूर्ण क्षेत्र हैं।

प्रत्यक्ष या हस्तांतरणीय प्रमाणीकरण के साथ संचार चैनल

संचार प्रोटोकॉल के अधिकांश मॉडलों में प्रतिभागी प्रमाणित चैनलों के माध्यम से संवाद करते हैं। इसका मतलब यह है कि संदेश गुमनाम नहीं होते हैं, और प्राप्तकर्ता उन्हें प्राप्त होने वाले प्रत्येक संदेश का स्रोत जानते हैं। कुछ मॉडल प्रमाणीकरण का एक मजबूत, हस्तांतरणीय रूप मानते हैं, जहां प्रत्येक संदेश पर प्रेषक द्वारा हस्ताक्षर किए जाते हैं, ताकि प्राप्तकर्ता न केवल प्रत्येक संदेश के तत्काल स्रोत को जानता है, बल्कि उस भागीदार को भी जानता है जिसने शुरू में संदेश बनाया था। प्रमाणीकरण का यह मजबूत प्रकार डिजिटल हस्ताक्षरों द्वारा प्राप्त किया जाता है, और जब प्रमाणीकरण का यह मजबूत रूप उपलब्ध होता है, तो प्रोटोकॉल बड़ी संख्या में दोषों को सहन कर सकते हैं।^[2] दो अलग-अलग प्रमाणीकरण मॉडल को अक्सर मौखिक संचार और लिखित संचार मॉडल कहा जाता है। मौखिक संचार मॉडल में, सूचना का तत्काल स्रोत ज्ञात होता है, जबकि मजबूत, लिखित संचार मॉडल में, रिसीवर के हर कदम पर न केवल संदेश का तत्काल स्रोत पता चलता है, बल्कि संदेश का संचार इतिहास भी पता चलता है।^[3]

सर्वसम्मति के इनपुट और आउटपुट

पैक्सोस (कंप्यूटर विज्ञान) जैसे सबसे पारंपरिक एकल-मूल्य सर्वसम्मति प्रोटोकॉल में, सहयोगी नोड्स एक पूर्णांक जैसे एकल मान पर सहमत होते हैं, जो परिवर्तनीय आकार का हो सकता है ताकि डेटाबेस के लिए प्रतिबद्ध लेनदेन जैसे उपयोगी मेटा डेटा को एन्कोड किया जा सके।

एकल-मूल्य सर्वसम्मति समस्या का एक विशेष मामला, जिसे बाइनरी सर्वसम्मति कहा जाता है, इनपुट और इसलिए आउटपुट डोमेन को एकल बाइनरी अंक {0,1} तक सीमित करता है। हालांकि अपने आप में अत्यधिक उपयोगी नहीं, बाइनरी सर्वसम्मति प्रोटोकॉल अक्सर अधिक सामान्य सर्वसम्मति प्रोटोकॉल में बिल्डिंग ब्लॉक के रूप में उपयोगी होते हैं, खासकर अतुल्यकालिक सर्वसम्मति के लिए।

पैक्सोस (कंप्यूटर विज्ञान)#मल्टी-पैक्सोस|मल्टी-पैक्सोस और राफ्ट (एल्गोरिदम) जैसे बहु-मूल्यवान सर्वसम्मति प्रोटोकॉल में, लक्ष्य केवल एक मूल्य पर नहीं बल्कि समय के साथ मूल्यों की एक श्रृंखला पर सहमत होना है, जो उत्तरोत्तर बनता है- बढ़ता इतिहास. जबकि उत्तराधिकार में एकल-मूल्यवान सर्वसम्मति प्रोटोकॉल के कई पुनरावृत्तियों को चलाकर बहु-मूल्यवान सर्वसम्मति को भोलेपन से प्राप्त किया जा सकता है, कई अनुकूलन और पुनर्विन्यास समर्थन जैसे अन्य विचार बहु-मूल्यवान सर्वसम्मति प्रोटोकॉल को व्यवहार में अधिक कुशल बना सकते हैं।

दुर्घटना और बीजान्टिन विफलताएँ

एक प्रक्रिया दो प्रकार की विफलताओं से गुजर सकती है, एक क्रैश विफलता या एक बीजान्टिन विफलता। क्रैश विफलता तब होती है जब कोई प्रक्रिया अचानक बंद हो जाती है और फिर से शुरू नहीं होती है। बीजान्टिन विफलताएँ ऐसी विफलताएँ हैं जिनमें बिल्कुल कोई शर्त नहीं लगाई जाती है। उदाहरण के लिए, वे किसी विरोधी के दुर्भावनापूर्ण कार्यों के परिणामस्वरूप घटित हो सकते हैं। एक प्रक्रिया जो बीजान्टिन विफलता का अनुभव करती है वह अन्य प्रक्रियाओं को विरोधाभासी या विरोधाभासी डेटा भेज सकती है, या यह सो सकती है और फिर लंबी देरी के बाद गतिविधि फिर से शुरू कर सकती है। दो प्रकार की विफलताओं में से, बीजान्टिन विफलताएँ कहीं अधिक विघटनकारी हैं।

इस प्रकार, बीजान्टिन विफलताओं को सहन करने वाला एक सर्वसम्मति प्रोटोकॉल हर संभावित त्रुटि के प्रति लचीला होना चाहिए।

बीजान्टिन विफलताओं को सहन करने वाली आम सहमति का एक मजबूत संस्करण सत्यनिष्ठा बाधा को मजबूत करके दिया गया है:

अखंडता: यदि एक सही प्रक्रिया निर्णय लेती है $v$ , तब $v$ किसी सही प्रक्रिया द्वारा प्रस्तावित किया गया होगा।

अतुल्यकालिक और तुल्यकालिक सिस्टम

एसिंक्रोनस या सिंक्रोनस सिस्टम के मामले में सर्वसम्मति की समस्या पर विचार किया जा सकता है। जबकि वास्तविक विश्व संचार अक्सर स्वाभाविक रूप से अतुल्यकालिक होते हैं, तुल्यकालिक प्रणालियों को मॉडल करना अधिक व्यावहारिक और अक्सर आसान होता है,^[4] यह देखते हुए कि एसिंक्रोनस सिस्टम में स्वाभाविक रूप से सिंक्रोनस सिस्टम की तुलना में अधिक समस्याएं शामिल होती हैं।

सिंक्रोनस सिस्टम में, यह माना जाता है कि सभी संचार राउंड में आगे बढ़ते हैं। एक दौर में, एक प्रक्रिया अन्य प्रक्रियाओं से सभी संदेश प्राप्त करते हुए, आवश्यक सभी संदेश भेज सकती है। इस प्रकार, एक दौर का कोई भी संदेश उसी दौर में भेजे गए किसी भी संदेश को प्रभावित नहीं कर सकता है।

अतुल्यकालिक नियतिवादी सर्वसम्मति के लिए एफएलपी असंभवता परिणाम

पूरी तरह से अतुल्यकालिक संदेश-पासिंग वितरित प्रणाली में, जिसमें कम से कम एक प्रक्रिया में क्रैश विफलता हो सकती है, फिशर, लिंच और पैटर्सन द्वारा प्रसिद्ध 1985 'एफएलपी असंभव परिणाम' में यह साबित हुआ है कि सर्वसम्मति प्राप्त करने के लिए एक नियतात्मक एल्गोरिदम असंभव है .^[5] यह असंभव परिणाम सबसे खराब स्थिति वाले शेड्यूलिंग परिदृश्यों से उत्पन्न होता है, जो नेटवर्क में एक बुद्धिमान सेवा से इनकार करने वाले हमलावर जैसी प्रतिकूल स्थितियों को छोड़कर व्यवहार में होने की संभावना नहीं है। अधिकांश सामान्य स्थितियों में, प्रक्रिया शेड्यूलिंग में प्राकृतिक यादृच्छिकता की एक डिग्री होती है।^[4]

एक अतुल्यकालिक मॉडल में, कुछ प्रकार की विफलताओं को एक तुल्यकालिक सर्वसम्मति प्रोटोकॉल द्वारा नियंत्रित किया जा सकता है। उदाहरण के लिए, संचार लिंक के नुकसान को एक ऐसी प्रक्रिया के रूप में देखा जा सकता है जिसे बीजान्टिन विफलता का सामना करना पड़ा है।

यादृच्छिक एल्गोरिथ्म सर्वसम्मति एल्गोरिदम अत्यधिक संभावना के साथ सुरक्षा और जीवंतता दोनों प्राप्त करके एफएलपी असंभवता परिणाम को दरकिनार कर सकता है, यहां तक कि नेटवर्क में एक बुद्धिमान सेवा से इनकार करने वाले हमलावर जैसे सबसे खराब स्थिति वाले शेड्यूलिंग परिदृश्यों के तहत भी।^[6]

अनुमति बनाम अनुमति रहित सर्वसम्मति

आम सहमति एल्गोरिदम परंपरागत रूप से मानते हैं कि भाग लेने वाले नोड्स का सेट तय हो गया है और शुरुआत में दिया गया है: यानी, कुछ पूर्व (मैन्युअल या स्वचालित) कॉन्फ़िगरेशन प्रक्रिया ने प्रतिभागियों के एक विशेष ज्ञात समूह को अनुमति दी है जो समूह के सदस्यों के रूप में एक दूसरे को प्रमाणित कर सकते हैं। प्रमाणित सदस्यों के साथ इस तरह के एक अच्छी तरह से परिभाषित, बंद समूह की अनुपस्थिति में, एक खुली सर्वसम्मति समूह के खिलाफ एक सिबिल हमला एक बीजान्टिन सर्वसम्मति एल्गोरिथ्म को भी हरा सकता है, बस दोष सहिष्णुता सीमा को खत्म करने के लिए पर्याप्त आभासी प्रतिभागियों का निर्माण करके।

इसके विपरीत, एक अनुमति रहित सर्वसम्मति प्रोटोकॉल, नेटवर्क में किसी को भी गतिशील रूप से शामिल होने और पूर्व अनुमति के बिना भाग लेने की अनुमति देता है, लेकिन इसके बजाय सिबिल हमले के खतरे को कम करने के लिए प्रवेश के लिए कृत्रिम लागत या बाधाओं का एक अलग रूप लगाता है। Bitcoin ने काम के प्रमाण और एक कठिनाई समायोजन फ़ंक्शन का उपयोग करते हुए पहला अनुमति रहित सर्वसम्मति प्रोटोकॉल पेश किया, जिसमें प्रतिभागी क्रिप्टोग्राफ़िक क्रिप्टोग्राफ़िक हैश फ़ंक्शन पहेली को हल करने के लिए प्रतिस्पर्धा करते हैं, और संभावित रूप से अपने निवेशित कम्प्यूटेशनल प्रयास के अनुपात में ब्लॉक करने और संबंधित पुरस्कार अर्जित करने का अधिकार अर्जित करते हैं। आंशिक रूप से इस दृष्टिकोण की उच्च ऊर्जा लागत से प्रेरित होकर, बाद के अनुमति रहित सर्वसम्मति प्रोटोकॉल ने सिबिल हमले से सुरक्षा के लिए अन्य वैकल्पिक भागीदारी नियमों को प्रस्तावित या अपनाया है, जैसे हिस्सेदारी का प्रमाण, स्थान का प्रमाण और अधिकार का प्रमाण।

समझौते की समस्याओं की समतुल्यता

हित की तीन समझौता समस्याएं इस प्रकार हैं।

विश्वसनीय प्रसारण समाप्त करना

का एक संग्रह $n$ प्रक्रियाएं, से क्रमांकित $0$ को $n-1,$ एक दूसरे को संदेश भेजकर संवाद करें। प्रक्रिया $0$ एक मान संचारित करना होगा $v$ ऐसी सभी प्रक्रियाओं के लिए:

यदि प्रक्रिया $0$ सही है, तो हर सही प्रक्रिया प्राप्त होती है $v$
किन्हीं दो सही प्रक्रियाओं के लिए, प्रत्येक प्रक्रिया को समान मान प्राप्त होता है।

इसे जनरल की समस्या के नाम से भी जाना जाता है।

सर्वसम्मति

सर्वसम्मति प्रोटोकॉल के लिए औपचारिक आवश्यकताओं में शामिल हो सकते हैं:

समझौता: सभी सही प्रक्रियाओं को समान मूल्य पर सहमत होना चाहिए।
कमज़ोर वैधता: प्रत्येक सही प्रक्रिया के लिए, उसका आउटपुट किसी सही प्रक्रिया का इनपुट होना चाहिए।
मजबूत वैधता: यदि सभी सही प्रक्रियाओं को समान इनपुट मान प्राप्त होता है, तो उन्हें उस मान को आउटपुट करना होगा।
समाप्ति: सभी प्रक्रियाओं को अंततः आउटपुट मान पर निर्णय लेना होगा

कमजोर इंटरैक्टिव संगति

आंशिक रूप से समकालिक प्रणाली में n प्रक्रियाओं के लिए (सिस्टम समकालिकता की अच्छी और बुरी अवधि के बीच वैकल्पिक होता है), प्रत्येक प्रक्रिया एक निजी मान चुनती है। सार्वजनिक मूल्य निर्धारित करने और उत्पन्न करने के लिए प्रक्रियाएं राउंड द्वारा एक-दूसरे के साथ संवाद करती हैं निम्नलिखित आवश्यकताओं के साथ सर्वसम्मति वेक्टर:^[7]

यदि कोई सही प्रक्रिया भेजता है $v$ , तो सभी सही प्रक्रियाएं या तो प्राप्त होती हैं $v$ या कुछ भी नहीं (अखंडता संपत्ति)
एक सही प्रक्रिया द्वारा एक राउंड में भेजे गए सभी संदेश सभी सही प्रक्रियाओं (संगति संपत्ति) द्वारा एक ही राउंड में प्राप्त होते हैं।

यह दिखाया जा सकता है कि इन समस्याओं की विविधताएँ इस मायने में समतुल्य हैं कि एक प्रकार के मॉडल में किसी समस्या का समाधान दूसरे प्रकार के मॉडल में किसी अन्य समस्या का समाधान हो सकता है। उदाहरण के लिए, सिंक्रोनस प्रमाणित संदेश पासिंग मॉडल में कमजोर बीजान्टिन सामान्य समस्या का समाधान कमजोर इंटरैक्टिव संगति के समाधान की ओर ले जाता है।^[8] एक इंटरएक्टिव कंसिस्टेंसी एल्गोरिदम प्रत्येक प्रक्रिया को उसके सर्वसम्मति वेक्टर में बहुमत मूल्य को उसके सर्वसम्मति मूल्य के रूप में चुनकर सर्वसम्मति की समस्या को हल कर सकता है। रेफरी>Fischer, Michael J. "अविश्वसनीय वितरित प्रणालियों में आम सहमति की समस्या (एक संक्षिप्त सर्वेक्षण)" (PDF). Archived from the original (PDF) on 22 April 2014. Retrieved 21 April 2014.</ref>

कुछ समझौते की समस्याओं के लिए समाधानयोग्यता परिणाम

एक टी-रेज़िलिएंट अनाम सिंक्रोनस प्रोटोकॉल है जो बीजान्टिन जनरल्स समस्या को हल करता है,^[9]^[10] अगर ${\tfrac {t}{n}}<{\tfrac {1}{3}}$ और कमजोर बीजान्टिन जनरलों का मामला^[8]कहाँ $t$ विफलताओं की संख्या है और $n$ प्रक्रियाओं की संख्या है.

के साथ सिस्टम के लिए $n$ प्रोसेसर, जिनमें से $f$ बीजान्टिन हैं, यह दिखाया गया है कि कोई एल्गोरिदम मौजूद नहीं है जो सर्वसम्मति की समस्या को हल करता है $n\leq 3f$ मौखिक-संदेश मॉडल में.^[11] प्रमाण का निर्माण पहले तीन-नोड मामले के लिए असंभवता दिखाकर किया जाता है $n=3$ और प्रोसेसर के विभाजन के बारे में बहस करने के लिए इस परिणाम का उपयोग करें। लिखित-संदेश मॉडल में ऐसे प्रोटोकॉल होते हैं जो सहन कर सकते हैं $n=f+1$ .^[2]

पूरी तरह से अतुल्यकालिक प्रणाली में कोई सर्वसम्मत समाधान नहीं है जो केवल गैर तुच्छता संपत्ति की आवश्यकता होने पर भी एक या अधिक क्रैश विफलताओं को सहन कर सके।^[5]इस परिणाम को कभी-कभी लेखकों माइकल जे. फिशर, नैन्सी लिंच और माइक पैटर्सन के नाम पर एफएलपी असंभव प्रमाण कहा जाता है, जिन्हें इस महत्वपूर्ण कार्य के लिए डिजस्ट्रा पुरस्कार से सम्मानित किया गया था। एफएलपी परिणाम को असीमित गैर-नियतिवाद#निष्पक्षता के तहत भी कायम रखने के लिए यांत्रिक रूप से सत्यापित किया गया है।^[12] हालांकि, एफएलपी यह नहीं बताता है कि आम सहमति कभी नहीं पहुंच सकती: केवल यह कि मॉडल की मान्यताओं के तहत, कोई भी एल्गोरिदम हमेशा निर्धारित समय में आम सहमति तक नहीं पहुंच सकता है। व्यवहार में ऐसा होने की अत्यधिक संभावना नहीं है।

कुछ सर्वसम्मति प्रोटोकॉल

लेस्ली लामपोर्ट द्वारा पैक्सोस (कंप्यूटर विज्ञान) सर्वसम्मति एल्गोरिदम, और इसके वेरिएंट जैसे राफ्ट (एल्गोरिदम), व्यापक रूप से तैनात वितरित कंप्यूटिंग और क्लाउड कंप्यूटिंग सिस्टम में व्यापक रूप से उपयोग किए जाते हैं। ये एल्गोरिदम आम तौर पर समकालिक होते हैं, प्रगति करने के लिए निर्वाचित नेता पर निर्भर होते हैं, और केवल दुर्घटनाओं को सहन करते हैं, बीजान्टिन विफलताओं को नहीं।

बहुपद समय बाइनरी सर्वसम्मति प्रोटोकॉल का एक उदाहरण जो बीजान्टिन विफलताओं को सहन करता है, गारे और बर्मन द्वारा चरण किंग एल्गोरिदम है।^[13] एल्गोरिथ्म n प्रक्रियाओं और f विफलताओं तक एक तुल्यकालिक संदेश पासिंग मॉडल में सर्वसम्मति को हल करता है, बशर्ते n > 4f। फेज़ किंग एल्गोरिथम में, f + 1 चरण होते हैं, प्रति चरण 2 राउंड होते हैं। प्रत्येक प्रक्रिया अपने पसंदीदा आउटपुट का ट्रैक रखती है (प्रारंभ में प्रक्रिया के अपने इनपुट मूल्य के बराबर)। प्रत्येक चरण के पहले दौर में प्रत्येक प्रक्रिया अन्य सभी प्रक्रियाओं के लिए अपना पसंदीदा मूल्य प्रसारित करती है। इसके बाद यह सभी प्रक्रियाओं से मान प्राप्त करता है और यह निर्धारित करता है कि कौन सा मान बहुसंख्यक मान है और उसकी गिनती क्या है। चरण के दूसरे दौर में, जिस प्रक्रिया की आईडी वर्तमान चरण संख्या से मेल खाती है उसे चरण का राजा नामित किया जाता है। राजा पहले दौर में देखे गए बहुमत मूल्य को प्रसारित करता है और टाई ब्रेकर के रूप में कार्य करता है। फिर प्रत्येक प्रक्रिया अपना पसंदीदा मान निम्नानुसार अद्यतन करती है। यदि पहले दौर में देखी गई प्रक्रिया के बहुमत मूल्य की गिनती n/2 + f से अधिक है, तो प्रक्रिया उस बहुमत मूल्य के लिए अपनी प्राथमिकता बदल देती है; अन्यथा यह चरण राजा के मान का उपयोग करता है। एफ + 1 चरणों के अंत में प्रक्रियाएं अपने पसंदीदा मानों को आउटपुट करती हैं।

Google ने एक वितरित ताला प्रबंधक लाइब्रेरी लागू की है जिसे डिस्ट्रीब्यूटेड लॉक मैनेजर#Google की चब्बी लॉक सेवा कहा जाता है।^[14] चब्बी छोटी फ़ाइलों में लॉक जानकारी रखता है जो विफलताओं की स्थिति में उच्च उपलब्धता प्राप्त करने के लिए एक प्रतिकृति डेटाबेस में संग्रहीत होती है। डेटाबेस को दोष-सहिष्णु लॉग परत के शीर्ष पर कार्यान्वित किया जाता है जो पैक्सोस एल्गोरिथ्म पर आधारित है। इस योजना में, चब्बी क्लाइंट प्रतिकृति लॉग तक पहुंचने/अद्यतन करने के लिए पैक्सोस मास्टर के साथ संवाद करते हैं; यानी, फ़ाइलों को पढ़ें/लिखें।^[15] कई पीयर-टू-पीयर ऑनलाइन रीयल-टाइम रणनीति गेम किसी गेम में खिलाड़ियों के बीच गेम की स्थिति को प्रबंधित करने के लिए एक सर्वसम्मति प्रोटोकॉल के रूप में संशोधित लॉकस्टेप प्रोटोकॉल का उपयोग करते हैं। प्रत्येक गेम एक्शन के परिणामस्वरूप गेम में अन्य सभी खिलाड़ियों के लिए गेम स्टेट डेल्टा का प्रसारण होता है, साथ ही कुल गेम स्टेट का हैश भी होता है। प्रत्येक खिलाड़ी अपने खेल राज्य में डेल्टा लागू करके और खेल राज्य हैश की तुलना करके परिवर्तन को मान्य करता है। यदि हैश सहमत नहीं होते हैं तो एक वोट डाला जाता है, और जिन खिलाड़ियों का खेल राज्य अल्पमत में है, उन्हें खेल से अलग कर दिया जाता है और हटा दिया जाता है (जिसे डीसिंक के रूप में जाना जाता है)।

एक अन्य प्रसिद्ध दृष्टिकोण को एमएसआर-प्रकार एल्गोरिदम कहा जाता है जिसका उपयोग कंप्यूटर विज्ञान से लेकर नियंत्रण सिद्धांत तक व्यापक रूप से किया गया है।^[16]^[17]^[18]

Source	Synchrony	Authentication	Threshold	Rounds	Notes
Pease-Shostak-Lamport ^[9]	Synchronous	Oral	$n>3f$	$f+1$	total communication $O(n^{f})$
Pease-Shostak-Lamport ^[9]	Synchronous	Written	$n>f+1$	$f+1$	total communication $O(n^{f})$
Ben-Or ^[19]	Asynchronous	Oral	$n>5f$	$O(2^{n})$ (expected)	expected $O(1)$ rounds when $f<{\sqrt {n}}$
Dolev et al.^[20]	Synchronous	Oral	$n>3f$	$2f+3$	total communication $O(f^{3}\log f)$
Dolev-Strong ^[2]	Synchronous	Written	$n>f+1$	$f+1$	total communication $O(n^{2})$
Dolev-Strong ^[2]	Synchronous	Written	$n>f+1$	$f+2$	total communication $O(nf)$
Feldman-Micali ^[21]	Synchronous	Oral	$n>3f$	$O(1)$ (expected)
Katz-Koo ^[22]	Synchronous	Written	$n>2f$	$O(1)$ (expected)	Requires Public Key Infrastructure (PKI)
PBFT ^[23]	Asynchronous (safety) Synchronous (liveness)	Oral	$n>3f$
HoneyBadger ^[24]	Asynchronous	Oral	$n>3f$	$O(\log n)$ (expected)	per tx communication $O(n)$ - requires public-key encryption
Abraham et al.^[25]	Synchronous	Written	$n>2f$	$8$
Byzantine Agreement Made Trivial ^[26]^[27]	Synchronous	Signatures	$n>3f$	$9$ (expected)	Requires digital signatures

अनुमति रहित सर्वसम्मति प्रोटोकॉल

बिटकॉइन अपने खुले पीयर-टू-पीयर नेटवर्क में अनुमति रहित सर्वसम्मति प्राप्त करने के लिए कार्य के प्रमाण, एक कठिनाई समायोजन फ़ंक्शन और एक पुनर्गठन फ़ंक्शन का उपयोग करता है। बिटकॉइन के ब्लॉकचेन या वितरित बहीखाते का विस्तार करने के लिए, खनिक एक क्रिप्टोग्राफ़िक पहेली को हल करने का प्रयास करते हैं, जहां समाधान खोजने की संभावना प्रति सेकंड हैश में खर्च किए गए कम्प्यूटेशनल प्रयास के समानुपाती होती है। जो नोड सबसे पहले ऐसी पहेली को हल करता है, उसके लेनदेन के अगले ब्लॉक का प्रस्तावित संस्करण बही में जोड़ा जाता है और अंततः अन्य सभी नोड्स द्वारा स्वीकार किया जाता है। चूंकि नेटवर्क में कोई भी नोड प्रूफ-ऑफ-वर्क समस्या को हल करने का प्रयास कर सकता है, सिबिल हमला सैद्धांतिक रूप से तब तक संभव नहीं है जब तक कि हमलावर के पास नेटवर्क के 50% से अधिक कम्प्यूटेशनल संसाधन न हों।

अन्य क्रिप्टोकरेंसी (यानी NEO, STRATIS, ...) हिस्सेदारी के प्रमाण का उपयोग करते हैं, जिसमें नोड्स ब्लॉक को जोड़ने और हिस्सेदारी के अनुपात में संबंधित पुरस्कार अर्जित करने के लिए प्रतिस्पर्धा करते हैं, या मौजूदा क्रिप्टोकरेंसी को कुछ समय अवधि के लिए आवंटित और लॉक या स्टेक किया जाता है। 'कार्य का प्रमाण' प्रणाली की तुलना में 'हिस्सेदारी का प्रमाण' का एक फायदा, बाद वाले द्वारा मांग की जाने वाली उच्च ऊर्जा खपत है। उदाहरण के तौर पर, बिटकॉइन माइनिंग (2018) में गैर-नवीकरणीय ऊर्जा स्रोतों की खपत चेक गणराज्य या जॉर्डन के पूरे देशों के बराबर होने का अनुमान है।^[28] कुछ क्रिप्टोकरेंसी, जैसे कि रिपल, बहीखाता को मान्य करने के लिए नोड्स को मान्य करने की एक प्रणाली का उपयोग करती हैं। रिपल द्वारा उपयोग की जाने वाली यह प्रणाली, जिसे रिपल प्रोटोकॉल कंसेंसस एल्गोरिथम (आरपीसीए) कहा जाता है, राउंड में काम करती है:

चरण 1: प्रत्येक सर्वर वैध उम्मीदवार लेनदेन की एक सूची संकलित करता है;

चरण 2: प्रत्येक सर्वर अपनी विशिष्ट नोड्स सूची (यूएनएल) से आने वाले सभी उम्मीदवारों को एकीकृत करता है और उनकी सत्यता पर वोट करता है;

चरण 3: न्यूनतम सीमा पार करने वाले लेनदेन को अगले दौर में भेज दिया जाता है;

चरण 4: अंतिम दौर में 80% सहमति की आवश्यकता है।^[29]

प्रवेश में बाधाएं लगाने और सिबिल हमलों का विरोध करने के लिए अनुमति रहित सर्वसम्मति प्रोटोकॉल में उपयोग किए जाने वाले अन्य भागीदारी नियमों में अधिकार का प्रमाण, स्थान का प्रमाण, जलने का प्रमाण, या बीते समय का प्रमाण शामिल है।

उपरोक्त अनुमति रहित भागीदारी नियमों के विपरीत, जिनमें से सभी प्रतिभागियों को किसी कार्रवाई या संसाधन में निवेश की मात्रा के अनुपात में पुरस्कृत करते हैं, व्यक्तित्व के प्रमाण प्रोटोकॉल का उद्देश्य प्रत्येक वास्तविक मानव प्रतिभागी को आर्थिक निवेश की परवाह किए बिना अनुमति रहित सर्वसम्मति में मतदान शक्ति की एक इकाई देना है। .^[30]^[31] व्यक्तित्व के प्रमाण के लिए सर्वसम्मति की शक्ति का एक-व्यक्ति वितरण प्राप्त करने के लिए प्रस्तावित दृष्टिकोण में भौतिक छद्म नाम वाली पार्टियाँ शामिल हैं,^[32] सोशल नेटवर्क,^[33] छद्म नाम से सरकार द्वारा जारी पहचान,^[34] और बायोमेट्रिक्स।^[35]

सर्वसम्मति संख्या

साझा-स्मृति प्रणाली में सर्वसम्मति की समस्या को हल करने के लिए, समवर्ती वस्तुओं को पेश किया जाना चाहिए। एक समवर्ती वस्तु, या साझा वस्तु, एक डेटा संरचना है जो समवर्ती प्रक्रियाओं को एक समझौते तक पहुंचने के लिए संचार करने में मदद करती है। यदि कोई प्रक्रिया महत्वपूर्ण अनुभाग के अंदर समाप्त हो जाती है या असहनीय रूप से लंबे समय तक निष्क्रिय रहती है, तो महत्वपूर्ण अनुभागों का उपयोग करने वाले पारंपरिक कार्यान्वयन को क्रैश होने का खतरा होता है। शोधकर्ताओं ने नॉन-ब्लॉकिंग एल्गोरिदम#प्रतीक्षा-स्वतंत्रता|प्रतीक्षा-स्वतंत्रता को इस गारंटी के रूप में परिभाषित किया है कि एल्गोरिदम चरणों की एक सीमित संख्या में पूरा होता है।

किसी समवर्ती वस्तु की सर्वसम्मति संख्या को सिस्टम में प्रक्रियाओं की अधिकतम संख्या के रूप में परिभाषित किया जाता है जो प्रतीक्षा-मुक्त कार्यान्वयन में दिए गए ऑब्जेक्ट द्वारा सर्वसम्मति तक पहुंच सकती है।^[36] सर्वसम्मति संख्या वाली वस्तुएँ $n$ की सर्वसम्मति संख्या के साथ किसी भी वस्तु को कार्यान्वित कर सकता है $n$ या उससे कम, लेकिन अधिक सर्वसम्मति संख्या वाली किसी भी वस्तु को लागू नहीं कर सकता। सर्वसम्मत संख्याएँ मौरिस हेर्लिही की सिंक्रनाइज़ेशन वस्तुओं के पदानुक्रम को बनाती हैं।^[37]

Consensus number	Objects
$1$	atomic read/write registers, mutex
$2$	test-and-set, swap, fetch-and-add, wait-free queue or stack
...	...
$2n-2$	n-register assignment
...	...
$\infty$	compare-and-swap, load-link/store-conditional,^[38] memory-to-memory move and swap, queue with peek operation, fetch&cons, sticky byte

पदानुक्रम के अनुसार, पढ़ने/लिखने वाले रजिस्टर 2-प्रक्रिया प्रणाली में भी सर्वसम्मति का समाधान नहीं कर सकते हैं। स्टैक और कतार जैसी डेटा संरचनाएं केवल दो प्रक्रियाओं के बीच आम सहमति का समाधान कर सकती हैं। हालाँकि, कुछ समवर्ती वस्तुएँ सार्वभौमिक हैं (तालिका में अंकित हैं)। $\infty$ ), जिसका अर्थ है कि वे किसी भी संख्या में प्रक्रियाओं के बीच सर्वसम्मति को हल कर सकते हैं और वे एक ऑपरेशन अनुक्रम के माध्यम से किसी भी अन्य ऑब्जेक्ट का अनुकरण कर सकते हैं।^[36]

यह भी देखें

संदर्भ

↑ ^1.0 ^1.1 ^1.2 George Coulouris; Jean Dollimore; Tim Kindberg (2001), Distributed Systems: Concepts and Design (3rd ed.), Addison-Wesley, p. 452, ISBN 978-0201-61918-8
↑ ^2.0 ^2.1 ^2.2 ^2.3 Dolev, D.; Strong, H.R. (1983). "बीजान्टिन समझौते के लिए प्रमाणित एल्गोरिदम". SIAM Journal on Computing. 12 (4): 656–666. doi:10.1137/0212045.
↑ Gong, Li; Lincoln, Patrick; Rushby, John (1995). "Byzantine Agreement with authentication". Dependable Computing for Critical Applications. 10.
↑ ^4.0 ^4.1 Aguilera, M. K. (2010). "Stumbling over Consensus Research: Misunderstandings and Issues". प्रतिकृति. Lecture Notes in Computer Science. Vol. 5959. pp. 59–72. doi:10.1007/978-3-642-11294-2_4. ISBN 978-3-642-11293-5.
↑ ^5.0 ^5.1 Fischer, M. J.; Lynch, N. A.; Paterson, M. S. (1985). "एक दोषपूर्ण प्रक्रिया के साथ वितरित सर्वसम्मति की असंभवता" (PDF). Journal of the ACM. 32 (2): 374–382. doi:10.1145/3149.214121. S2CID 207660233.
↑ Aspnes, James (May 1993). "समय- और स्थान-कुशल यादृच्छिक सहमति". Journal of Algorithms. 14 (3): 414–431. doi:10.1006/jagm.1993.1022.
↑ Milosevic, Zarko; Martin Hutle; Andre Schiper (2009). कमजोर इंटरैक्टिव संगति के साथ बीजान्टिन सर्वसम्मति एल्गोरिदम को एकीकृत करना. pp. 300–314. CiteSeerX 10.1.1.180.4229. doi:10.1007/978-3-642-10877-8_24. ISBN 978-3-642-10876-1. {{cite book}}: |journal= ignored (help)
↑ ^8.0 ^8.1 Lamport, L. (1983). "कमजोर बीजान्टिन जनरलों की समस्या". Journal of the ACM. 30 (3): 668. doi:10.1145/2402.322398. S2CID 1574706.
↑ ^9.0 ^9.1 ^9.2 Lamport, L.; Shostak, R.; Pease, M. (1982). "बीजान्टिन जनरलों की समस्या" (PDF). ACM Transactions on Programming Languages and Systems. 4 (3): 382–401. CiteSeerX 10.1.1.64.2312. doi:10.1145/357172.357176. S2CID 55899582.
↑ Lamport, Leslie; Marshall Pease; Robert Shostak (April 1980). "दोषों की उपस्थिति में समझौते पर पहुंचना" (PDF). Journal of the ACM. 27 (2): 228–234. CiteSeerX 10.1.1.68.4044. doi:10.1145/322186.322188. S2CID 6429068. Retrieved 2007-07-25.
↑ Attiya, Hagit (2004). वितरित अभिकलन (2nd ed.). Wiley. pp. 101–103. ISBN 978-0-471-45324-6.
↑ Bisping, Benjamin; et al. (2016), Blanchette, Jasmin Christian; Merz, Stephan (eds.), Mechanical Verification of a Constructive Proof for FLP, Lecture Notes in Computer Science, vol. 9807, Springer International Publishing, doi:10.1007/978-3-319-43144-4_7, ISBN 978-3-319-43144-4
↑ Berman, Piotr; Garay, Juan A. (1993). "Cloture Votes: n/4-resilient Distributed Consensus in t + 1 rounds". Theory of Computing Systems. 2. 26: 3–19. doi:10.1007/BF01187072. S2CID 6102847.
↑ Burrows, M. (2006). The Chubby lock service for loosely-coupled distributed systems (PDF). Proceedings of the 7th Symposium on Operating Systems Design and Implementation. USENIX Association Berkeley, CA, USA. pp. 335–350.
↑ Tushar, C.; Griesemer, R.; Redstone, J. (2007). Paxos Made Live – An Engineering Perspective (PDF). Proceedings of the Twenty-Sixth Annual ACM Symposium on Principles of Distributed Computing. Portland, Oregon, USA: ACM Press New York, NY, USA. pp. 398–407. doi:10.1145/1281100.1281103. Archived from the original (PDF) on 2014-12-12. Retrieved 2008-02-06.
↑ LeBlanc, Heath J. (April 2013). "मजबूत नेटवर्क में लचीली स्पर्शोन्मुख सहमति". IEEE Journal on Selected Areas in Communications. 31 (4): 766–781. CiteSeerX 10.1.1.310.5354. doi:10.1109/JSAC.2013.130413. S2CID 11287513.
↑ Dibaji, S. M. (May 2015). "स्थानीय रूप से बंधे दोषों की उपस्थिति में दूसरे क्रम के मल्टी-एजेंट सिस्टम की सहमति". Systems & Control Letters. 79: 23–29. doi:10.1016/j.sysconle.2015.02.005.
↑ Dibaji, S. M. (July 2017). "Resilient consensus of second-order agent networks: Asynchronous update rules with delays". Automatica. 81: 123–132. arXiv:1701.03430. Bibcode:2017arXiv170103430M. doi:10.1016/j.automatica.2017.03.008. S2CID 7467466.
↑ Ben-Or, Michael (1983). "Another advantage of free choice (extended abstract): Completely asynchronous agreement protocols". Proceedings of the second annual ACM symposium on Principles of distributed computing. pp. 27–30. doi:10.1145/800221.806707. S2CID 38215511.
↑ Dolev, Danny; Fisher, Michael J.; Fowler, Rob; Lynch, Nancy; Strong, H. Raymond (1982). "An Efficient Algorithm for Byzantine Agreement without Authentication". Information and Control. 52 (3): 257–274. doi:10.1016/S0019-9958(82)90776-8.
↑ Feldman, Pesech; Micali, Sylvio (1997). "An optimal probabilistic protocol for synchronous Byzantine agreement". SIAM Journal on Computing. 26 (4). doi:10.1137/S0097539790187084.
↑ Katz, Jonathan; Koo, Chiu-Yuen (2006). On Expected Constant-Round Protocols for Byzantine Agreement. CRYPTO 2006. doi:10.1007/11818175_27.
↑ Castro, Miguel; Liskov, Barbara (1999). "Practical Byzantine Fault Tolerance" (PDF). Proceedings of the Third Symposium on Operating Systems Design and Implementation, New Orleans, USA, February 1999.
↑ Miller, Andrew; Xia, Yu; Croman, Kyle; Shi, Elaine; Song, Dawn (October 2016). "The honey badger of BFT protocols" (PDF). CCS '16: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. pp. 31–42. doi:10.1145/2976749.2978399.
↑ Abraham, Ittai; Devadas, Srinivas; Dolev, Danny; Nayak, Kartik; Ren, Ling (September 11, 2017). "Efficient Synchronous Byzantine Consensus" (PDF). Cryptology ePrint Archive. Paper 2017/307.
↑ Micali, Sylvio (March 19, 2018). "Byzantine agreement made trivial" (PDF). Cambridge, MA: CSAIL, MIT.
↑ Chen, Jing; Micali, Silvio (2016). "ALGORAND". arXiv:1607.01341v9 [cs.CR].
↑ Irfan, Umair (June 18, 2019). "Bitcoin is an energy hog. Where is all that electricity coming from?". Vox.
↑ Schwartz, David; Youngs, Noah; Britto, Arthur (2014). "रिपल प्रोटोकॉल सर्वसम्मति एल्गोरिदम" (PDF). Ripple Labs (Draft).
↑ Maria Borge; Eleftherios Kokoris-Kogias; Philipp Jovanovic; Linus Gasser; Nicolas Gailly; Bryan Ford (29 April 2017). Proof-of-Personhood: Redemocratizing Permissionless Cryptocurrencies. IEEE Security & Privacy on the Blockchain (IEEE S&B). doi:10.1109/EuroSPW.2017.46.
↑ Divya Siddarth; Sergey Ivliev; Santiago Siri; Paula Berman (13 Oct 2020). "Who Watches the Watchmen? A Review of Subjective Approaches for Sybil-resistance in Proof of Personhood Protocols". arXiv:2008.05300 [cs.CR].
↑ Ford, Bryan; Strauss, Jacob (April 2008). ऑनलाइन जवाबदेह छद्मनामों के लिए एक ऑफ़लाइन फाउंडेशन. 1st Workshop on Social Network Systems - SocialNets '08. pp. 31–36. doi:10.1145/1435497.1435503. ISBN 978-1-60558-124-8.
↑ Gal Shahaf; Ehud Shapiro; Nimrod Talmon (October 2020). सिबिल-रेज़िलिएंट सामुदायिक विकास के लिए वास्तविक व्यक्तिगत पहचानकर्ता और पारस्परिक ज़मानत. International Conference on Social Informatics. doi:10.1007/978-3-030-60975-7_24.
↑ Deepak Maram; Harjasleen Malvai; Fan Zhang; Nerla Jean-Louis; Alexander Frolov; Tyler Kell; Tyrone Lobban; Christine Moy; Ari Juels; Andrew Miller (28 Sep 2020). "CanDID: Can-Do Decentralized Identity with Legacy Compatibility, Sybil-Resistance, and Accountability" (PDF).
↑ Mohammad-Javad Hajialikhani; Mohammad-Mahdi Jahanara (20 June 2018). "UniqueID: Decentralized Proof-of-Unique-Human". arXiv:1806.07583 [cs.CR].
↑ ^36.0 ^36.1 Herlihy, Maurice (January 1991). "प्रतीक्षा-मुक्त तुल्यकालन" (PDF). ACM TransactIons on Programming Languages and Systems. 11 (1): 124–149. Retrieved 19 December 2011.
↑ Imbs, Damien; Raynal, Michel (25 July 2010). "सर्वसम्मत संख्याओं की गुणात्मक शक्ति" (PDF). Proceedings of the 29th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing. Association for Computing Machinery: 26–35. doi:10.1145/1835698.1835705. ISBN 978-1-60558-888-9. S2CID 3179361. Retrieved 22 April 2021.
↑ Fich, Faith; Hendler, Danny; Shavit, Nir (25 July 2004). "On the inherent weakness of conditional synchronization primitives". Proceedings of the Twenty-Third Annual ACM Symposium on Principles of Distributed Computing. Association for Computing Machinery: 80–87. CiteSeerX 10.1.1.96.9340. doi:10.1145/1011767.1011780. ISBN 1-58113-802-4. S2CID 9313205.

अग्रिम पठन

Herlihy, M.; Shavit, N. (1999). "The topological structure of asynchronous computability". Journal of the ACM. 46 (6): 858. CiteSeerX 10.1.1.78.1455. doi:10.1145/331524.331529. S2CID 5797174.
Saks, M.; Zaharoglou, F. (2000). "Wait-Free k-Set Agreement is Impossible: The Topology of Public Knowledge". SIAM Journal on Computing. 29 (5): 1449–1483. doi:10.1137/S0097539796307698.
Bashir, Imran. "Blockchain Consensus." Blockchain Consensus - An Introduction to Classical, Blockchain, and Quantum Consensus Protocols. ISBN 978-1-4842-8178-9 Apress, Berkeley, CA, 2022. doi:10.1007/978-1-4842-8179-6

[coulouris-1] 1.0 ^1.1 ^1.2 George Coulouris; Jean Dollimore; Tim Kindberg (2001), Distributed Systems: Concepts and Design (3rd ed.), Addison-Wesley, p. 452, ISBN 978-0201-61918-8

[dolev_strong-2] 2.0 ^2.1 ^2.2 ^2.3 Dolev, D.; Strong, H.R. (1983). "बीजान्टिन समझौते के लिए प्रमाणित एल्गोरिदम". SIAM Journal on Computing. 12 (4): 656–666. doi:10.1137/0212045.

[GLR95-3] Gong, Li; Lincoln, Patrick; Rushby, John (1995). "Byzantine Agreement with authentication". Dependable Computing for Critical Applications. 10.

[aguilera_stumbling-4] 4.0 ^4.1 Aguilera, M. K. (2010). "Stumbling over Consensus Research: Misunderstandings and Issues". प्रतिकृति. Lecture Notes in Computer Science. Vol. 5959. pp. 59–72. doi:10.1007/978-3-642-11294-2_4. ISBN 978-3-642-11293-5.

[fischer_impossibility-5] 5.0 ^5.1 Fischer, M. J.; Lynch, N. A.; Paterson, M. S. (1985). "एक दोषपूर्ण प्रक्रिया के साथ वितरित सर्वसम्मति की असंभवता" (PDF). Journal of the ACM. 32 (2): 374–382. doi:10.1145/3149.214121. S2CID 207660233.

[6] Aspnes, James (May 1993). "समय- और स्थान-कुशल यादृच्छिक सहमति". Journal of Algorithms. 14 (3): 414–431. doi:10.1006/jagm.1993.1022.

[7] Milosevic, Zarko; Martin Hutle; Andre Schiper (2009). कमजोर इंटरैक्टिव संगति के साथ बीजान्टिन सर्वसम्मति एल्गोरिदम को एकीकृत करना. pp. 300–314. CiteSeerX 10.1.1.180.4229. doi:10.1007/978-3-642-10877-8_24. ISBN 978-3-642-10876-1. {{cite book}}: |journal= ignored (help)

[lamport_WBGP-8] 8.0 ^8.1 Lamport, L. (1983). "कमजोर बीजान्टिन जनरलों की समस्या". Journal of the ACM. 30 (3): 668. doi:10.1145/2402.322398. S2CID 1574706.

[PSL82-9] 9.0 ^9.1 ^9.2 Lamport, L.; Shostak, R.; Pease, M. (1982). "बीजान्टिन जनरलों की समस्या" (PDF). ACM Transactions on Programming Languages and Systems. 4 (3): 382–401. CiteSeerX 10.1.1.64.2312. doi:10.1145/357172.357176. S2CID 55899582.

[10] Lamport, Leslie; Marshall Pease; Robert Shostak (April 1980). "दोषों की उपस्थिति में समझौते पर पहुंचना" (PDF). Journal of the ACM. 27 (2): 228–234. CiteSeerX 10.1.1.68.4044. doi:10.1145/322186.322188. S2CID 6429068. Retrieved 2007-07-25.

[11] Attiya, Hagit (2004). वितरित अभिकलन (2nd ed.). Wiley. pp. 101–103. ISBN 978-0-471-45324-6.

[flp_verification-12] Bisping, Benjamin; et al. (2016), Blanchette, Jasmin Christian; Merz, Stephan (eds.), Mechanical Verification of a Constructive Proof for FLP, Lecture Notes in Computer Science, vol. 9807, Springer International Publishing, doi:10.1007/978-3-319-43144-4_7, ISBN 978-3-319-43144-4

[13] Berman, Piotr; Garay, Juan A. (1993). "Cloture Votes: n/4-resilient Distributed Consensus in t + 1 rounds". Theory of Computing Systems. 2. 26: 3–19. doi:10.1007/BF01187072. S2CID 6102847.

[14] Burrows, M. (2006). The Chubby lock service for loosely-coupled distributed systems (PDF). Proceedings of the 7th Symposium on Operating Systems Design and Implementation. USENIX Association Berkeley, CA, USA. pp. 335–350.

[15] Tushar, C.; Griesemer, R.; Redstone, J. (2007). Paxos Made Live – An Engineering Perspective (PDF). Proceedings of the Twenty-Sixth Annual ACM Symposium on Principles of Distributed Computing. Portland, Oregon, USA: ACM Press New York, NY, USA. pp. 398–407. doi:10.1145/1281100.1281103. Archived from the original (PDF) on 2014-12-12. Retrieved 2008-02-06.

[16] LeBlanc, Heath J. (April 2013). "मजबूत नेटवर्क में लचीली स्पर्शोन्मुख सहमति". IEEE Journal on Selected Areas in Communications. 31 (4): 766–781. CiteSeerX 10.1.1.310.5354. doi:10.1109/JSAC.2013.130413. S2CID 11287513.

[17] Dibaji, S. M. (May 2015). "स्थानीय रूप से बंधे दोषों की उपस्थिति में दूसरे क्रम के मल्टी-एजेंट सिस्टम की सहमति". Systems & Control Letters. 79: 23–29. doi:10.1016/j.sysconle.2015.02.005.

[18] Dibaji, S. M. (July 2017). "Resilient consensus of second-order agent networks: Asynchronous update rules with delays". Automatica. 81: 123–132. arXiv:1701.03430. Bibcode:2017arXiv170103430M. doi:10.1016/j.automatica.2017.03.008. S2CID 7467466.

[B83-19] Ben-Or, Michael (1983). "Another advantage of free choice (extended abstract): Completely asynchronous agreement protocols". Proceedings of the second annual ACM symposium on Principles of distributed computing. pp. 27–30. doi:10.1145/800221.806707. S2CID 38215511.

[DFFLS82-20] Dolev, Danny; Fisher, Michael J.; Fowler, Rob; Lynch, Nancy; Strong, H. Raymond (1982). "An Efficient Algorithm for Byzantine Agreement without Authentication". Information and Control. 52 (3): 257–274. doi:10.1016/S0019-9958(82)90776-8.

[FM97-21] Feldman, Pesech; Micali, Sylvio (1997). "An optimal probabilistic protocol for synchronous Byzantine agreement". SIAM Journal on Computing. 26 (4). doi:10.1137/S0097539790187084.

[KK06-22] Katz, Jonathan; Koo, Chiu-Yuen (2006). On Expected Constant-Round Protocols for Byzantine Agreement. CRYPTO 2006. doi:10.1007/11818175_27.

[PBFT-23] Castro, Miguel; Liskov, Barbara (1999). "Practical Byzantine Fault Tolerance" (PDF). Proceedings of the Third Symposium on Operating Systems Design and Implementation, New Orleans, USA, February 1999.

[HoneyBadger-24] Miller, Andrew; Xia, Yu; Croman, Kyle; Shi, Elaine; Song, Dawn (October 2016). "The honey badger of BFT protocols" (PDF). CCS '16: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. pp. 31–42. doi:10.1145/2976749.2978399.

[ADDNR17-25] Abraham, Ittai; Devadas, Srinivas; Dolev, Danny; Nayak, Kartik; Ren, Ling (September 11, 2017). "Efficient Synchronous Byzantine Consensus" (PDF). Cryptology ePrint Archive. Paper 2017/307.

[M18-26] Micali, Sylvio (March 19, 2018). "Byzantine agreement made trivial" (PDF). Cambridge, MA: CSAIL, MIT.

[27] Chen, Jing; Micali, Silvio (2016). "ALGORAND". arXiv:1607.01341v9 [cs.CR].

[28] Irfan, Umair (June 18, 2019). "Bitcoin is an energy hog. Where is all that electricity coming from?". Vox.

[29] Schwartz, David; Youngs, Noah; Britto, Arthur (2014). "रिपल प्रोटोकॉल सर्वसम्मति एल्गोरिदम" (PDF). Ripple Labs (Draft).

[30] Maria Borge; Eleftherios Kokoris-Kogias; Philipp Jovanovic; Linus Gasser; Nicolas Gailly; Bryan Ford (29 April 2017). Proof-of-Personhood: Redemocratizing Permissionless Cryptocurrencies. IEEE Security & Privacy on the Blockchain (IEEE S&B). doi:10.1109/EuroSPW.2017.46.

[31] Divya Siddarth; Sergey Ivliev; Santiago Siri; Paula Berman (13 Oct 2020). "Who Watches the Watchmen? A Review of Subjective Approaches for Sybil-resistance in Proof of Personhood Protocols". arXiv:2008.05300 [cs.CR].

[32] Ford, Bryan; Strauss, Jacob (April 2008). ऑनलाइन जवाबदेह छद्मनामों के लिए एक ऑफ़लाइन फाउंडेशन. 1st Workshop on Social Network Systems - SocialNets '08. pp. 31–36. doi:10.1145/1435497.1435503. ISBN 978-1-60558-124-8.

[33] Gal Shahaf; Ehud Shapiro; Nimrod Talmon (October 2020). सिबिल-रेज़िलिएंट सामुदायिक विकास के लिए वास्तविक व्यक्तिगत पहचानकर्ता और पारस्परिक ज़मानत. International Conference on Social Informatics. doi:10.1007/978-3-030-60975-7_24.

[34] Deepak Maram; Harjasleen Malvai; Fan Zhang; Nerla Jean-Louis; Alexander Frolov; Tyler Kell; Tyrone Lobban; Christine Moy; Ari Juels; Andrew Miller (28 Sep 2020). "CanDID: Can-Do Decentralized Identity with Legacy Compatibility, Sybil-Resistance, and Accountability" (PDF).

[35] Mohammad-Javad Hajialikhani; Mohammad-Mahdi Jahanara (20 June 2018). "UniqueID: Decentralized Proof-of-Unique-Human". arXiv:1806.07583 [cs.CR].

[hierarchy-36] 36.0 ^36.1 Herlihy, Maurice (January 1991). "प्रतीक्षा-मुक्त तुल्यकालन" (PDF). ACM TransactIons on Programming Languages and Systems. 11 (1): 124–149. Retrieved 19 December 2011.

[37] Imbs, Damien; Raynal, Michel (25 July 2010). "सर्वसम्मत संख्याओं की गुणात्मक शक्ति" (PDF). Proceedings of the 29th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing. Association for Computing Machinery: 26–35. doi:10.1145/1835698.1835705. ISBN 978-1-60558-888-9. S2CID 3179361. Retrieved 22 April 2021.

[38] Fich, Faith; Hendler, Danny; Shavit, Nir (25 July 2004). "On the inherent weakness of conditional synchronization primitives". Proceedings of the Twenty-Third Annual ACM Symposium on Principles of Distributed Computing. Association for Computing Machinery: 80–87. CiteSeerX 10.1.1.96.9340. doi:10.1145/1011767.1011780. ISBN 1-58113-802-4. S2CID 9313205.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]

[34]

[35]

[36]

[37]

[38]

Anonymous

Search

कॉन्सेंसस (कंप्यूटर विज्ञान)

Namespaces

More

Page actions

Contents

समस्या विवरण

गणना के मॉडल