स्टेलर सर्वसम्मति प्रोटोकॉल को पहली बार 2015 में डेविड मजियर के एक वैज्ञानिक लेख में वर्णित किया गया था। यह एक "बीजान्टिन समझौते की संघीय प्रणाली" है, जो नेताओं के बिना विकेंद्रीकृत कंप्यूटिंग नेटवर्क को प्रभावी ढंग से किसी भी निर्णय पर आम सहमति तक पहुंचने की अनुमति देता है। तारकीय बिलिंग नेटवर्क सभी सदस्यों को एक सुसंगत लेनदेन इतिहास बनाए रखने के लिए तारकीय सहमति प्रोटोकॉल (SCP) का उपयोग करता है।

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

इस लेख में, हम संक्षेप में वर्णन करते हैं कि "समझौतों की प्रणाली" क्या है, यह "बीजान्टिन" क्या बना सकता है और बीजान्टिन प्रणाली को "संघीय" क्यों बना सकता है। फिर हम एससीपी लेख में वर्णित संघबद्ध मतदान प्रक्रिया की व्याख्या करते हैं, और अंत में स्वयं एससीपी प्रोटोकॉल की व्याख्या करते हैं।

समझौता प्रणाली

समझौतों की प्रणाली प्रतिभागियों के एक समूह को एक विषय पर आम सहमति में आने की अनुमति देती है, उदाहरण के लिए, दोपहर के भोजन के लिए क्या ऑर्डर करना है।

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

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

ऐसा लगता है कि समाधान सरल है: वोट करने के लिए! लेकिन यह एक भ्रामक धारणा है। मतपत्रों को कौन एकत्रित करेगा और परिणामों की रिपोर्ट करेगा? और बाकी लोगों को क्यों विश्वास करना चाहिए कि वह क्या कहता है? शायद हम पहले उस नेता को वोट दे सकते हैं जिस पर हम वोट का नेतृत्व करने के लिए भरोसा करते हैं - लेकिन इस पहले वोट का नेतृत्व कौन करेगा? क्या होगा यदि हम एक नेता पर सहमत नहीं हो सकते हैं? या अगर हम सहमत हैं, और यह नेता एक बैठक में फंस जाता है या बीमार छुट्टी के लिए छोड़ देता है?

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

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

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

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

एक व्यापक नेटवर्क में एकल नोड के संदर्भ में एक कोरम बनाना संभव नहीं लग सकता है, लेकिन यह संभव है। ऐसा कोरम विकेंद्रीकृत वोट के परिणामों की गारंटी भी दे सकता है। एससीपी श्वेत पत्र दिखाता है कि फ़ेडरेटेड वोटिंग नामक प्रक्रिया का उपयोग करके ऐसा कैसे किया जा सकता है।

अधीर के लिए

बाकी लेख में संघीय मतदान और स्टेलर सर्वसम्मति प्रोटोकॉल का विवरण है। यदि आप विवरण में रुचि नहीं रखते हैं, तो यहां प्रक्रिया का एक सामान्य अवलोकन है।

1. नोड्स "प्रत्याशियों" पर संघीय मतदान के दौर का संचालन करते हैं। संघीय मतदान के एक दौर का मतलब है:
   
   • किसी भी बयान के लिए नोड वोट, उदाहरण के लिए, "मैं वी के मूल्य का प्रस्ताव करता हूं";
     
   • नोड दावतों की आवाज़ों को सुनता है जब तक कि वह एक ऐसा न मिल जाए जो "प्राप्त" कर सकता है;
     
   • नोड इस कथन के लिए "कोरम" की तलाश कर रहा है। कोरम "नामित" की पुष्टि करता है।
2. जैसे ही एक नोड एक या अधिक प्रत्याशियों की पुष्टि कर सकता है, यह संघीय मतदान के कई दौरों के माध्यम से एक "मतपत्र" तैयार करने की कोशिश करता है।
   
