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

From Vigyanwiki
No edit summary
No edit summary
Line 14: Line 14:
एक प्रोटोकॉल जो <math>n</math> प्रक्रियाओं के बीच कॉन्सेंसस के लिए उत्तरदाई हो सकता है जिनमें से अधिकांश <math>T</math> रेसिलिएंट हो जाती है, उसे <math>T</math> रेसिलिएंट कहा जाता है।
एक प्रोटोकॉल जो <math>n</math> प्रक्रियाओं के बीच कॉन्सेंसस के लिए उत्तरदाई हो सकता है जिनमें से अधिकांश <math>T</math> रेसिलिएंट हो जाती है, उसे <math>T</math> रेसिलिएंट कहा जाता है।


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


==गणना के मॉडल==
==कम्प्यूटेशन के मॉडल==


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


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


संचार प्रोटोकॉल के अधिकांश मॉडलों में प्रतिभागी प्रमाणित चैनलों के माध्यम से संवाद करते हैं। इसका मतलब यह है कि संदेश गुमनाम नहीं होते हैं, और प्राप्तकर्ता उन्हें प्राप्त होने वाले प्रत्येक संदेश का स्रोत जानते हैं। कुछ मॉडल प्रमाणीकरण का एक मजबूत, हस्तांतरणीय रूप मानते हैं, जहां प्रत्येक संदेश पर प्रेषक द्वारा हस्ताक्षर किए जाते हैं, ताकि प्राप्तकर्ता न केवल प्रत्येक संदेश के तत्काल स्रोत को जानता है, बल्कि उस भागीदार को भी जानता है जिसने शुरू में संदेश बनाया था। इस मजबूत प्रकार का प्रमाणीकरण डिजिटल हस्ताक्षरों द्वारा प्राप्त किया जाता है, और जब प्रमाणीकरण का यह मजबूत रूप उपलब्ध होता है, तो प्रोटोकॉल बड़ी संख्या में दोषों को सहन कर सकते हैं।<ref name="dolev strong">{{Cite journal | doi = 10.1137/0212045 | volume = 12 | issue = 4 | journal = SIAM Journal on Computing | year = 1983 | last1 = Dolev | first1 = D. | last2 = Strong | first2 = H.R. | title = बीजान्टिन समझौते के लिए प्रमाणित एल्गोरिदम| pages = 656–666 }}</ref>
संचार प्रोटोकॉल के अधिकांश मॉडलों में प्रतिभागी प्रमाणित चैनलों के माध्यम से संवाद करते हैं। इसका अर्थ यह है कि संदेश अस्पष्ट नहीं होते हैं और प्राप्तकर्ता उन्हें प्राप्त होने वाले प्रत्येक संदेश का सोर्स जानते हैं। कुछ मॉडल प्रमाणीकरण का एक जटिल स्थानांतरणीय रूप मानते हैं, जहां प्रत्येक संदेश पर प्रेषक द्वारा हस्ताक्षर किए जाते हैं, ताकि प्राप्तकर्ता न केवल प्रत्येक संदेश के सोर्स को जानता है, बल्कि उस भागीदार को भी जानता है जिसने प्रारम्भ में संदेश बनाया था। इस जटिल प्रकार का प्रमाणीकरण को डिजिटल हस्ताक्षरों द्वारा प्राप्त किया जाता है और जब प्रमाणीकरण का यह जटिल रूप उपलब्ध होता है तो प्रोटोकॉल बड़ी संख्या में दोषों को सहन कर सकते हैं।<ref name="dolev strong">{{Cite journal | doi = 10.1137/0212045 | volume = 12 | issue = 4 | journal = SIAM Journal on Computing | year = 1983 | last1 = Dolev | first1 = D. | last2 = Strong | first2 = H.R. | title = बीजान्टिन समझौते के लिए प्रमाणित एल्गोरिदम| pages = 656–666 }}</ref>


