सर्वसम्मति और समन्वय

सर्वसम्मति और समन्वय इस बात पर ध्यान केंद्रित करते हैं कि कैसे स्वतंत्र प्रक्रियाएँ, जो केवल संदेशों के माध्यम से संचार करती हैं, देरी और विफलताओं के बावजूद एक सामान्य मूल्य या कार्रवाई पर सहमत हो सकती हैं।

Definition

सर्वसम्मति प्रक्रियाओं के एक समूह की समस्या है, जिनमें से प्रत्येक एक मूल्य प्रस्तावित करती है, सभी एक ही सामान्य मूल्य पर निर्णय लेते हैं ताकि निर्णय वैध हो, सभी सही प्रक्रियाएँ सहमत हों, और प्रत्येक सही प्रक्रिया अंततः निर्णय ले, भले ही कुछ प्रक्रियाएँ विफल हो जाएँ।

Scope

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

Sub-topics

• बीजान्टिन फॉल्ट टॉलरेंस
• वितरित सहमति
• वितरित पारस्परिक अपवर्जन और लीडर चुनाव
• पैक्सोस और राफ्ट

Core questions

• किन समय और विफलता मॉडलों के तहत सर्वसम्मति हल करने योग्य है, और कब यह सिद्ध रूप से असंभव है?
• व्यावहारिक प्रोटोकॉल सुरक्षा बनाए रखते हुए FLP असंभवता को कैसे दरकिनार करते हैं?
• क्रैश (crash) बनाम बीजान्टिन (Byzantine) विफलताओं को सहन करने के लिए कितनी प्रतिकृति की आवश्यकता है?
• प्रक्रियाएँ साझा संसाधनों तक पहुँच का समन्वय कैसे कर सकती हैं या विश्वसनीय रूप से एक नेता का चुनाव कैसे कर सकती हैं?

Key theories

FLP असंभवता

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

कोरम-आधारित सर्वसम्मति

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

बीजान्टिन समझौता सीमाएँ

जब f तक प्रक्रियाएँ मनमाने ढंग से व्यवहार कर सकती हैं, तो समझौते तक पहुँचने के लिए शास्त्रीय तुल्यकालिक सेटिंग में कम से कम 3f+1 प्रक्रियाओं की आवश्यकता होती है, एक सख्त सीमा जो सभी बीजान्टिन दोष-सहिष्णु प्रणालियों के डिजाइन को आकार देती है।

Clinical relevance

सर्वसम्मति विश्वसनीय बुनियादी ढाँचे की रीढ़ है: समन्वय सेवाएँ, प्रतिकृति डेटाबेस, वितरित ताले (distributed locks), और ब्लॉकचेन सभी प्रतिकृतियों को सुसंगत रखने के लिए एक सर्वसम्मति प्रोटोकॉल चलाते हैं, जिससे यह क्षेत्र आधुनिक क्लाउड प्रणालियों की स्थायित्व और उपलब्धता की गारंटी के लिए सीधे तौर पर जिम्मेदार है।

History

1982 के बीजान्टिन जनरलों के पेपर और 1985 के FLP असंभवता परिणाम ने समझौते की सीमाओं को निर्धारित किया; लैम्पॉर्ट के पैक्सोस (Paxos) (1989 में प्रसारित, 1998 में प्रकाशित) ने एक व्यावहारिक अतुल्यकालिक-सुरक्षित प्रोटोकॉल दिया, और बीजान्टिन दोष सहिष्णुता और राफ्ट (Raft) पर बाद के काम ने सर्वसम्मति को दुर्भावनापूर्ण दोषों के खिलाफ मजबूत और कार्यान्वयनकर्ताओं के लिए सुलभ दोनों बना दिया।

Debates

क्या FLP असंभवता सर्वसम्मति को व्यवहार में अप्राप्य बनाती है?

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

Key figures

• Leslie Lamport
• Nancy Lynch
• Michael Fischer
• Michael Paterson
• Barbara Liskov

Seminal works

• fischer1985
• lamport1998
• lamport1982byz

Frequently asked questions

वितरित प्रणालियों में सर्वसम्मति को सबसे कठिन समस्या क्यों माना जाता है?

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

सर्वसम्मति प्रतिकृति डेटाबेस से कैसे संबंधित है?

एक प्रतिकृति डेटाबेस संचालन के क्रम पर सहमत होकर अपनी प्रतिकृतियों को सुसंगत रखता है, जो ठीक सर्वसम्मति निर्णयों का एक क्रम है; यही कारण है कि वितरित कुंजी-मूल्य स्टोर (distributed key-value stores) जैसी प्रणालियाँ अपने मूल में एक सर्वसम्मति प्रोटोकॉल को एम्बेड करती हैं।