समय और विफलता मॉडल

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

Definition

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

Scope

यह विषय समकालिक (synchronous), अतुल्यकालिक (asynchronous), और आंशिक रूप से समकालिक (partially synchronous) समय मॉडल को शामिल करता है; क्रैश (fail-stop) से लेकर चूक (omission) और समय (timing) से लेकर मनमानी (Byzantine) त्रुटियों तक विफलताओं का वर्गीकरण; और विफलता डिटेक्टरों (failure detectors) का अमूर्तन जो अतुल्यकालिक प्रणालियों और टाइमआउट-आधारित तर्क को जोड़ता है। ये मॉडल वे अभिगृहीत हैं जिनसे संभावना और असंभवता दोनों परिणाम प्राप्त होते हैं।

Core questions

• विलंब और गति पर कौन सी सीमाएँ एक एल्गोरिथम मान सकता है, और टाइमआउट उन पर कैसे निर्भर करते हैं?
• कौन सी विफलता श्रेणियाँ—क्रैश, चूक, समय, बीजान्टिन—एक प्रोटोकॉल को मास्क करनी चाहिए?
• असंभवता परिणामों को दरकिनार करने के लिए अतुल्यकालिक प्रणालियों को विफलता डिटेक्टरों के साथ कैसे बढ़ाया जा सकता है?

Key theories

आंशिक समकालिकता

वास्तविक प्रणालियाँ न तो पूरी तरह से समकालिक होती हैं और न ही पूरी तरह से अतुल्यकालिक; आंशिक रूप से समकालिक मॉडल विलंब और गति पर ऐसी सीमाओं को मानता है जो अंततः मान्य होती हैं या अज्ञात होती हैं, जो यथार्थवादी रहते हुए सहमति को हल करने के लिए पर्याप्त है।

विफलता-मॉडल पदानुक्रम

विफलताएँ सौम्य फेल-स्टॉप क्रैश से लेकर, भेजने/प्राप्त करने की चूक और समय के उल्लंघन से लेकर मनमानी बीजान्टिन व्यवहार तक होती हैं; जिन विफलताओं को एक प्रोटोकॉल को सहन करना चाहिए, उनकी गंभीरता आवश्यक प्रतिकृति कारक और संदेश जटिलता को निर्धारित करती है।

अविश्वसनीय विफलता डिटेक्टर

एक अमूर्त विफलता डिटेक्टर इस बारे में संभावित रूप से गलत संकेत प्रदान करता है कि कौन सी प्रक्रियाएँ क्रैश हो गई हैं; सहमति को हल करने के लिए पर्याप्त सबसे कमजोर डिटेक्टर को चिह्नित करना अतुल्यकालिक कठोरता को व्यावहारिक टाइमआउट-आधारित कार्यान्वयन के साथ समेटता है।

Clinical relevance

उत्पादन प्रणालियाँ अंतर्निहित रूप से एक समय और विफलता मॉडल चुनती हैं जब भी वे टाइमआउट सेट करती हैं, एक प्रतिकृति कारक (replication factor) चुनती हैं, या यह तय करती हैं कि दुर्भावनापूर्ण प्रतिभागियों से बचाव करना है या नहीं; इन मान्यताओं को गलत समझना स्प्लिट-ब्रेन (split-brain) और डेटा-हानि की घटनाओं का एक सामान्य मूल कारण है।

History

अतुल्यकालिक मॉडल को दोष-सहिष्णु सहमति के लिए बहुत कमजोर दिखाए जाने के बाद, ड्वॉर्क, लिंच और स्टॉकमेयर ने 1988 में आंशिक समकालिकता (partial synchrony) की शुरुआत की, और चंद्र और टूग ने 1996 में अविश्वसनीय विफलता डिटेक्टरों (unreliable failure detectors) को औपचारिक रूप दिया, साथ में मॉडलिंग उपकरण प्रदान किए जो व्यावहारिक दोष-सहिष्णु समझौते को संभव बनाते हैं।

Debates

क्या टाइमआउट एक समय की धारणा है या एक विफलता डिटेक्टर?

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

Key figures

• Cynthia Dwork
• Nancy Lynch
• Larry Stockmeyer
• Tushar Chandra
• Sam Toueg

Seminal works

• dwork1988
• chandra1996
• lynch1996

Frequently asked questions

शुद्ध रूप से अतुल्यकालिक प्रणाली में विश्वसनीय विफलता का पता क्यों नहीं लगाया जा सकता है?

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