दो अलग-अलग प्रमाणीकरण मॉडल को प्रायः मौखिक संचार और लिखित संचार मॉडल कहा जाता है। मौखिक संचार मॉडल में, सूचना का तत्काल स्रोत ज्ञात होता है, जबकि मजबूत, लिखित संचार मॉडल में, रिसीवर के हर कदम पर न केवल संदेश का तत्काल स्रोत पता चलता है, बल्कि संदेश का संचार इतिहास भी पता चलता है।<ref name="GLR95">{{Cite journal | url = http://www.csl.sri.com/papers/dcca95/ | volume = 10 | journal = Dependable Computing for Critical Applications | year = 1995 | last1 = Gong | first1 = Li | last2 = Lincoln | first2 = Patrick | last3 = Rushby | first3 = John | title = Byzantine Agreement with authentication }}</ref>
दो अलग-अलग प्रमाणीकरण मॉडल को प्रायः मौखिक संचार और लिखित संचार मॉडल कहा जाता है। मौखिक संचार मॉडल में सूचना का शीघ्र सोर्स ज्ञात होता है, जबकि जटिल लिखित संचार मॉडल में अभिग्राही के प्रत्येक चरण पर संदेश के सोर्स के साथ साथ संदेश का संचार इतिहास भी पता चलता है।<ref name="GLR95">{{Cite journal | url = http://www.csl.sri.com/papers/dcca95/ | volume = 10 | journal = Dependable Computing for Critical Applications | year = 1995 | last1 = Gong | first1 = Li | last2 = Lincoln | first2 = Patrick | last3 = Rushby | first3 = John | title = Byzantine Agreement with authentication }}</ref>
=== कॉन्सेंसस के इनपुट और आउटपुट ===
=== कॉन्सेंसस के इनपुट और आउटपुट ===


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


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


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


=== दुर्घटना और बीजान्टिन विफलताएँ ===
=== क्रैश और बीजान्टिन विफलताएँ ===
{{See also|बीजान्टिन विफलता
{{See also|बीजान्टिन विफलता
}}
}}


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


इस प्रकार, बीजान्टिन विफलताओं को सहन करने वाला एक कॉन्सेंसस प्रोटोकॉल हर संभावित त्रुटि के प्रति लचीला होना चाहिए।
;अखंडता: यदि कोई सही प्रक्रिया <math>v</math> का निर्णय करती है, तो <math>v</math> को किसी सही प्रक्रिया द्वारा प्रस्तावित किया जा सकता है।
 
बीजान्टिन विफलताओं को सहन करने वाली कॉन्सेंसस का एक मजबूत संस्करण सत्यनिष्ठा बाधा को मजबूत करके दिया गया है:
 
;अखंडता: यदि एक सही प्रक्रिया निर्णय लेती है <math>v</math>, तब <math>v</math> किसी सही प्रक्रिया द्वारा प्रस्तावित किया गया होगा।


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


एसिंक्रोनाइज़ या सिंक्रोनाइज़ सिस्टम के मामले में कॉन्सेंसस की समस्या पर विचार किया जा सकता है। जबकि वास्तविक दुनिया संचार प्रायः स्वाभाविक रूप से असिंक्रोनाइज़ होते हैं, सिंक्रोनाइज़ सिस्टम को मॉडल करना अधिक व्यावहारिक और प्रायः आसान होता है<ref name="aguilera_stumbling">{{Cite book | doi = 10.1007/978-3-642-11294-2_4| chapter = Stumbling over Consensus Research: Misunderstandings and Issues| volume = 5959| pages = 59–72| series = Lecture Notes in Computer Science| year = 2010| last1 = Aguilera | first1 = M. K. | title = प्रतिकृति| isbn = 978-3-642-11293-5}}</ref> यह देखते हुए कि एसिंक्रोनाइज़ सिस्टम में स्वाभाविक रूप से सिंक्रोनाइज़ की तुलना में अधिक समस्याएं सम्मिलित होती हैं।
असिंक्रोनाइज़ या सिंक्रोनाइज़ सिस्टम की स्थिति में कॉन्सेंसस की समस्या पर विचार किया जा सकता है। जबकि वास्तविक विश्व संचार प्रायः स्वाभाविक रूप से असिंक्रोनाइज़ होते हैं। सिंक्रोनाइज़ सिस्टम को मॉडल करना अधिक व्यावहारिक और प्रायः आसान होता है यह देखते हुए कि असिंक्रोनाइज़ सिस्टम में स्वाभाविक रूप से सिंक्रोनाइज़ की तुलना में अधिक समस्याएं सम्मिलित होती हैं।<ref name="aguilera_stumbling">{{Cite book | doi = 10.1007/978-3-642-11294-2_4| chapter = Stumbling over Consensus Research: Misunderstandings and Issues| volume = 5959| pages = 59–72| series = Lecture Notes in Computer Science| year = 2010| last1 = Aguilera | first1 = M. K. | title = प्रतिकृति| isbn = 978-3-642-11293-5}}</ref>
 
सिंक्रोनाइज़ सिस्टम में, यह माना जाता है कि सभी संचार राउंड में आगे बढ़ते हैं। एक दौर में, एक प्रक्रिया अन्य प्रक्रियाओं से सभी संदेश प्राप्त करते हुए, आवश्यक सभी संदेश भेज सकती है। इस प्रकार, एक दौर का कोई भी संदेश उसी दौर में भेजे गए किसी भी संदेश को प्रभावित नहीं कर सकता है।


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


पूरी तरह से असिंक्रोनाइज़ संदेश-पासिंग वितरित प्रणाली में, जिसमें कम से कम एक प्रक्रिया में क्रैश विफलता हो सकती है, फिशर, लिंच और पैटर्सन द्वारा प्रसिद्ध 1985 एफएलपी असंभवता परिणाम में यह साबित हुआ है कि कॉन्सेंसस प्राप्त करने के लिए एक नियतात्मक एल्गोरिदम असंभव है।<ref name="fischer_impossibility">{{Cite journal | last1 = Fischer | first1 = M. J. |author-link1=Michael J. Fischer| last2 = Lynch | first2 = N. A. |author-link2=Nancy Lynch| last3 = Paterson | first3 = M. S. |author-link3=Michael S. Paterson| doi = 10.1145/3149.214121 | title = एक दोषपूर्ण प्रक्रिया के साथ वितरित सर्वसम्मति की असंभवता| journal = [[Journal of the ACM]]| volume = 32 | issue = 2 | pages = 374–382 | year = 1985 | s2cid = 207660233 | url = https://groups.csail.mit.edu/tds/papers/Lynch/jacm85.pdf}}</ref> यह असंभव परिणाम सबसे खराब स्थिति वाले शेड्यूलिंग परिदृश्यों से उत्पन्न होता है, जो नेटवर्क में बुद्धिमान डिनायल-ऑफ-सर्विस हमलावर जैसी प्रतिकूल स्थितियों को छोड़कर व्यवहार में घटित होने की संभावना नहीं है। अधिकांश सामान्य स्थितियों में, प्रक्रिया शेड्यूलिंग में प्राकृतिक यादृच्छिकता की एक डिग्री होती है।<ref name="aguilera_stumbling"/>
==== असिंक्रोनाइज़ डेटर्मिनिस्टिक-कॉन्सेंसस के लिए एफएलपी असंभवता परिणाम ====


एक असिंक्रोनाइज़ मॉडल में, कुछ प्रकार की विफलताओं को एक तुल्यकालिक कॉन्सेंसस प्रोटोकॉल द्वारा नियंत्रित किया जा सकता है। उदाहरण के लिए, संचार लिंक के नुकसान को एक ऐसी प्रक्रिया के रूप में देखा जा सकता है जिसे बीजान्टिन विफलता का सामना करना पड़ा है।
पूरी तरह से असिंक्रोनाइज़ संदेश-पासिंग वितरित सिस्टम में जिसमें कम से कम एक प्रक्रिया में क्रैश विफलता हो सकती है। फिशर, लिंच और पैटर्सन द्वारा प्रसिद्ध 1985 एफएलपी असंभवता परिणाम में यह सिद्ध हुआ है कि कॉन्सेंसस प्राप्त करने के लिए एक नियतात्मक एल्गोरिदम असंभव है।<ref name="fischer_impossibility">{{Cite journal | last1 = Fischer | first1 = M. J. |author-link1=Michael J. Fischer| last2 = Lynch | first2 = N. A. |author-link2=Nancy Lynch| last3 = Paterson | first3 = M. S. |author-link3=Michael S. Paterson| doi = 10.1145/3149.214121 | title = एक दोषपूर्ण प्रक्रिया के साथ वितरित सर्वसम्मति की असंभवता| journal = [[Journal of the ACM]]| volume = 32 | issue = 2 | pages = 374–382 | year = 1985 | s2cid = 207660233 | url = https://groups.csail.mit.edu/tds/papers/Lynch/jacm85.pdf}}</ref> यह असंभव परिणाम सबसे जटिल स्थिति वाले नियतात्मक परिदृश्यों से उत्पन्न होता है, जो नेटवर्क में बुद्धिमत्ता डिनायल सेवा  जैसी विरोधात्मक स्थितियों को छोड़कर प्रायः घटित होने की संभावना नहीं है। अधिकांश सामान्य स्थितियों में डेटर्मिनिस्टिक-कॉन्सेंसस प्रक्रिया में प्राकृतिक यादृच्छिकता की एक डिग्री होती है।<ref name="aguilera_stumbling"/> एक असिंक्रोनाइज़ मॉडल में कुछ प्रकार की विफलताओं को एक सिंक्रोनाइज़ कॉन्सेंसस प्रोटोकॉल द्वारा नियंत्रित किया जा सकता है। उदाहरण के लिए संचार लिंक की कमी को एक ऐसी प्रक्रिया के रूप में देखा जा सकता है जिसे बीजान्टिन विफलता का सामना करना पड़ता है।


यादृच्छिक कॉन्सेंसस एल्गोरिदम नेटवर्क में सेवा हमलावर के बुद्धिमान इनकार जैसे सबसे खराब स्थिति वाले शेड्यूलिंग परिदृश्यों के तहत भी अत्यधिक संभावना के साथ सुरक्षा और जीवंतता दोनों प्राप्त करके एफएलपी असंभव परिणाम को दरकिनार कर सकते हैं।<ref>{{cite journal|title=समय- और स्थान-कुशल यादृच्छिक सहमति|first=James|last=Aspnes|journal=Journal of Algorithms|volume=14|number=3|date=May 1993|pages=414–431|doi=10.1006/jagm.1993.1022|url=https://www.sciencedirect.com/science/article/abs/pii/S0196677483710229}}</ref>
यादृच्छिक कॉन्सेंसस एल्गोरिदम नेटवर्क में डिनायल सेवा बुद्धिमत्ता जैसी सबसे अस्पष्ट स्थिति वाले नियतात्मक परिदृश्यों के अंतर्गत अत्यधिक संभावना के साथ सुरक्षा और लिवेन्सस दोनों को प्राप्त करके एफएलपी असंभव परिणाम को असिंक्रोनाइज़ कर सकते हैं।<ref>{{cite journal|title=समय- और स्थान-कुशल यादृच्छिक सहमति|first=James|last=Aspnes|journal=Journal of Algorithms|volume=14|number=3|date=May 1993|pages=414–431|doi=10.1006/jagm.1993.1022|url=https://www.sciencedirect.com/science/article/abs/pii/S0196677483710229}}</ref>
=== स्वीकृति बनाम स्वीकृति रहित कॉन्सेंसस ===
=== परमिशन और परमिशनलेस कॉन्सेंसस ===


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


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


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


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


===विश्वसनीय प्रसारण समाप्त करना===
===टर्मिनेशन रेलिएबल ब्रॉडकास्ट===
{{Main|Terminating Reliable Broadcast}}
{{Main|टर्मिनेट रेलिएबल ब्रॉडकास्ट}}


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


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


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


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


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


आंशिक रूप से समकालिक प्रणाली में n प्रक्रियाओं के लिए (सिस्टम समकालिकता की अच्छी और बुरी अवधि के बीच वैकल्पिक होता है), प्रत्येक प्रक्रिया एक निजी मान चुनती है। सार्वजनिक मान निर्धारित करने और निम्नलिखित आवश्यकताओं के साथ एक कॉन्सेंसस वेक्टर उत्पन्न करने के लिए प्रक्रियाएं राउंड द्वारा एक-दूसरे के साथ संवाद करती हैं:<ref>{{cite book|last=Milosevic|first=Zarko|author2=Martin Hutle|author3=Andre Schiper|title=कमजोर इंटरैक्टिव संगति के साथ बीजान्टिन सर्वसम्मति एल्गोरिदम को एकीकृत करना|journal=Principles of Distributed Systems, Lecture Notes in Computer Science|year=2009|volume=5293|pages=[https://archive.org/details/principlesofdist0000opod/page/300 300–314]|doi=10.1007/978-3-642-10877-8_24|series=Lecture Notes in Computer Science|isbn=978-3-642-10876-1|citeseerx=10.1.1.180.4229|url-access=registration|url=https://archive.org/details/principlesofdist0000opod/page/300}}</ref>
===वीक इंटरैक्टिव कंसिस्टेंसी===
# यदि कोई सही प्रक्रिया भेजता है <math>v</math>, तो सभी सही प्रक्रियाएं या तो प्राप्त होती हैं <math>v</math> या कुछ भी नहीं (अखंडता संपत्ति)
# एक सही प्रक्रिया द्वारा एक राउंड में भेजे गए सभी संदेश सभी सही प्रक्रियाओं (संगति संपत्ति) द्वारा एक ही राउंड में प्राप्त होते हैं।


यह दिखाया जा सकता है कि इन समस्याओं की विविधताएँ इस मायने में समतुल्य हैं कि एक प्रकार के मॉडल में किसी समस्या का समाधान दूसरे प्रकार के मॉडल में किसी अन्य समस्या का समाधान हो सकता है। उदाहरण के लिए, सिंक्रोनाइज़ प्रमाणित संदेश पासिंग मॉडल में कमजोर बीजान्टिन सामान्य समस्या का समाधान कमजोर इंटरैक्टिव संगति के समाधान की ओर ले जाता है।<ref name="lamport_WBGP">{{Cite journal | doi = 10.1145/2402.322398| title = कमजोर बीजान्टिन जनरलों की समस्या| journal = Journal of the ACM| volume = 30| issue = 3| page = 668| year = 1983| last1 = Lamport | first1 = L.| s2cid = 1574706| doi-access = free}}</ref> एक इंटरएक्टिव कंसिस्टेंसी एल्गोरिदम प्रत्येक प्रक्रिया को उसके कॉन्सेंसस वेक्टर में बहुमत मान को उसके कॉन्सेंसस मान के रूप में चुनकर कॉन्सेंसस की समस्या को हल कर सकता है।
आंशिक रूप से सिंक्रोनाइज़ सिस्टम में n प्रक्रियाओं के लिए (सिंक्रोनाइज़ सिस्टम के अच्छे और गलत समय के बीच वैकल्पिक होता है) प्रत्येक प्रक्रिया एक निजी मान का चयन करती है। सार्वजनिक मान निर्धारित करने और निम्नलिखित आवश्यकताओं के साथ एक कॉन्सेंसस एल्गोरिथ्म उत्पन्न करने के लिए प्रक्रियाएं राउंड द्वारा एक-दूसरे के साथ संचार करती हैं:<ref>{{cite book|last=Milosevic|first=Zarko|author2=Martin Hutle|author3=Andre Schiper|title=कमजोर इंटरैक्टिव संगति के साथ बीजान्टिन सर्वसम्मति एल्गोरिदम को एकीकृत करना|journal=Principles of Distributed Systems, Lecture Notes in Computer Science|year=2009|volume=5293|pages=[https://archive.org/details/principlesofdist0000opod/page/300 300–314]|doi=10.1007/978-3-642-10877-8_24|series=Lecture Notes in Computer Science|isbn=978-3-642-10876-1|citeseerx=10.1.1.180.4229|url-access=registration|url=https://archive.org/details/principlesofdist0000opod/page/300}}</ref>
# यदि एक सही प्रक्रिया <math>v</math> भेजती है, तो सभी सही प्रक्रियाओं को <math>v</math> का कोई भी मान नहीं प्राप्त होता है।
# एक सही प्रक्रिया द्वारा एक बार में भेजे गए सभी संदेश सभी सही प्रक्रियाओं द्वारा एक ही बार में प्राप्त होते हैं।


यह दिखाया जा सकता है कि इन समस्याओं की विविधताएँ इस मायने में समतुल्य हैं कि एक प्रकार के मॉडल में किसी समस्या का समाधान दूसरे प्रकार के मॉडल में किसी अन्य समस्या का समाधान हो सकता है। उदाहरण के लिए, सिंक्रोनाइज़ प्रमाणित संदेश पासिंग मॉडल में कमजोर बीजान्टिन सामान्य समस्या का समाधान कमजोर इंटरैक्टिव संगति के समाधान की ओर ले जाता है।<ref name="lamport_WBGP" /> एक इंटरएक्टिव कंसिस्टेंसी एल्गोरिदम प्रत्येक प्रक्रिया को उसके कॉन्सेंसस वेक्टर में बहुमत मान को उसके कॉन्सेंसस मान के रूप में चुनकर कॉन्सेंसस की समस्या को हल कर सकता है।<ref><nowiki><ref></nowiki>{{cite web|last=Fischer|first=Michael J|title=अविश्वसनीय वितरित प्रणालियों में आम सहमति की समस्या (एक संक्षिप्त सर्वेक्षण)|url=http://zoo.cs.yale.edu/classes/cs426/2012/bib/fischer83consensus.pdf|access-date=21 April 2014|archive-date=22 April 2014|archive-url=https://web.archive.org/web/20140422231847/http://zoo.cs.yale.edu/classes/cs426/2012/bib/fischer83consensus.pdf}}&lt;nowiki&gt;</ref></nowiki></ref>
यह दिखाया जा सकता है कि इन समस्याओं की विविधताएँ इस स्थिति में समतुल्य हैं कि एक प्रकार के मॉडल में किसी समस्या का समाधान दूसरे प्रकार के मॉडल में किसी अन्य समस्या का समाधान हो सकता है। उदाहरण के लिए सिंक्रोनाइज़ प्रमाणित संदेश पासिंग मॉडल में दुर्बल बीजान्टिन सामान्य समस्या का समाधान वीक इंटरैक्टिव कंसिस्टेंसी के समाधान की ओर ले जाता है।<ref name="lamport_WBGP">{{Cite journal | doi = 10.1145/2402.322398| title = कमजोर बीजान्टिन जनरलों की समस्या| journal = Journal of the ACM| volume = 30| issue = 3| page = 668| year = 1983| last1 = Lamport | first1 = L.| s2cid = 1574706| doi-access = free}}</ref> एक इंटरएक्टिव कंसिस्टेंसी एल्गोरिदम प्रत्येक प्रक्रिया को उसके कॉन्सेंसस एल्गोरिदम में बहुमत मान को उसके कॉन्सेंसस मान के रूप में चुनकर कॉन्सेंसस की समस्या को हल कर सकता है।<ref><nowiki><ref></nowiki>{{cite web|last=Fischer|first=Michael J|title=अविश्वसनीय वितरित प्रणालियों में आम सहमति की समस्या (एक संक्षिप्त सर्वेक्षण)|url=http://zoo.cs.yale.edu/classes/cs426/2012/bib/fischer83consensus.pdf|access-date=21 April 2014|archive-date=22 April 2014|archive-url=https://web.archive.org/web/20140422231847/http://zoo.cs.yale.edu/classes/cs426/2012/bib/fischer83consensus.pdf}}&lt;nowiki&gt;</ref>  


==कुछ समझौते की समस्याओं के लिए समाधानयोग्यता परिणाम==
==कुछ औपचारिक समस्याओं के लिए समाधान योग्य परिणाम==
एक टी-रेज़िलिएंट अनाम सिंक्रोनाइज़ प्रोटोकॉल है जो बीजान्टिन जनरल्स समस्या को हल करता है,<ref name="PSL82">{{Cite journal |last1=Lamport |first1=L. |author-link1=Leslie Lamport| last2=Shostak |first2=R. |last3=Pease |first3=M. |doi=10.1145/357172.357176 |title=बीजान्टिन जनरलों की समस्या|journal=ACM Transactions on Programming Languages and Systems |volume=4 |issue=3 |pages=382–401 |year=1982 |url=http://research.microsoft.com/en-us/um/people/lamport/pubs/byz.pdf| citeseerx=10.1.1.64.2312 |s2cid=55899582}}</ref><ref>{{cite journal |last=Lamport |first=Leslie |author2=Marshall Pease |author3=Robert Shostak |title=दोषों की उपस्थिति में समझौते पर पहुंचना|journal=Journal of the ACM |date=April 1980 |volume=27 |issue=2 |pages=228–234 |doi=10.1145/322186.322188 |url=http://research.microsoft.com/users/lamport/pubs/reaching.pdf |access-date=2007-07-25 |citeseerx=10.1.1.68.4044 |s2cid=6429068}}</ref> अगर <math>\tfrac{t}{n} < \tfrac{1}{3}</math> और कमजोर बीजान्टिन जनरलों का मामला<ref name="lamport_WBGP"/> कहाँ <math>t</math> विफलताओं की संख्या है और <math>n</math> प्रक्रियाओं की संख्या है.
एक टी-रेज़िलिएंट अनाम सिंक्रोनाइज़ प्रोटोकॉल है जो बीजान्टिन जनरल समस्या को हल करता है,<ref name="PSL82">{{Cite journal |last1=Lamport |first1=L. |author-link1=Leslie Lamport| last2=Shostak |first2=R. |last3=Pease |first3=M. |doi=10.1145/357172.357176 |title=बीजान्टिन जनरलों की समस्या|journal=ACM Transactions on Programming Languages and Systems |volume=4 |issue=3 |pages=382–401 |year=1982 |url=http://research.microsoft.com/en-us/um/people/lamport/pubs/byz.pdf| citeseerx=10.1.1.64.2312 |s2cid=55899582}}</ref><ref>{{cite journal |last=Lamport |first=Leslie |author2=Marshall Pease |author3=Robert Shostak |title=दोषों की उपस्थिति में समझौते पर पहुंचना|journal=Journal of the ACM |date=April 1980 |volume=27 |issue=2 |pages=228–234 |doi=10.1145/322186.322188 |url=http://research.microsoft.com/users/lamport/pubs/reaching.pdf |access-date=2007-07-25 |citeseerx=10.1.1.68.4044 |s2cid=6429068}}</ref> अगर <math>\tfrac{t}{n} < \tfrac{1}{3}</math> और कमजोर बीजान्टिन जनरलों का मामला<ref name="lamport_WBGP"/> कहाँ <math>t</math> विफलताओं की संख्या है और <math>n</math> प्रक्रियाओं की संख्या है.


के साथ सिस्टम के लिए <math>n</math> प्रोसेसर, जिनमें से <math>f</math> बीजान्टिन हैं, यह दिखाया गया है कि कोई एल्गोरिदम मौजूद नहीं है जो कॉन्सेंसस की समस्या को हल करता है <math>n \leq 3f</math> मौखिक-संदेश मॉडल में.<ref>{{cite book |first=Hagit |last=Attiya |author-link=Hagit Attiya |title=वितरित अभिकलन|edition=2nd |year=2004 |publisher=Wiley |isbn=978-0-471-45324-6 |pages=101–103}}</ref> प्रमाण का निर्माण पहले तीन-नोड मामले के लिए असंभवता दिखाकर किया जाता है <math>n=3</math> और प्रोसेसर के विभाजन के बारे में बहस करने के लिए इस परिणाम का उपयोग करें। लिखित-संदेश मॉडल में ऐसे प्रोटोकॉल होते हैं जो सहन कर सकते हैं <math>n=f+1</math>.<ref name="dolev strong"/>
के साथ सिस्टम के लिए <math>n</math> प्रोसेसर, जिनमें से <math>f</math> बीजान्टिन हैं, यह दिखाया गया है कि कोई एल्गोरिदम मौजूद नहीं है जो कॉन्सेंसस की समस्या को हल करता है <math>n \leq 3f</math> मौखिक-संदेश मॉडल में.<ref>{{cite book |first=Hagit |last=Attiya |author-link=Hagit Attiya |title=वितरित अभिकलन|edition=2nd |year=2004 |publisher=Wiley |isbn=978-0-471-45324-6 |pages=101–103}}</ref> प्रमाण का निर्माण पहले तीन-नोड मामले के लिए असंभवता दिखाकर किया जाता है <math>n=3</math> और प्रोसेसर के विभाजन के बारे में बहस करने के लिए इस परिणाम का उपयोग करें। लिखित-संदेश मॉडल में ऐसे प्रोटोकॉल होते हैं जो सहन कर सकते हैं <math>n=f+1</math>.<ref name="dolev strong"/>


पूरी तरह से असिंक्रोनाइज़ प्रणाली में कोई सर्वसम्मत समाधान नहीं है जो केवल गैर-तुच्छता संपत्ति की आवश्यकता होने पर भी एक या अधिक क्रैश विफलताओं को सहन कर सके।<ref name="fischer_impossibility"/> इस परिणाम को कभी-कभी लेखकों माइकल जे. फिशर, [[नैन्सी लिंच]] और [[माइक पैटर्सन]] के नाम पर एफएलपी असंभव प्रमाण कहा जाता है, जिन्हें इस महत्वपूर्ण कार्य के लिए डिजस्ट्रा पुरस्कार से सम्मानित किया गया था। एफएलपी परिणाम को निष्पक्षता मान्यताओं के तहत भी बनाए रखने के लिए यांत्रिक रूप से सत्यापित किया गया है।<ref name="flp_verification">{{Citation |title=Mechanical Verification of a Constructive Proof for FLP |last1=Bisping |first1=Benjamin |volume=9807 |date=2016 |last2=Brodmann |first2=Paul-David |last3=Jungnickel |first3=Tim |last4=Rickmann |first4=Christina |last5=Seidler |first5=Henning |last6=Stüber |first6=Anke |last7=Wilhelm-Weidner |first7=Arno |last8=Peters |first8=Kirstin |last9=Nestmann |first9=Uwe |series=Lecture Notes in Computer Science |issue=Interactive Theorem Proving. ITP 2016 |doi=10.1007/978-3-319-43144-4_7 |isbn=978-3-319-43144-4 |display-authors=1 |editor-last=Blanchette |editor-first=Jasmin Christian |editor2-last=Merz |editor2-first=Stephan |publisher=Springer International Publishing}}</ref> हालाँकि, एफएलपी यह नहीं बताता है कि कॉन्सेंसस कभी नहीं पहुँच सकती: केवल यह कि मॉडल की मान्यताओं के तहत, कोई भी एल्गोरिदम हमेशा निर्धारित समय में कॉन्सेंसस तक नहीं पहुँच सकता है। व्यवहार में ऐसा होने की अत्यधिक संभावना नहीं है।
पूरी तरह से असिंक्रोनाइज़ सिस्टम में कोई सर्वसम्मत समाधान नहीं है जो केवल गैर-तुच्छता संपत्ति की आवश्यकता होने पर भी एक या अधिक क्रैश विफलताओं को सहन कर सके।<ref name="fischer_impossibility"/> इस परिणाम को कभी-कभी लेखकों माइकल जे. फिशर, [[नैन्सी लिंच]] और [[माइक पैटर्सन]] के नाम पर एफएलपी असंभव प्रमाण कहा जाता है, जिन्हें इस महत्वपूर्ण कार्य के लिए डिजस्ट्रा पुरस्कार से सम्मानित किया गया था। एफएलपी परिणाम को निष्पक्षता मान्यताओं के तहत भी बनाए रखने के लिए यांत्रिक रूप से सत्यापित किया गया है।<ref name="flp_verification">{{Citation |title=Mechanical Verification of a Constructive Proof for FLP |last1=Bisping |first1=Benjamin |volume=9807 |date=2016 |last2=Brodmann |first2=Paul-David |last3=Jungnickel |first3=Tim |last4=Rickmann |first4=Christina |last5=Seidler |first5=Henning |last6=Stüber |first6=Anke |last7=Wilhelm-Weidner |first7=Arno |last8=Peters |first8=Kirstin |last9=Nestmann |first9=Uwe |series=Lecture Notes in Computer Science |issue=Interactive Theorem Proving. ITP 2016 |doi=10.1007/978-3-319-43144-4_7 |isbn=978-3-319-43144-4 |display-authors=1 |editor-last=Blanchette |editor-first=Jasmin Christian |editor2-last=Merz |editor2-first=Stephan |publisher=Springer International Publishing}}</ref> हालाँकि, एफएलपी यह नहीं बताता है कि कॉन्सेंसस कभी नहीं पहुँच सकती: केवल यह कि मॉडल की मान्यताओं के तहत, कोई भी एल्गोरिदम हमेशा निर्धारित समय में कॉन्सेंसस तक नहीं पहुँच सकता है। व्यवहार में ऐसा होने की अत्यधिक संभावना नहीं है।


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


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


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




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


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


अन्य क्रिप्टोकरेंसी (यानी NEO, STRATIS, ...) हिस्सेदारी के प्रमाण का उपयोग करते हैं, जिसमें नोड्स ब्लॉक को जोड़ने और हिस्सेदारी के अनुपात में संबंधित पुरस्कार अर्जित करने के लिए प्रतिस्पर्धा करते हैं, या मौजूदा क्रिप्टोकरेंसी को कुछ समय अवधि के लिए आवंटित और लॉक या स्टेक किया जाता है। 'कार्य का प्रमाण' प्रणाली की तुलना में 'हिस्सेदारी का प्रमाण' का एक फायदा, बाद वाले द्वारा मांग की जाने वाली उच्च ऊर्जा खपत है। उदाहरण के तौर पर, बिटकॉइन माइनिंग (2018) में गैर-नवीकरणीय ऊर्जा स्रोतों की खपत चेक गणराज्य या जॉर्डन के पूरे देशों के समान मात्रा में होने का अनुमान है।<ref>{{Cite web |first=Umair |last=Irfan |url=https://www.vox.com/2019/6/18/18642645/bitcoin-energy-price-renewable-china |title=Bitcoin is an energy hog. Where is all that electricity coming from?|date=June 18, 2019 |website=Vox}}</ref>
अन्य क्रिप्टोकरेंसी (यानी NEO, STRATIS, ...) हिस्सेदारी के प्रमाण का उपयोग करते हैं, जिसमें नोड्स ब्लॉक को जोड़ने और हिस्सेदारी के अनुपात में संबंधित पुरस्कार अर्जित करने के लिए प्रतिस्पर्धा करते हैं, या मौजूदा क्रिप्टोकरेंसी को कुछ समय अवधि के लिए आवंटित और लॉक या स्टेक किया जाता है। 'कार्य का प्रमाण' सिस्टम की तुलना में 'हिस्सेदारी का प्रमाण' का एक फायदा, बाद वाले द्वारा मांग की जाने वाली उच्च ऊर्जा खपत है। उदाहरण के तौर पर, बिटकॉइन माइनिंग (2018) में गैर-नवीकरणीय ऊर्जा सोर्सों की खपत चेक गणराज्य या जॉर्डन के पूरे देशों के समान मात्रा में होने का अनुमान है।<ref>{{Cite web |first=Umair |last=Irfan |url=https://www.vox.com/2019/6/18/18642645/bitcoin-energy-price-renewable-china |title=Bitcoin is an energy hog. Where is all that electricity coming from?|date=June 18, 2019 |website=Vox}}</ref>


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


:चरण 1: प्रत्येक सर्वर वैध उम्मीदवार लेनदेन की एक सूची संकलित करता है;
:चरण 1: प्रत्येक सर्वर वैध उम्मीदवार लेनदेन की एक सूची संकलित करता है;
Line 188: Line 180:
:चरण 3: न्यूनतम सीमा पार करने वाले लेनदेन को अगले दौर में भेज दिया जाता है;
:चरण 3: न्यूनतम सीमा पार करने वाले लेनदेन को अगले दौर में भेज दिया जाता है;
:चरण 4: अंतिम दौर में 80% कॉन्सेंसस की आवश्यकता है।<ref>{{cite web |last1=Schwartz |first1=David |last2=Youngs |first2=Noah |last3=Britto |first3=Arthur |date=2014 |title=रिपल प्रोटोकॉल सर्वसम्मति एल्गोरिदम|type=Draft |website=Ripple Labs |url= https://ripple.com/files/ripple_consensus_whitepaper.pdf}}</ref>
:चरण 4: अंतिम दौर में 80% कॉन्सेंसस की आवश्यकता है।<ref>{{cite web |last1=Schwartz |first1=David |last2=Youngs |first2=Noah |last3=Britto |first3=Arthur |date=2014 |title=रिपल प्रोटोकॉल सर्वसम्मति एल्गोरिदम|type=Draft |website=Ripple Labs |url= https://ripple.com/files/ripple_consensus_whitepaper.pdf}}</ref>
प्रवेश में बाधाएं लगाने और सिबिल हमलों का विरोध करने के लिए स्वीकृति रहित कॉन्सेंसस प्रोटोकॉल में उपयोग किए जाने वाले अन्य भागीदारी नियमों में अधिकार का प्रमाण, स्थान का प्रमाण, जलने का प्रमाण, या बीते समय का प्रमाण सम्मिलित है।
प्रवेश में बाधाएं लगाने और सिबिल हमलों का विरोध करने के लिए परमिशनलेस कॉन्सेंसस प्रोटोकॉल में उपयोग किए जाने वाले अन्य भागीदारी नियमों में अधिकार का प्रमाण, स्थान का प्रमाण, जलने का प्रमाण, या बीते समय का प्रमाण सम्मिलित है।


उपरोक्त स्वीकृति रहित भागीदारी नियमों के विपरीत, जिनमें से सभी प्रतिभागियों को किसी कार्रवाई या संसाधन में निवेश की मात्रा के अनुपात में पुरस्कृत करते हैं, व्यक्तित्व के प्रमाण प्रोटोकॉल का उद्देश्य प्रत्येक वास्तविक मानव प्रतिभागी को आर्थिक निवेश की परवाह किए बिना स्वीकृति रहित कॉन्सेंसस में मतदान शक्ति की एक इकाई देना है।<ref>{{cite conference |author1=Maria Borge |author2=Eleftherios Kokoris-Kogias |author3=Philipp Jovanovic |author4=Linus Gasser |author5=Nicolas Gailly |author6=Bryan Ford |title=Proof-of-Personhood: Redemocratizing Permissionless Cryptocurrencies |conference=IEEE Security & Privacy on the Blockchain (IEEE S&B) |conference-url=https://prosecco.gforge.inria.fr/ieee-blockchain2016/ |date=29 April 2017 |doi=10.1109/EuroSPW.2017.46 |url=https://ieeexplore.ieee.org/document/7966966}}</ref><ref>{{cite arXiv|author1=Divya Siddarth |author2=Sergey Ivliev |author3=Santiago Siri |author4=Paula Berman |title=Who Watches the Watchmen? A Review of Subjective Approaches for Sybil-resistance in Proof of Personhood Protocols|eprint=2008.05300|date=13 Oct 2020|class=cs.CR}}</ref> व्यक्तित्व के प्रमाण के लिए कॉन्सेंसस शक्ति के एक-व्यक्ति वितरण को प्राप्त करने के लिए प्रस्तावित दृष्टिकोण में भौतिक छद्म नाम वाली पार्टियां<ref>{{cite conference |doi=10.1145/1435497.1435503 |title=ऑनलाइन जवाबदेह छद्मनामों के लिए एक ऑफ़लाइन फाउंडेशन|isbn=978-1-60558-124-8 |conference=1st Workshop on Social Network Systems - SocialNets '08 |pages=31–36 |date=April 2008 |last1=Ford |first1=Bryan |last2=Strauss |first2=Jacob |conference-url=https://dl.acm.org/doi/proceedings/10.1145/1435497}}</ref> सामाजिक नेटवर्क<ref>{{cite conference |title=सिबिल-रेज़िलिएंट सामुदायिक विकास के लिए वास्तविक व्यक्तिगत पहचानकर्ता और पारस्परिक ज़मानत|author1=Gal Shahaf |author2=Ehud Shapiro |author3=Nimrod Talmon |conference=International Conference on Social Informatics |conference-url=https://kdd.isti.cnr.it/socinfo2020/index.html |date=October 2020|doi=10.1007/978-3-030-60975-7_24 |url=https://link.springer.com/chapter/10.1007/978-3-030-60975-7_24}}</ref> छद्म नाम से सरकार द्वारा जारी पहचान<ref>{{cite web|title=CanDID: Can-Do Decentralized Identity with Legacy Compatibility, Sybil-Resistance, and Accountability|author1=Deepak Maram |author2=Harjasleen Malvai |author3=Fan Zhang |author4=Nerla Jean-Louis |author5=Alexander Frolov |author6=Tyler Kell |author7=Tyrone Lobban |author8=Christine Moy |author9=Ari Juels |author10=Andrew Miller |url=https://eprint.iacr.org/2020/934.pdf |date=28 Sep 2020}}</ref> और बायोमेट्रिक्स सम्मिलित हैं।<ref>{{cite arXiv |title=UniqueID: Decentralized Proof-of-Unique-Human |author1=Mohammad-Javad Hajialikhani |author2=Mohammad-Mahdi Jahanara |eprint=1806.07583|date=20 June 2018 |class=cs.CR}}</ref>
'''उपरोक्त परमिशनलेस पार्टिसिपेशन नियमों के''' विपरीत जिनमें से सभी पार्टिसिपेशनों को किसी नियम या संसाधन में निवेश की मात्रा के अनुपात में पुरस्कृत करते हैं, व्यक्तित्व के प्रमाण प्रोटोकॉल का उद्देश्य प्रत्येक वास्तविक मानव पार्टिसिपेशन को आर्थिक निवेश की चिंता किए बिना परमिशनलेस कॉन्सेंसस में मतदान शक्ति की एक इकाई देना है।<ref>{{cite conference |author1=Maria Borge |author2=Eleftherios Kokoris-Kogias |author3=Philipp Jovanovic |author4=Linus Gasser |author5=Nicolas Gailly |author6=Bryan Ford |title=Proof-of-Personhood: Redemocratizing Permissionless Cryptocurrencies |conference=IEEE Security & Privacy on the Blockchain (IEEE S&B) |conference-url=https://prosecco.gforge.inria.fr/ieee-blockchain2016/ |date=29 April 2017 |doi=10.1109/EuroSPW.2017.46 |url=https://ieeexplore.ieee.org/document/7966966}}</ref><ref>{{cite arXiv|author1=Divya Siddarth |author2=Sergey Ivliev |author3=Santiago Siri |author4=Paula Berman |title=Who Watches the Watchmen? A Review of Subjective Approaches for Sybil-resistance in Proof of Personhood Protocols|eprint=2008.05300|date=13 Oct 2020|class=cs.CR}}</ref> व्यक्तित्व के प्रमाण के लिए कॉन्सेंसस शक्ति के एक-व्यक्ति वितरण को प्राप्त करने के लिए प्रस्तावित दृष्टिकोण में भौतिक छद्म नाम वाली पार्टियां<ref>{{cite conference |doi=10.1145/1435497.1435503 |title=ऑनलाइन जवाबदेह छद्मनामों के लिए एक ऑफ़लाइन फाउंडेशन|isbn=978-1-60558-124-8 |conference=1st Workshop on Social Network Systems - SocialNets '08 |pages=31–36 |date=April 2008 |last1=Ford |first1=Bryan |last2=Strauss |first2=Jacob |conference-url=https://dl.acm.org/doi/proceedings/10.1145/1435497}}</ref> सामाजिक नेटवर्क<ref>{{cite conference |title=सिबिल-रेज़िलिएंट सामुदायिक विकास के लिए वास्तविक व्यक्तिगत पहचानकर्ता और पारस्परिक ज़मानत|author1=Gal Shahaf |author2=Ehud Shapiro |author3=Nimrod Talmon |conference=International Conference on Social Informatics |conference-url=https://kdd.isti.cnr.it/socinfo2020/index.html |date=October 2020|doi=10.1007/978-3-030-60975-7_24 |url=https://link.springer.com/chapter/10.1007/978-3-030-60975-7_24}}</ref> छद्म नाम से सरकार द्वारा जारी पहचान<ref>{{cite web|title=CanDID: Can-Do Decentralized Identity with Legacy Compatibility, Sybil-Resistance, and Accountability|author1=Deepak Maram |author2=Harjasleen Malvai |author3=Fan Zhang |author4=Nerla Jean-Louis |author5=Alexander Frolov |author6=Tyler Kell |author7=Tyrone Lobban |author8=Christine Moy |author9=Ari Juels |author10=Andrew Miller |url=https://eprint.iacr.org/2020/934.pdf |date=28 Sep 2020}}</ref> और बायोमेट्रिक्स सम्मिलित हैं।<ref>{{cite arXiv |title=UniqueID: Decentralized Proof-of-Unique-Human |author1=Mohammad-Javad Hajialikhani |author2=Mohammad-Mahdi Jahanara |eprint=1806.07583|date=20 June 2018 |class=cs.CR}}</ref>
==कॉन्सेंसस संख्या==
==कॉन्सेंसस संख्या==
साझा-स्मृति प्रणाली में कॉन्सेंसस की समस्या को हल करने के लिए, समवर्ती वस्तुओं को पेश किया जाना चाहिए। एक समवर्ती वस्तु, या साझा वस्तु, एक डेटा संरचना है जो समवर्ती प्रक्रियाओं को एक समझौते तक पहुंचने के लिए संचार करने में मदद करती है। यदि कोई प्रक्रिया महत्वपूर्ण अनुभाग के अंदर समाप्त हो जाती है या असहनीय रूप से लंबे समय तक निष्क्रिय रहती है, तो महत्वपूर्ण अनुभागों का उपयोग करने वाले पारंपरिक कार्यान्वयन को क्रैश होने का खतरा होता है। शोधकर्ताओं ने प्रतीक्षा-स्वतंत्रता को इस गारंटी के रूप में परिभाषित किया कि एल्गोरिदम चरणों की एक सीमित संख्या में पूरा होता है।
साझा-मेमोरी सिस्टम में कॉन्सेंसस की समस्या को हल करने के लिए समवर्ती ऑब्जेक्ट को प्रस्तुत किया जाना चाहिए। एक समवर्ती ऑब्जेक्ट या साझा ऑब्जेक्ट एक डेटा संरचना है जो समवर्ती प्रक्रियाओं को एक समझौते तक अभिगम्य के लिए संचार करने में सहायता करती है। यदि कोई प्रक्रिया महत्वपूर्ण भाग के अंदर समाप्त हो जाती है या असहनीय रूप से लंबे समय तक निष्क्रिय रहती है, तो महत्वपूर्ण भागों का उपयोग करने वाले पारंपरिक कार्यान्वयन को क्रैश होने का जोखिम होता है। शोधकर्ताओं ने फ्रीडम को इस गारंटी के रूप में परिभाषित किया है कि एल्गोरिदम चरणों की एक सीमित संख्या में पूरा होता है।


समवर्ती वस्तु की कॉन्सेंसस संख्या को सिस्टम में प्रक्रियाओं की अधिकतम संख्या के रूप में परिभाषित किया गया है जो प्रतीक्षा-मुक्त कार्यान्वयन में दिए गए ऑब्जेक्ट द्वारा कॉन्सेंसस तक पहुंच सकती है।<ref name="hierarchy">{{cite journal |last=Herlihy |first=Maurice |date=January 1991 |title=प्रतीक्षा-मुक्त तुल्यकालन|journal=ACM TransactIons on Programming Languages and Systems |volume=11 |issue=1 |url=http://www.cs.brown.edu/~mph/Herlihy91/p124-herlihy.pdf |access-date=19 December 2011 |pages=124-149}}</ref> <math>n</math> की कॉन्सेंसस संख्या वाली वस्तुएँ <math>n</math> या उससे कम की कॉन्सेंसस संख्या वाली किसी भी वस्तु को लागू कर सकती हैं, लेकिन उच्च कॉन्सेंसस संख्या वाली किसी भी वस्तु को लागू नहीं कर सकती हैं। सर्वसम्मत संख्याएँ वह बनाती हैं जिसे [[मौरिस हेर्लिही]] का सिंक्रनाइज़ेशन ऑब्जेक्ट का पदानुक्रम कहा जाता है।<ref>{{cite journal |last1=Imbs |first1=Damien |last2=Raynal |first2=Michel |date=25 July 2010 |title=सर्वसम्मत संख्याओं की गुणात्मक शक्ति|journal=Proceedings of the 29th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing |pages=26–35 |doi=10.1145/1835698.1835705 |publisher=Association for Computing Machinery |isbn=978-1-60558-888-9 |s2cid=3179361 |url=https://hal.inria.fr/inria-00454399/file/PI-1949.pdf |access-date=22 April 2021}}</ref>
समवर्ती ऑब्जेक्ट की कॉन्सेंसस संख्या को सिस्टम में प्रक्रियाओं की अधिकतम संख्या के रूप में परिभाषित किया गया है जो फ्री कार्यान्वयन में दिए गए ऑब्जेक्ट द्वारा कॉन्सेंसस तक अभिगम्य हो सकती है।<ref name="hierarchy">{{cite journal |last=Herlihy |first=Maurice |date=January 1991 |title=प्रतीक्षा-मुक्त तुल्यकालन|journal=ACM TransactIons on Programming Languages and Systems |volume=11 |issue=1 |url=http://www.cs.brown.edu/~mph/Herlihy91/p124-herlihy.pdf |access-date=19 December 2011 |pages=124-149}}</ref> <math>n</math> की कॉन्सेंसस संख्या वाला ऑब्जेक्ट <math>n</math> या उससे कम की कॉन्सेंसस संख्या वाले किसी भी ऑब्जेक्ट को प्रयुक्त कर सकते हैं, लेकिन उच्च कॉन्सेंसस संख्या वाले किसी भी ऑब्जेक्ट को प्रयुक्त नहीं किया जा सकता है। कॉन्सेंसस संख्याएँ वे संख्याएं हैं जिसे [[मौरिस हेर्लिही]] का सिंक्रनाइज़ेशन ऑब्जेक्ट कहा जाता है।<ref>{{cite journal |last1=Imbs |first1=Damien |last2=Raynal |first2=Michel |date=25 July 2010 |title=सर्वसम्मत संख्याओं की गुणात्मक शक्ति|journal=Proceedings of the 29th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing |pages=26–35 |doi=10.1145/1835698.1835705 |publisher=Association for Computing Machinery |isbn=978-1-60558-888-9 |s2cid=3179361 |url=https://hal.inria.fr/inria-00454399/file/PI-1949.pdf |access-date=22 April 2021}}</ref>
{| class="wikitable"
{| class="wikitable"
|-
|-
Line 201: Line 193:
| <math>1</math> || [[Atomic semantics|एटॉमिक]] [[Shared register|रीड/राइट पंजीकरण]], [[Lock (computer science)|म्युटेक्स]]
| <math>1</math> || [[Atomic semantics|एटॉमिक]] [[Shared register|रीड/राइट पंजीकरण]], [[Lock (computer science)|म्युटेक्स]]
|-
|-
| <math>2</math> || [[test-and-set]], [[Swap (computer programming)|स्वैप]], [[fetch-and-add|फ़ेच और एडीडी]] , wait-free [[Queue (abstract data type)|केयूए]] या [[Stack (abstract data type)|स्टैक]]
| <math>2</math> || [[test-and-set|परीक्षण और समूह]], [[Swap (computer programming)|स्वैप]], [[fetch-and-add|फ़ेच और एडीडी]], [[Queue (abstract data type)|केयूए]] या [[Stack (abstract data type)|स्टैक]]
|-
|-
| ... || ...
| ... || ...
|-
|-
| <math>2n-2</math> || n-register assignment
| <math>2n-2</math> || n-पंजीकरण असाइनमेंट
|-
|-
| ... || ...
| ... || ...
|-
|-
| <math>\infty</math> || [[compare-and-swap]], [[load-link/store-conditional]],<ref>{{cite journal |last1=Fich |first1=Faith |last2=Hendler |first2=Danny |last3=Shavit |first3=Nir |title=On the inherent weakness of conditional synchronization primitives |journal=Proceedings of the Twenty-Third Annual ACM Symposium on Principles of Distributed Computing |date=25 July 2004 |pages=80–87 |doi=10.1145/1011767.1011780 | citeseerx=10.1.1.96.9340 |publisher=Association for Computing Machinery|isbn=1-58113-802-4 |s2cid=9313205 }}</ref> memory-to-memory move and swap, queue with peek operation, fetch&cons, sticky byte
| <math>\infty</math> || [[compare-and-swap|कॉम्पेयर और स्वैप]], [[load-link/store-conditional|लोड-लिंक/स्टोर]],<ref>{{cite journal |last1=Fich |first1=Faith |last2=Hendler |first2=Danny |last3=Shavit |first3=Nir |title=On the inherent weakness of conditional synchronization primitives |journal=Proceedings of the Twenty-Third Annual ACM Symposium on Principles of Distributed Computing |date=25 July 2004 |pages=80–87 |doi=10.1145/1011767.1011780 | citeseerx=10.1.1.96.9340 |publisher=Association for Computing Machinery|isbn=1-58113-802-4 |s2cid=9313205 }}</ref> मेमोरी से मेमोरी स्वैप, पीक ऑपरेशन के साथ केयूए, फ़ेच & कॉन, स्ट्रिक बाइट
|}
|}
पदानुक्रम के अनुसार, पढ़ने/लिखने वाले रजिस्टर 2-प्रक्रिया प्रणाली में भी कॉन्सेंसस का समाधान नहीं कर सकते हैं। स्टैक और कतार जैसी डेटा संरचनाएं केवल दो प्रक्रियाओं के बीच कॉन्सेंसस का समाधान कर सकती हैं। हालाँकि, कुछ समवर्ती वस्तुएँ सार्वभौमिक हैं (तालिका में <math>\infty</math> के साथ अंकित है जिसका अर्थ है कि वे किसी भी संख्या में प्रक्रियाओं के बीच कॉन्सेंसस को हल कर सकते हैं और वे एक ऑपरेशन अनुक्रम के माध्यम से किसी भी अन्य कॉन्सेंसस का अनुकरण कर सकते हैं।<ref name="hierarchy"/>
सिंक्रनाइज़ेशन ऑब्जेक्ट के अनुसार [[Shared register|रीड/राइट]] वाले [[Shared register|पंजीकरण]] प्रक्रिया सिस्टम में भी कॉन्सेंसस का समाधान नहीं कर सकते हैं। स्टैक और केयूए जैसी डेटा संरचनाएं केवल दो प्रक्रियाओं के बीच कॉन्सेंसस का समाधान कर सकती हैं। हालाँकि, कुछ समवर्ती ऑब्जेक्ट सार्वभौमिक हैं जो तालिका में <math>\infty</math> के साथ अंकित है जिसका अर्थ है कि वे किसी भी संख्या में प्रक्रियाओं के बीच कॉन्सेंसस को हल कर सकते हैं और वे एक ऑपरेशन अनुक्रम के माध्यम से किसी भी अन्य कॉन्सेंसस का अनुकरण कर सकते हैं।<ref name="hierarchy"/>
==यह भी देखें==
==यह भी देखें==
* [[एकसमान सहमति|एकसमान कॉन्सेंसस]]
* [[एकसमान सहमति|एकसमान कॉन्सेंसस]]

Revision as of 12:08, 21 July 2023

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

समस्या विवरण

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  1. यदि प्रक्रिया सही है, तो प्रत्येक सही प्रक्रिया प्राप्त होती है।
  2. किन्हीं दो सही प्रक्रियाओं के लिए प्रत्येक प्रक्रिया का समान मान प्राप्त होता है।

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

कॉन्सेंसस

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

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

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

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

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

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

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

एक टी-रेज़िलिएंट अनाम सिंक्रोनाइज़ प्रोटोकॉल है जो बीजान्टिन जनरल समस्या को हल करता है,[10][11] अगर और कमजोर बीजान्टिन जनरलों का मामला[8] कहाँ विफलताओं की संख्या है और प्रक्रियाओं की संख्या है.

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

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

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

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

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

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

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

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

सोर्स सिंक्रोनाइज़ेशन प्रमाणीकरण थ्रेसहोल्ड स्थिति टिप्पणियाँ
पीज़-शोस्ताक-लामपोर्ट [10] सिंक्रोनाइज़ मौखिक कुल संचार
पीज़-शोस्ताक-लामपोर्ट [10] सिंक्रोनाइज़ लिखित कुल संचार
Ben-Or [19] असिंक्रोनाइज़ मौखिक
(एक्सपेक्ट)
एक्सपेक्ट rounds when
डोलेव.[20] सिंक्रोनाइज़ मौखिक कुल संचार
डोलेव-स्ट्रोंग [2] सिंक्रोनाइज़ लिखित कुल संचार
डोलेव-स्ट्रोंग [2] सिंक्रोनाइज़ लिखित कुल संचार
फेल्डमैन-मिकाली [21] सिंक्रोनाइज़ मौखिक
(एक्सपेक्ट)
काट्ज़-कू [22] सिंक्रोनाइज़ लिखित
(एक्सपेक्ट)
पीकेआई की आवश्यकता है।
पीबीएफटी [23] असिंक्रोनाइज़ (safety)
सिंक्रोनाइज़ (liveness)
मौखिक
हनीबजर [24] असिंक्रोनाइज़ मौखिक
(एक्सपेक्ट)
per tx communication - requires public-key encryption
अब्राहम[25] सिंक्रोनाइज़ लिखित
बीजान्टिन एग्रीमेन्ट ट्रिवियल [26][27] सिंक्रोनाइज़ हस्ताक्षर
(एक्सपेक्ट)
डिजिटल हस्ताक्षर की आवश्यकता है।


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

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

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

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

चरण 1: प्रत्येक सर्वर वैध उम्मीदवार लेनदेन की एक सूची संकलित करता है;
चरण 2: प्रत्येक सर्वर अपनी विशिष्ट नोड्स सूची (यूएनएल) से आने वाले सभी उम्मीदवारों को एकीकृत करता है और उनकी सत्यता पर वोट करता है;
चरण 3: न्यूनतम सीमा पार करने वाले लेनदेन को अगले दौर में भेज दिया जाता है;
चरण 4: अंतिम दौर में 80% कॉन्सेंसस की आवश्यकता है।[29]

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

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

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

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

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

कॉन्सेंसस
संख्या
ऑब्जेक्ट
एटॉमिक रीड/राइट पंजीकरण, म्युटेक्स
परीक्षण और समूह, स्वैप, फ़ेच और एडीडी, केयूए या स्टैक
... ...
n-पंजीकरण असाइनमेंट
... ...
कॉम्पेयर और स्वैप, लोड-लिंक/स्टोर,[38] मेमोरी से मेमोरी स्वैप, पीक ऑपरेशन के साथ केयूए, फ़ेच & कॉन, स्ट्रिक बाइट

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

यह भी देखें

संदर्भ

  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
  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.
  3. Gong, Li; Lincoln, Patrick; Rushby, John (1995). "Byzantine Agreement with authentication". Dependable Computing for Critical Applications. 10.
  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.
  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)
  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>
  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.
  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.
  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.
  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.
  21. Feldman, Pesech; Micali, Sylvio (1997). "An optimal probabilistic protocol for synchronous Byzantine agreement". SIAM Journal on Computing. 26 (4). doi:10.1137/S0097539790187084.
  22. Katz, Jonathan; Koo, Chiu-Yuen (2006). On Expected Constant-Round Protocols for Byzantine Agreement. CRYPTO 2006. doi:10.1007/11818175_27.
  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.
  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.
  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.
  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].
  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.


अग्रिम पठन