3. जैसे ही नोड बैलट की तत्परता को सत्यापित करने में सक्षम होता है, वह फ़ेडरिंग वोटिंग के और भी दौरों के साथ इसे खिलाने की कोशिश करता है।
   
4. एक बार जब कोई साइट किसी समाचार पत्र की प्रतिबद्धता की पुष्टि कर सकती है, तो वह इस न्यूज़लेटर के मूल्य को "बाह्यकृत" कर सकती है, इसका उपयोग सर्वसम्मति के रूप में कर सकती है।

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

संघीय मत

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

कोरम और कोरम स्लाइस

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

कोरम का गठन एक कोरम में कटौती के साथ शुरू होता है। प्रत्येक नोड के लिए, इसके स्लाइस के नोड जोड़े जाते हैं। फिर, इन नोड्स के स्लाइसर सदस्यों को जोड़ा जाता है , और इसी तरह। जैसा कि आप जारी रखते हैं, अधिक से अधिक नोड्स आते हैं जिन्हें आप जोड़ नहीं सकते, क्योंकि वे पहले से ही स्लाइस में शामिल हैं। जब जोड़ने के लिए अधिक नए नोड नहीं होते हैं, तो प्रक्रिया बंद हो जाती है: हमने प्रारंभिक नोड के कोरम को काटकर "सकर्मक बंद" द्वारा एक कोरम का गठन किया।


इस नोड से कोरम खोजने के लिए ...


... इसके स्लाइस में सदस्यों को जोड़ें ...


... फिर इन नोड्स में स्लाइसर सदस्य जोड़ें।


तब तक जारी रखें जब तक जोड़ने के लिए कोई नोड्स न हों।




बाएँ जोड़ने के लिए कोई नोड नहीं। यह एक कोरम है।

वास्तव में, प्रत्येक नोड एक से अधिक स्लाइस में जा सकता है। कोरम बनाने के लिए, केवल एक स्लाइस का चयन करें और सदस्यों को जोड़ें; फिर प्रत्येक सदस्य के लिए कोई भी स्लाइस चुनें और सदस्यों को उस स्लाइस वगैरह में जोड़ें। इसका मतलब है कि प्रत्येक नोड कई संभावित कोरम का सदस्य है।


प्रत्येक चरण पर केवल एक कोरम टुकड़ा चुनें।






एक संभव कोरम। या एक विकल्प ...


... अन्य स्लाइस चुनें ...




... (जब संभव हो) ...


... एक और कोरम बनाता है।

एक नोड को कैसे पता चलता है कि अन्य नोड्स में क्या स्लाइस हैं? उसी तरह जैसे अन्य नोड्स के बारे में अन्य जानकारी: प्रसारण से जो प्रत्येक नोड नेटवर्क में प्रसारित होता है जब इसकी वोटिंग स्थिति बदल जाती है। प्रत्येक प्रसारण में भेजने वाले नोड के स्लाइस के बारे में जानकारी शामिल है। एससीपी तकनीकी दस्तावेज एक संचार तंत्र निर्दिष्ट नहीं करता है। कार्यान्वयन आमतौर पर पूरे नेटवर्क में प्रसारण संदेशों की गारंटी के लिए गपशप प्रोटोकॉल का उपयोग करते हैं ।

