वितरित सहमति
वितरित सहमति प्रक्रियाओं के एक समूह को संदेश विलंब और प्रक्रिया विफलताओं के बावजूद एक ही मान पर सहमत होने की समस्या है, और यह दोष-सहिष्णु कंप्यूटिंग का केंद्रीय अमूर्त है।
Definition
सहमति के लिए आवश्यक है कि प्रत्येक गैर-दोषपूर्ण प्रक्रिया, प्रस्तावित इनपुट से शुरू होकर, अंततः एक आउटपुट मान पर निर्णय लेती है ताकि सभी गैर-दोषपूर्ण प्रक्रियाएं एक ही मान पर निर्णय लें (समझौता), मान किसी प्रक्रिया द्वारा प्रस्तावित किया गया था (वैधता), और प्रत्येक गैर-दोषपूर्ण प्रक्रिया अंततः निर्णय लेती है (समाप्ति)।
Scope
यह विषय सहमति के औपचारिक विनिर्देश (समझौता, वैधता, अखंडता और समाप्ति), FLP असंभवता प्रमेय और इसे दरकिनार करने के तरीके—आंशिक तुल्यकालन, अविश्वसनीय विफलता डिटेक्टर, और यादृच्छिकीकरण—और परमाणु प्रसारण और प्रतिकृति राज्य मशीनों के साथ सहमति की समानता को शामिल करता है। यह क्रैश-विफलता सेटिंग का इलाज करता है; बीजान्टिन सेटिंग को एक सहोदर विषय में माना जाता है।
Core questions
- एक सही सहमति एल्गोरिथम होने के लिए एक प्रोटोकॉल को वास्तव में क्या गारंटी देनी चाहिए?
- एक भी क्रैश के साथ नियतात्मक अतुल्यकालिक सहमति असंभव क्यों है?
- कौन सी अतिरिक्त धारणाएँ—तुल्यकालन, विफलता डिटेक्टर, यादृच्छिकता—समाधानशीलता को बहाल करती हैं?
Key theories
- FLP असंभवता
- कोई भी नियतात्मक प्रोटोकॉल एक अतुल्यकालिक संदेश-पासिंग प्रणाली में सहमति को हल नहीं करता है यदि एक भी प्रक्रिया क्रैश हो सकती है, क्योंकि प्रत्येक प्रोटोकॉल में एक निष्पादन होता है जिसे बिना निर्णय लिए हमेशा के लिए चलाने के लिए निर्देशित किया जा सकता है।
- विफलता-डिटेक्टर दृष्टिकोण
- एक अविश्वसनीय विफलता डिटेक्टर के साथ एक अतुल्यकालिक प्रणाली को बढ़ाना जो अंततः सटीक है, सहमति की समाधानशीलता को बहाल करता है, और सबसे कमजोर ऐसा डिटेक्टर जो पर्याप्त है, उसे सटीक रूप से चित्रित किया गया है।
- यादृच्छिक सहमति
- प्रक्रियाओं को सिक्के उछालने की अनुमति देने से पूरी तरह से अतुल्यकालिक प्रणाली में भी एक की संभावना के साथ सहमति समाप्त हो जाती है, FLP बाधा से बचने के लिए नियतात्मक समाप्ति को संभाव्य समाप्ति के लिए व्यापार करना।
Clinical relevance
प्रत्येक दृढ़ता से सुसंगत वितरित प्रणाली—प्रतिकृति लॉग, समन्वय सेवाएं, कॉन्फ़िगरेशन स्टोर—आंतरिक रूप से सहमति को हल करती है, इसलिए यहां स्थापित गारंटी और सीमाएं सीधे यह निर्धारित करती हैं कि ऐसी प्रणालियां संगति और उपलब्धता के बारे में क्या वादा कर सकती हैं।
History
1985 के FLP प्रमेय ने मौलिक असंभवता स्थापित की; बेन-ओर के 1983 के यादृच्छिक प्रोटोकॉल और चंद्र और टूएग के 1996 के विफलता-डिटेक्टर फ्रेमवर्क ने तब सहमति को हल करने योग्य बनाने के दो पूरक तरीके दिखाए, जिसने अगले दशकों के लिए अनुसंधान एजेंडा को परिभाषित किया।
Key figures
- Michael Fischer
- Nancy Lynch
- Michael Paterson
- Tushar Chandra
- Sam Toueg
- Michael Ben-Or
Related topics
Seminal works
- fischer1985
- chandra1996
- ben-or1983
Frequently asked questions
- यदि सहमति असंभव है, तो वास्तविक प्रणालियाँ इसे कैसे प्राप्त करती हैं?
- असंभवता केवल एक नियतात्मक प्रोटोकॉल पर लागू होती है जिसे पूरी तरह से अतुल्यकालिक मॉडल में हमेशा समाप्त होना चाहिए। वास्तविक प्रणालियाँ सुरक्षा को बिना शर्त रखती हैं और समाप्ति के लिए अंततः तुल्यकालन या यादृच्छिकता पर निर्भर करती हैं, इसलिए वे कभी भी समझौते का उल्लंघन नहीं करती हैं और जब भी नेटवर्क अच्छी तरह से व्यवहार करता है तो प्रगति करती हैं।