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

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

समस्या विवरण

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

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

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

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

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

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

कम्प्यूटेशन के मॉडल

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

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

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

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

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

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

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

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

क्रैश और बीजान्टिन विफलताएँ

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

अखंडता: यदि कोई सही प्रक्रिया $v$ का निर्णय करती है, तो $v$ को किसी सही प्रक्रिया द्वारा प्रस्तावित किया जा सकता है।

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

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

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

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

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

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

परमिशन और परमिशनलेस कॉन्सेंसस

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

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

औपचारिक समस्याओं की समतुल्यता

समतुल्यता की तीन औपचारिक समस्याएं इस प्रकार हैं।

टर्मिनेशन रेलिएबल ब्रॉडकास्ट

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

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

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

कॉन्सेंसस

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

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

वीक इंटरैक्टिव कंसिस्टेंसी

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

यदि एक सही प्रक्रिया $v$ भेजती है, तो सभी सही प्रक्रियाओं को $v$ का कोई भी मान नहीं प्राप्त होता है।
एक सही प्रक्रिया द्वारा एक बार में भेजे गए सभी संदेश सभी सही प्रक्रियाओं द्वारा एक ही बार में प्राप्त होते हैं।

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

कुछ औपचारिक समस्याओं के लिए समाधान योग्य परिणाम

एक टी-रेज़िलिएंट अनाम सिंक्रोनाइज़ प्रोटोकॉल है जो बीजान्टिन जनरल समस्या को हल करता है,^[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$	परीक्षण और समूह, स्वैप, फ़ेच और एडीडी, केयूए या स्टैक
...	...
$2n-2$	n-पंजीकरण असाइनमेंट
...	...
$\infty$	कॉम्पेयर और स्वैप, लोड-लिंक/स्टोर,^[38] मेमोरी से मेमोरी स्वैप, पीक ऑपरेशन के साथ केयूए, फ़ेच & कॉन, स्ट्रिक बाइट

सिंक्रनाइज़ेशन ऑब्जेक्ट के अनुसार रीड/राइट वाले पंजीकरण प्रक्रिया सिस्टम में भी कॉन्सेंसस का समाधान नहीं कर सकते हैं। स्टैक और केयूए जैसी डेटा संरचनाएं केवल दो प्रक्रियाओं के बीच कॉन्सेंसस का समाधान कर सकती हैं। हालाँकि, कुछ समवर्ती ऑब्जेक्ट सार्वभौमिक हैं जो तालिका में $\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.
↑ <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 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

समस्या विवरण

कम्प्यूटेशन के मॉडल