याद रखें कि समझौतों के गैर-संघीय बीजान्टिन प्रणाली में, एक कोरम को सभी नोड्स के बहुमत के रूप में परिभाषित किया गया है। समझौतों के बीजान्टिन प्रणाली को सवाल के दृष्टिकोण से विकसित किया गया था: सिस्टम कितने बेईमान नोड को सहन कर सकता है? एन नोड्स की एक प्रणाली में जिसे एफ विफलताओं (चाल) के साथ जीवित रहने के लिए डिज़ाइन किया गया है, नोड को एन - एफ साथियों से प्रतिक्रिया प्राप्त करके प्रगति करने में सक्षम होना चाहिए, क्योंकि उनमें से एफ कार्य नहीं कर सकता है। लेकिन N - f साथियों से एक प्रतिक्रिया प्राप्त करने के बाद, हम यह मान सकते हैं कि सभी f साथियों (जिनसे नोड को कोई प्रतिक्रिया नहीं मिली) वास्तव में ईमानदार हैं। इस प्रकार, एन - एफ साथियों से (जिसमें से एक प्रतिक्रिया प्राप्त होती है) दुर्भावनापूर्ण हैं। समान सहमति के लिए आने वाले नोड्स के लिए, शेष नोड्स का बहुमत ईमानदार होना चाहिए, अर्थात, हमें N - f की आवश्यकता 2 एफ या एन> 3 एफ से अधिक होनी चाहिए। इसलिए आमतौर पर f विफलताओं से बचने के लिए डिज़ाइन की गई प्रणाली में कुल N = 3f + 1 नोड्स और 2f + 1 का कोरम आकार होगा। जैसे ही प्रस्ताव कोरम की सीमा को पार करता है, बाकी नेटवर्क आश्वस्त हो जाता है कि कोई भी प्रतिस्पर्धी प्रस्ताव विफल हो जाएगा। इसलिए नेटवर्क परिणाम में परिवर्तित हो जाता है।

लेकिन समझौतों के एक संघीय बीजान्टिन प्रणाली में, न केवल एक बहुमत हो सकता है (क्योंकि कोई भी नेटवर्क के समग्र आकार को नहीं जानता है), लेकिन बहुमत की अवधारणा आम तौर पर बेकार है! यदि सिस्टम में सदस्यता खुली है, तो कोई केवल तथाकथित सिबिल हमले का संचालन करके बहुमत प्राप्त कर सकता है: बार-बार कई नोड्स के माध्यम से नेटवर्क में शामिल होने से। तो क्यों एक स्लाइस के सकर्मक बंद को कोरम कहा जा सकता है, और यह कैसे प्रतिस्पर्धी ऑफ़र को दबाने में सक्षम है?

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

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


यदि नेटवर्क में कोरम का अंतर है ...


... तो कोई भी दो कोरम आप बना सकते हैं ...


... हमेशा प्रतिच्छेदन करेगा।





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

यह उम्मीद करना अनुचित हो सकता है कि स्वतंत्र नोड के नेटवर्क में कोरम का एक विश्वसनीय चौराहा संभव है। लेकिन ऐसा होने के दो कारण हैं।

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

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

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

मतदान, स्वीकृति और पुष्टि

फ़ेडरेटेड वोटिंग के दौर में, नोड वैकल्पिक रूप से V के कुछ मान के लिए मतदान करना शुरू कर देता है। इसका मतलब है कि संदेश नेटवर्क को भेजा जाता है: "मैं नोड एन हूं, मेरे कोरम स्लाइस क्यू हैं, और मैं वी के लिए वोट करता हूं"। जब एक नोड इस तरह से वोट करता है, तो वह वादा करता है कि उसने कभी भी वी के खिलाफ वोट नहीं दिया और कभी नहीं होगा।

पीयर-टू-पीयर नोड्स से प्रसारण में, प्रत्येक नोड देखता है कि अन्य लोग कैसे वोट करते हैं। जैसे ही नोड पर्याप्त संख्या में ऐसे संदेश एकत्र करता है, यह कोरम स्लाइस को ट्रैक कर सकता है और कोरम खोजने की कोशिश कर सकता है। यदि वह सहकर्मियों का एक कोरम देखता है जो V को वोट देता है, तो वह V को स्वीकार करने के लिए आगे बढ़ सकता है और इस नए संदेश को नेटवर्क पर प्रसारित कर सकता है: "मैं नोड N हूं, मेरे स्लाइस कोरम Q हैं, और मैं V को स्वीकार करता हूं"। स्वीकृति एक साधारण वोट की तुलना में एक मजबूत गारंटी प्रदान करती है। जब कोई नोड V के लिए वोट करता है, तो वह अन्य विकल्पों के लिए कभी भी वोट नहीं कर सकता है। लेकिन अगर कोई नोड V को स्वीकार करता है, तो वेब पर कोई नोड कभी भी अन्य विकल्प को स्वीकार नहीं करेगा (तकनीकी श्वेत पत्र SCP में प्रमेय 8 यह सिद्ध करता है)।

