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

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

समस्या विवरण

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

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

टर्मिनेशन: अंततः प्रत्येक सही प्रक्रिया कुछ मान तय करती है।
इंटीग्रिटी (अखंडता): यदि सभी सही प्रक्रियाओं ने समान मान $v$ प्रस्तावित किया है तो किसी भी सही प्रक्रिया को $v$ का निर्णय करना होता है।
औपचारिक स्वीकृति: प्रत्येक सही प्रक्रिया को समान मान पर सहमत होना आवश्यक है।

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

एक प्रोटोकॉल जो $n$ प्रक्रियाओं के बीच कॉन्सेंसस के लिए उत्तरदाई हो सकता है जिनमें से अधिकांश $T$ रेसिलिएंट हो जाती है, उसे $T$ रेसिलिएंट कहा जाता है।

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

गणना के मॉडल

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

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

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

दो अलग-अलग प्रमाणीकरण मॉडल को प्रायः मौखिक संचार और लिखित संचार मॉडल कहा जाता है। मौखिक संचार मॉडल में, सूचना का तत्काल स्रोत ज्ञात होता है, जबकि मजबूत, लिखित संचार मॉडल में, रिसीवर के हर कदम पर न केवल संदेश का तत्काल स्रोत पता चलता है, बल्कि संदेश का संचार इतिहास भी पता चलता है।^[3]

कॉन्सेंसस के इनपुट और आउटपुट

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

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

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

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

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

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

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

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

असिंक्रोनाइज़ और सिंक्रोनाइज़ सिस्टम

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

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

असिंक्रोनाइज़ नियतिवादी कॉन्सेंसस के लिए एफएलपी असंभवता परिणाम

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

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

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

स्वीकृति बनाम स्वीकृति रहित कॉन्सेंसस

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

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

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

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

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

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

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

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

कॉन्सेंसस

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

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

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

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

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

यह दिखाया जा सकता है कि इन समस्याओं की विविधताएँ इस मायने में समतुल्य हैं कि एक प्रकार के मॉडल में किसी समस्या का समाधान दूसरे प्रकार के मॉडल में किसी अन्य समस्या का समाधान हो सकता है। उदाहरण के लिए, सिंक्रोनाइज़ प्रमाणित संदेश पासिंग मॉडल में कमजोर बीजान्टिन सामान्य समस्या का समाधान कमजोर इंटरैक्टिव संगति के समाधान की ओर ले जाता है।^[8] एक इंटरएक्टिव कंसिस्टेंसी एल्गोरिदम प्रत्येक प्रक्रिया को उसके कॉन्सेंसस वेक्टर में बहुमत मान को उसके कॉन्सेंसस मान के रूप में चुनकर कॉन्सेंसस की समस्या को हल कर सकता है।

यह दिखाया जा सकता है कि इन समस्याओं की विविधताएँ इस मायने में समतुल्य हैं कि एक प्रकार के मॉडल में किसी समस्या का समाधान दूसरे प्रकार के मॉडल में किसी अन्य समस्या का समाधान हो सकता है। उदाहरण के लिए, सिंक्रोनाइज़ प्रमाणित संदेश पासिंग मॉडल में कमजोर बीजान्टिन सामान्य समस्या का समाधान कमजोर इंटरैक्टिव संगति के समाधान की ओर ले जाता है।^[8] एक इंटरएक्टिव कंसिस्टेंसी एल्गोरिदम प्रत्येक प्रक्रिया को उसके कॉन्सेंसस वेक्टर में बहुमत मान को उसके कॉन्सेंसस मान के रूप में चुनकर कॉन्सेंसस की समस्या को हल कर सकता है।^[9]</nowiki></ref>

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

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

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

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

कुछ कॉन्सेंसस प्रोटोकॉल

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

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

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

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

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