बेशक, यह बहुत संभावना है कि तुरंत नोड्स का एक कोरम नहीं होगा जो वी के साथ सहमत हैं। अन्य नोड अन्य मूल्यों के लिए वोट कर सकते हैं। लेकिन साइट के लिए सरल मतदान से स्वीकृति तक जाने का एक और तरीका है। N W, , . , W. — N. , . W, ( 8) , , N W.


N .


BDF — N: N.


BE N, E N.

— . N, , N. — . N , , . , , SCP ( 11), , N .


.

, . Stellar .

तारकीय सहमति प्रोटोकॉल

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

वर्णित फ़ेडरेटेड मतदान प्रक्रिया इस अर्थ में सुरक्षित है कि यदि कोई नोड V के मान की पुष्टि करता है, तो कोई भी नोड दूसरे मान की पुष्टि नहीं करता है। लेकिन "दूसरे अर्थ की पुष्टि नहीं करता है" - इसका मतलब यह नहीं है कि वह आवश्यक रूप से कुछ की पुष्टि करेगा। प्रतिभागी इतने भिन्न मूल्यों के लिए मतदान कर सकते हैं कि कुछ भी स्वीकृति की सीमा तक नहीं पहुंचता है। इसका मतलब है कि कोई संघीय वोट नहीं है। .

Stellar , , . ( SCP . , , , ). , , , SCP, .

, SCP , , - , , , . .

(nomination phase), « V», , V. — , .

SCP , , ( ) , (commit). , . , . — , , — .

.

नामांकन चरण की शुरुआत में, प्रत्येक नोड अनायास मूल्य V का चयन कर सकता है और बयान के लिए वोट कर सकता है "मैं V नामांकित कर रहा हूं"। इस स्तर पर लक्ष्य एक संघीय वोट के माध्यम से एक निश्चित मूल्य के नामांकन की पुष्टि करना है।

, , . , «» . (echo) , V, , W, V, W. ( , . SCP . , «» , . , , , . , , ).

वैचारिक रूप से, वी और डब्ल्यू दोनों के समानांतर नामांकन अलग-अलग संघीय वोट हैं, प्रत्येक अलग से स्वीकृति या पुष्टि प्राप्त करने में सक्षम हैं। व्यवहार में, एससीपी प्रोटोकॉल संदेश इन व्यक्तिगत आवाजों को एक साथ पैक करते हैं।

हालांकि नामांकन V के लिए मतदान, नामांकन V के विरुद्ध कभी भी वोट नहीं देने का वादा है, इस स्तर पर - इस मामले में, एससीपी - इसे परिभाषित किया जाता है जिसका अर्थ "विरुद्ध" है। एससीपी एक बयान नहीं देखता है जो "मैं एक्स नामित कर रहा हूं" वोट का विरोधाभास है, अर्थात, "मैं नामांकन एक्स के खिलाफ नहीं हूं" संदेश है, इसलिए नोड किसी भी मूल्य को नामित करने के लिए वोट कर सकता है। इनमें से कई नामांकन से कुछ नहीं होगा, लेकिन अंत में, नोड एक या अधिक मूल्यों को स्वीकार या पुष्टि करने में सक्षम होगा। एक बार उम्मीदवार की पुष्टि हो जाने के बाद, वह एक उम्मीदवार बन जाता है ।


फ़ेडरेटेड वोटिंग का उपयोग करके एससीपी को नामांकित करना। साथियों द्वारा धकेल दिए गए कई "बी" मूल्य हो सकते हैं और सहकर्मी द्वारा परिलक्षित होते हैं।

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

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

लेकिन यह सामान्य है। नामांकन की तैयारी है। मुख्य बात यह है कि मतदान प्रक्रिया के दौरान होने वाली आम सहमति प्राप्त करने के लिए उम्मीदवारों की संख्या को सीमित करना ।

मतदान

समाचार पत्र <काउंटर, मान> की एक जोड़ी है, जहां काउंटर एक पूर्णांक है जो 1 से शुरू होता है, और मान नामांकित चरण से एक उम्मीदवार है। यह नोड का अपना उम्मीदवार या उस नोड द्वारा अपनाए गए पड़ोसी उम्मीदवार हो सकता है। मोटे तौर पर, रन के दौरान, बार-बार मतपत्रों पर संभावित रूप से कई संघीय वोटों को पकड़कर किसी मतपत्र पर किसी उम्मीदवार पर आम सहमति तक पहुंचने के लिए नेटवर्क को मजबूर करने का प्रयास किया जाता है। मतपत्रों में काउंटर किए गए प्रयासों पर नज़र रखते हैं, और उच्च काउंटरों वाले मतपत्र कम काउंटरों वाले मतपत्रों पर वरीयता लेते हैं। यदि मतपत्र <काउंटर, मूल्य> अटक गया है, तो एक नया वोट शुरू होता है, अब मतपत्र <काउंटर + 1, मूल्य> पर। मूल्यों के

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

• "मैं बुलेटिन बी करने के लिए तैयार हूं" और
  
• "मैं बुलेटिन बी के लिए एक प्रतिबद्धता की घोषणा"

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

यद्यपि वैचारिक रूप से कई फेडरेटेड वोट कई अलग-अलग मतपत्रों के लिए अनुप्रयोगों पर आयोजित किए जाते हैं, वे कई संदेशों का आदान-प्रदान नहीं करते हैं क्योंकि प्रत्येक संदेश कई मतपत्रों को कूटबद्ध करता है। एक संदेश, इस प्रकार, एक साथ कई संघटित वोटों की स्थिति को बढ़ावा देता है, उदाहरण के लिए: "मैं <min, V> से <max, V>" तक की सीमा में बैलट कमीशन स्वीकार करता हूं।

"तैयार" और "प्रतिबद्ध" शब्द का क्या अर्थ है?

एक नोड वोट करने के लिए एक नोड वोट करता है जब यह आश्वस्त हो जाता है कि अन्य नोड विभिन्न मूल्यों के साथ मतपत्र नहीं करेंगे। इसे समझाने का उद्देश्य बयान तैयार करना है। एक वोट जो कहता है कि "मैं बुलेटिन बी करने के लिए तैयार हूं" एक वादा है कि बी से कम बुलेटिन कभी न करें, यानी कम काउंटर (एससीपी के लिए आवश्यक है कि बुलेटिन में मूल्यों का एक निश्चित क्रम हो। इस प्रकार) बुलेटिन <N1, V1> <N2, V2> से कम है अगर N1 <N2, और अगर N1 = N2 और V1 <V2) भी। इन छोटे मतपत्रों को प्रारंभिक वोट के दौरान "निरस्त" किया जाता है, जबकि बी को "तैयार" माना जाता है।

"मैं बुलेटिन बी करने के लिए तैयार क्यों हूँ" का अर्थ है "मैं कभी भी बी से कम मतपत्रों का वादा नहीं करता" क्योंकि एससीपी प्रतिबद्ध के विपरीत गर्भपात को परिभाषित करता है। एक मतपत्र की तैयारी के लिए मतदान का अर्थ कुछ अन्य मतपत्रों को रद्द करने के लिए मतदान करना भी है, और, जैसा कि हमने पहले चर्चा की थी, एक बात के लिए मतदान करना इसके विरुद्ध कभी मत न करने का वादा है।

प्रतिबद्ध प्रसारित करने से पहले, साइट को पहले बुलेटिन ढूंढना होगा, जिसे वह तैयार किए जाने की पुष्टि कर सकता है। दूसरे शब्दों में, वह "मैं बुलेटिन बी के लिए प्रतिबद्ध हूं," कई अलग-अलग मतपत्रों के लिए संघीय मत रखता है, जब तक कि वह एक को नहीं पाता जो कि कोरम स्वीकार करता है।