स्रोत	सिंक्रोनाइज़ेशन	प्रमाणीकरण	थ्रेसहोल्ड	स्थिति	टिप्पणियाँ
पीज़-शोस्ताक-लामपोर्ट ^[10]	सिंक्रोनाइज़	मौखिक	$n>3f$	$f+1$	कुल संचार $O(n^{f})$
पीज़-शोस्ताक-लामपोर्ट ^[10]	सिंक्रोनाइज़	लिखित	$n>f+1$	$f+1$	कुल संचार $O(n^{f})$
Ben-Or ^[19]	असिंक्रोनाइज़	मौखिक	$n>5f$	$O(2^{n})$ (एक्सपेक्ट)	एक्सपेक्ट $O(1)$ rounds when $f<{\sqrt {n}}$
डोलेव.^[20]	सिंक्रोनाइज़	मौखिक	$n>3f$	$2f+3$	कुल संचार $O(f^{3}\log f)$
डोलेव-स्ट्रोंग ^[2]	सिंक्रोनाइज़	लिखित	$n>f+1$	$f+1$	कुल संचार $O(n^{2})$
डोलेव-स्ट्रोंग ^[2]	सिंक्रोनाइज़	लिखित	$n>f+1$	$f+2$	कुल संचार $O(nf)$
फेल्डमैन-मिकाली ^[21]	सिंक्रोनाइज़	मौखिक	$n>3f$	$O(1)$ (एक्सपेक्ट)
काट्ज़-कू ^[22]	सिंक्रोनाइज़	लिखित	$n>2f$	$O(1)$ (एक्सपेक्ट)	पीकेआई की आवश्यकता है।
पीबीएफटी ^[23]	असिंक्रोनाइज़ (safety) सिंक्रोनाइज़ (liveness)	मौखिक	$n>3f$
हनीबजर ^[24]	असिंक्रोनाइज़	मौखिक	$n>3f$	$O(\log n)$ (एक्सपेक्ट)	per tx communication $O(n)$ - requires public-key encryption
अब्राहम^[25]	सिंक्रोनाइज़	लिखित	$n>2f$	$8$
बीजान्टिन एग्रीमेन्ट ट्रिवियल ^[26]^[27]	सिंक्रोनाइज़	हस्ताक्षर	$n>3f$	$9$ (एक्सपेक्ट)	डिजिटल हस्ताक्षर की आवश्यकता है।

स्वीकृति रहित कॉन्सेंसस प्रोटोकॉल

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

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

कुछ क्रिप्टोकरेंसी, जैसे कि रिपल, बहीखाता को मान्य करने के लिए नोड्स को मान्य करने की एक प्रणाली का उपयोग करती हैं। रिपल द्वारा उपयोग की जाने वाली यह प्रणाली, जिसे रिपल प्रोटोकॉल कंसेंसस एल्गोरिथम (आरपीसीए) कहा जाता है, राउंड में काम करती है:

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

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

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

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

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

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

कॉन्सेंसस संख्या

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

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

कॉन्सेंसस संख्या	ऑब्जेक्ट
$1$	एटॉमिक रीड/राइट पंजीकरण, म्युटेक्स
$2$	test-and-set, स्वैप, फ़ेच और एडीडी , wait-free केयूए या स्टैक
...	...
$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 ^8.2 Lamport, L. (1983). "कमजोर बीजान्टिन जनरलों की समस्या". Journal of the ACM. 30 (3): 668. doi:10.1145/2402.322398. S2CID 1574706.
↑ <ref>Fischer, Michael J. "अविश्वसनीय वितरित प्रणालियों में आम सहमति की समस्या (एक संक्षिप्त सर्वेक्षण)" (PDF). Archived from the original (PDF) on 22 April 2014. Retrieved 21 April 2014.<nowiki>
↑ ^10.0 ^10.1 ^10.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
↑ 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 कॉन्सेंसस." Blockchain कॉन्सेंसस - An Introduction to Classical, Blockchain, and Quantum कॉन्सेंसस 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 ^8.2 Lamport, L. (1983). "कमजोर बीजान्टिन जनरलों की समस्या". Journal of the ACM. 30 (3): 668. doi:10.1145/2402.322398. S2CID 1574706.

[9] <ref>Fischer, Michael J. "अविश्वसनीय वितरित प्रणालियों में आम सहमति की समस्या (एक संक्षिप्त सर्वेक्षण)" (PDF). Archived from the original (PDF) on 22 April 2014. Retrieved 21 April 2014.<nowiki>

[PSL82-10] 10.0 ^10.1 ^10.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.

[11] 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.

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

[flp_verification-13] 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

[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

समस्या विवरण

गणना के मॉडल