मतदान के लिए मतपत्र कहां से आते हैं? सबसे पहले, नोड <1, सी> के लिए मतदान की तैयारी प्रसारित करता है, जहां सी नामांकन चरण में उत्पादित समग्र उम्मीदवार है। हालांकि, मतदान की तैयारी शुरू होने के बाद भी, नामांकन से अतिरिक्त उम्मीदवारों की उपस्थिति हो सकती है जो नए मतपत्र बन जाएंगे। इस बीच, साथियों के पास अलग-अलग उम्मीदवार हो सकते हैं, और वे एक अवरुद्ध सेट बना सकते हैं जो "मैं बी 2 बुलेटिन के लिए तैयार हूं" स्वीकार करता है, जो नोड को भी स्वीकार करने के लिए मनाएगा। अंत में, एक टाइमआउट तंत्र है जो वर्तमान मतपत्रों के अटक जाने पर नए मतपत्रों पर नए मतपत्रों पर फ़ेडरेटेड वोटिंग के नए दौर उत्पन्न करता है।

जैसे ही नोड बुलेटिन बी पाता है, जिसे वह तैयार के रूप में पुष्टि कर सकता है, यह एक नया संदेश प्रसारित करता है, "बुलेटिन बी कमिट"। यह वोट साथियों को बताता है कि नोड कभी भी बी को नहीं देगा। यदि बी एक मतपत्र है <n, C>, तो "प्रतिबद्ध बुलेटिन <एन, सी>" का अर्थ है कि प्रत्येक मतपत्र की तत्परता के लिए वोट देने के लिए बिना शर्त सहमति, C> से <>, s>। यह अतिरिक्त मान अन्य नोड्स को एक कमिट के साथ पकड़ने में मदद करता है, अगर वे अभी भी प्रोटोकॉल के पहले चरण में हैं।

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

यदि संदेश "मैं एक प्रतिबद्ध घोषित करता हूं <N, C>" स्वीकार या पुष्टि नहीं की जा सकती है, अर्थात, संदेश की स्वीकृति या पुष्टि की संभावना <N + 1, C> या <N + 2, C> - या, किसी भी मामले में, कोई भी बुलेटिन C के मान के साथ, और किसी अन्य के साथ नहीं, क्योंकि नोड ने पहले ही वादा किया था कि कभी भी रद्द नहीं किया जाएगा <N, C>। जब तक नोड प्रतिबद्ध के लिए वोट प्रसारित करता है, तब तक यह C या कुछ भी नहीं होगा, यह इस बात पर निर्भर करता है कि सर्वसम्मति कितनी दूर है। हालाँकि, यह नोड सी को बाहरी करने के लिए पर्याप्त नहीं है। कुछ बीजान्टिन दावतें (एक कोरम से कम, सुरक्षा के बारे में हमारी धारणाओं के आधार पर) नोड पर झूठ हो सकती हैं। गोद लेने और फिर एक निश्चित मतपत्र (या मतपत्रों की सीमा) की पुष्टि होती है जो नोड को अंत में सी को बाहरी बनाने का विश्वास दिलाता है।


महासंघ मतदान के माध्यम से चल रहे एस.सी.पी. नहीं दिखाया गया है: किसी भी समय एक टाइमर काम कर सकता है, मतपत्र में काउंटर बढ़ाता है (और, संभवतः, अतिरिक्त नामांकित उम्मीदवारों से एक नया संमिश्र का उत्पादन करता है)।

और वह सब है! एक बार जब नेटवर्क आम सहमति पर पहुंच जाता है, तो वह इसे बार-बार करने के लिए तैयार होता है। स्टेलर बिलिंग नेटवर्क पर, यह लगभग हर 5 सेकंड में होता है: एक ऐसा करतब जिसमें SCP द्वारा गारंटीकृत सुरक्षा और उत्तरजीविता दोनों की आवश्यकता होती है।

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

आगे पढ़ रहे हैं

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