स्व-स्थिरीकरण

From Vigyanwiki

स्व-स्थिरीकरण वितरित प्रणालियों में दोष-सहिष्णुता की अवधारणा है। किसी भी प्रारंभिक स्थिति को देखते हुए, एक स्व-स्थिरीकरण वितरित प्रणाली निष्पादन चरणों की एक परिमित संख्या में सही स्थिति समाप्त हो जाएगी।

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

1974 में एड्सगर डिजस्ट्रा के मौलिक पेपर के कई साल बाद, यह अवधारणा महत्वपूर्ण बनी हुई है क्योंकि यह स्व-प्रबंधन कंप्यूटर सिस्टम और दोष-सहिष्णु प्रणालियों के लिए एक महत्वपूर्ण नींव प्रस्तुत करती है। नतीजतन, डिजस्ट्रा के पेपर ने 2002 ACM PODC प्रभावशाली-पेपर अवार्ड प्राप्त किया, जो वितरित कंप्यूटिंग समुदाय में सर्वोच्च मान्यताओं में से एक है।[1] इसके अलावा, डिजस्ट्रा की मृत्यु के बाद, पुरस्कार का नाम बदल दिया गया और अब इसे डिजस्ट्रा अवार्ड कहा जाता है।

इतिहास

1974 में ई.डब्ल्यू. डिजस्ट्रा ने इस क्षेत्र में आगे के शोध को प्रेरित करते हुए ,आत्म-स्थिरीकरण की अवधारणा को प्रस्तुत किया। [2] उनके प्रदर्शन में स्व-स्थिर करने वाले आपसी बहिष्करण एल्गोरिदम की प्रस्तुति शामिल थी।[3] इसने पहला आत्म-स्थिरता (सेल्फ-स्टेबलाइजिंग) एल्गोरिदम भी दिखाया जो सिस्टम पर मजबूत मान्यताओं पर भरोसा नहीं करता था। व्यवहार में उपयोग किए जाने वाले कुछ पिछले प्रोटोकॉल वास्तव में स्थिर हो गए थे, लेकिन केवल एक घड़ी के अस्तित्व को मानते हुए जो सिस्टम के लिए वैश्विक था, और प्रत्येक प्रणाली संक्रमण की अवधि पर एक ज्ञात ऊपरी सीमा को मानता था।bयह केवल दस साल बाद था जब लेस्ली लामपोर्ट ने 1983 के सम्मोहक के एक सम्मेलन में डायज्क्स्ट्रा के काम के महत्व को इंगित किया, जो कि डिस्ट्रिब्यूटेड कंप्यूटिंग के सिद्धांतों पर संगोष्ठी नामक शोधकर्ता थे। इस सुरुचिपूर्ण गलती-सहिष्णुता अवधारणा पर अपना ध्यान केंद्रित किया। अपनी बात में, लैमपोर्ट ने कहा:

मैं इसे डिजस्ट्रा के सबसे शानदार काम के रूप में मानता हूं- उनका यह सबसे शानदार प्रकाशित पेपर है। ज़ो लगभग पूरी तरह से अज्ञात है। मैं इसे गलती सहिष्णुता पर काम में एक मील का पत्थर मानता हूं.......मैं आत्म-स्थिरीकरण को गलती सहिष्णुता में एक बहुत ही महत्वपूर्ण अवधारणा मानता हूं और यह अनुसंधान के लिए एक बहुत ही उपजाऊ क्षेत्र है।[3]

बाद में, डिजस्ट्रा के काम को ACM-PODC प्रभावशाली पेपर अवार्ड से सम्मानित किया गया, जो तब वार्षिक ACM-PODC संगोष्ठी में दिए गए वितरित कंप्यूटिंग में ACM (द एसोसिएशन फॉर कम्प्यूटिंग मशीनरी) डिजस्ट्रा पुरस्कार बन गया।[4]

अवलोकन

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

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

  • इस नेटवर्क में प्रत्येक कंप्यूटर के लिए एक टोकन न पकड़ना एक सही स्थिति है, क्योंकि टोकन को दूसरे कंप्यूटर द्वारा आयोजित किया जा सकता है। हालाँकि, यदि प्रत्येक कंप्यूटर टोकन नहीं रखने की स्थिति में है, तो नेटवर्क पूरी तरह से सही स्थिति में नहीं है।
  • इसी तरह, यदि एक से अधिक कंप्यूटर एक टोकन रखते हैं, तो यह नेटवर्क के लिए एक सही स्थिति नहीं है, हालांकि यह किसी भी कंप्यूटर को व्यक्तिगत रूप से देखकर गलत नहीं देखा जा सकता है। चूंकि प्रत्येक कंप्यूटर केवल अपने दो पड़ोसियों के स्थितिों का निरीक्षण कर सकता है, इसलिए कंप्यूटर के लिए यह तय करना कठिन है कि नेटवर्क पूरी तरह से सही स्थिति में है या नहीं।

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

दक्षता में सुधार

हाल ही में, शोधकर्ताओं ने स्थानीय जाँच का उपयोग करके स्व-स्थिरीकरण प्रणालियों के लिए प्रकाश-वजन त्रुटि का पता लगाने के लिए नए तरीके प्रस्तुत किए हैं।[7][8] और सामान्य कार्यों के लिए।[9] स्थानीय शब्द कंप्यूटर नेटवर्क के एक हिस्से को संदर्भित करता है। जब स्थानीय पहचान का उपयोग किया जाता है, तो एक नेटवर्क में एक कंप्यूटर को एक त्रुटि का पता लगाने के लिए पूरे नेटवर्क के साथ संवाद करने की आवश्यकता नहीं होती है; प्रत्येक कंप्यूटर को केवल अपने निकटतम पड़ोसियों के साथ संवाद करने से त्रुटि का पता लगाया जा सकता है। इन स्थानीय डिटेक्शन विधियों नेआत्म-स्थिरता (सेल्फ-स्टेबलाइज़िंग) एल्गोरिदम को काफी हद तक डिजाइन करने के कार्य को सरल बनाया। ऐसा इसलिए है क्योंकि त्रुटि का पता लगाने वाले तंत्र और वसूली तंत्र को अलग से डिज़ाइन किया जा सकता है। इन पहचान विधियों के आधार पर नए एल्गोरिदम भी बहुत अधिक कुशल हो गए। इसके अलावा, इन पत्रों ने गैर-स्व -स्थिर एल्गोरिदम को बदलने के लिए कुशल सामान्य ट्रांसफार्मर का सुझाव दिया, ताकि वे स्वयं स्थिर हो सकें। विचार यह है कि

  1. एक ही समय में गैर स्व स्थिर प्रोटोकॉल चलाएं,
  2. उपर्युक्त पता लगाने के तरीकों का उपयोग करके दोषों का पता लगाएं (दिए गए प्रोटोकॉल के निष्पादन के दौरान),
  3. फिर, प्रणाली को कुछ पूर्व निर्धारित प्रारंभिक स्थिति में वापस करने के लिए एक (सेल्फ स्टैबलाइजिंग) रीसेट प्रोटोकॉल लागू करें, और अंत में,
  4. दिए गए (गैर-स्व स्थिर) प्रोटोकॉल को पुनरारंभ करें।

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

स्व-स्थिरीकरण एल्गोरिदम की एक उपयोगी संपत्ति यह है कि वे परतों से बने हो सकते हैं यदि परतें किसी भी परिपत्र निर्भरता को प्रदर्शित नहीं करती हैं। रचना का स्थिरीकरण समय तब प्रत्येक परत के व्यक्तिगत स्थिरीकरण समय के योग से घिरा होता है।[5] डिजस्ट्रा के काम के लिए नए दृष्टिकोण बाद में उभरे जैसे कि Krzysztof Apt और Ehsan Shoja के प्रस्ताव के मामले में, जिसमें दिखाया गया कि कैसे स्व-स्थिरीकरण को रणनीतिक खेलों की मानक अवधारणाओं का उपयोग करके स्वाभाविक रूप से तैयार किया जा सकता है, विशेष रूप से एक सुधार पथ की अवधारणा। [13] इस विशेष कार्य ने स्व-स्थिरीकरण और खेल सिद्धांत के बीच कड़ी को प्रदर्शित करने की मांग की।

समय जटिलता

एक स्व-स्थिरीकरण एल्गोरिथ्म की समय जटिलता को (एसिंक्रोनस) दौर या चक्रों में मापा जाता है।

  • एक दौर सबसे छोटा निष्पादन अनुरेख (ट्रेस) है जिसमें प्रत्येक प्रोसेसर कम से कम एक कदम निष्पादित करता है।
  • इसी तरह, एक चक्र सबसे छोटा निष्पादन अनुरेख (ट्रेस ) है जिसमें प्रत्येक प्रोसेसर कम से कम एक पूर्ण पुनरावृत्ति को कम से कम निष्पादित सूची की सूची में निष्पादित करता है।

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

परिभाषा

एक प्रणाली आत्म-स्थिर है अगर और केवल अगर:

  1. किसी भी स्थिति से शुरू होकर, यह गारंटी दी जाती है कि सिस्टम अंततः एक सही स्थिति तक पहुंच जाएगा (अभिसरण)।
  2. यह देखते हुए कि प्रणाली एक सही स्थिति में है, यह एक सही स्थिति में रहने की गारंटी है, बशर्ते कि कोई गलती न हो (समापन)।

एक प्रणाली को यादृच्छिक रूप से आत्म-स्थिरीकरण कहा जाता है यदि और केवल अगर यह स्व-स्थिर है और एक सही स्थिति तक पहुंचने के लिए आवश्यक राउंड की अपेक्षित संख्या कुछ स्थिरांक से बंधी है .[14] उपर्युक्त अर्थों में स्व-स्थिरीकरण का डिजाइन एक कठिन काम के रूप में जाना जाता है। वास्तव में, वितरित एल्गोरिदम के एक वर्ग में स्थानीय जाँच की संपत्ति नहीं होती है: नेटवर्क स्थिति की वैधता का मूल्यांकन एक ही प्रक्रिया द्वारा नहीं किया जा सकता है। सबसे स्पष्ट मामला डिजस्ट्रा के टोकन-रिंग को ऊपर परिभाषित किया गया है: कोई भी प्रक्रिया यह पता नहीं लगा सकती है कि नेटवर्क स्थिति वैध है या नहीं उस मामले में जहां एक से अधिक टोकन गैर-पड़ोसी प्रक्रियाओं में मौजूद है। इससे पता चलता है कि एक वितरित प्रणाली का स्व-स्थिरीकरण एक प्रकार की सामूहिक बुद्धिमत्ता है जहां प्रत्येक घटक अपने स्थानीय ज्ञान के आधार पर स्थानीय कार्रवाई कर रहा है, लेकिन अंततः यह अंत में वैश्विक अभिसरण की गारंटी देता है।

ऊपर परिभाषित स्व-स्थिरीकरण को डिजाइन करने की कठिनाई को दूर करने में मदद करने के लिए, अन्य प्रकार के स्थिरीकरण को तैयार किया गया था। उदाहरण के लिए, कमजोर स्थिरीकरण वह संपत्ति है जो एक वितरित प्रणाली में हर संभव स्थिति से अपने वैध व्यवहार तक पहुंचने की संभावना है।[15] कमजोर स्थिरीकरण डिजाइन करना आसान है क्योंकि यह सिर्फ हर रन के लिए अभिसरण के बजाय वितरित प्रणाली के कुछ रनों के लिए अभिसरण की संभावना की गारंटी देता है।

एक स्व-स्थिरीकरण एल्गोरिथ्म चुप है अगर और केवल अगर यह एक वैश्विक स्थिति में परिवर्तित हो जाता है जहां एल्गोरिथ्म द्वारा उपयोग किए जाने वाले संचार रजिस्टरों के मूल्य निश्चित रहते हैं।[16]

संबंधित कार्य

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

संदर्भ

  1. ↑ "PODC Influential Paper Award: 2002", ACM Symposium on Principles of Distributed Computing, retrieved 2009-09-01
  2. ↑ Dijkstra, Edsger W. (1974), "Self-stabilizing systems in spite of distributed control" (PDF), Communications of the ACM, 17 (11): 643–644, doi:10.1145/361179.361202.
  3. ↑ 3.0 3.1 Dolev, Shlomi (2000). Self-stabilization. Cambridge, MA: The MIT Press. p. 3. ISBN 978-0262041782.
  4. ↑ 4.0 4.1 4.2 Chaudhuri, Soma; Das, Samir; Paul, Himadri; Tirthapura, Srikanta (2007). Distributed Computing and Networking: 8th International Conference, ICDCN 2006, Guwahati, India, December 27-30, 2006, Proceedings. Berlin: Springer. p. 108. ISBN 978-3540681397.
  5. ↑ 5.0 5.1 5.2 Shlomi Dolev, Shlomo Moran, Amos Israeli: Self-Stabilization of Dynamic Systems Assuming only Read/Write Atomicity. Distributed Computing, volume 7, pages3–16(1993).
  6. ↑ Katz, Shmuel; Perry, Kenneth J. (1993), "Self-stabilizing extensions for meassage-passing systems", Distributed Computing, 7 (1): 17–26, doi:10.1007/BF02278852.
  7. ↑ 7.0 7.1 Awerbuch, Baruch; Patt-Shamir, Boaz; Varghese, George (1991), "Self-stabilization by local checking and correction", Proc. 32nd Symposium on Foundations of Computer Science (FOCS), pp. 268–277, CiteSeerX 10.1.1.211.8704, doi:10.1109/SFCS.1991.185378, ISBN 978-0-8186-2445-2.
  8. ↑ Afek, Yehuda; Kutten, Shay; Yung, Moti (1997), "The local detection paradigm and its applications to self-stabilization", Theoretical Computer Science, 186 (1–2): 199–229, doi:10.1016/S0304-3975(96)00286-1, MR 1478668.
  9. ↑ Shlomi Dolev, Yehuda Afek: Local Stabilizer. Journal of Parallel and Distributed Computing Volume 62, Issue 5, May 2002, Pages 745-765.
  10. ↑ Baruch Awerbuch, Boaz Patt-Shamir, George Varghese, Shlomi Dolev. Self-Stabilization by Local Checking and Global Reset. WDAG 1994: 326-339.
  11. ↑ [Baruch Awerbuch, Shay Kutten, Yishay Mansour, Boaz Patt-Shamir, George Varghese. Time optimal self-stabilizing synchronization. ACM STOC 1993: 652-661.]
  12. ↑ Shay Kutten, Boaz Patt-Shamir: Stabilizing Time-Adaptive Protocols. Theor. Comput. Sci. 220(1): 93-111 (1999).
  13. ↑ de Boer, Frank; Bonsangue, Marcello; Rutten, Jan (2018). Apt. Cham: Springer. p. 22. ISBN 9783319900889.
  14. ↑ Dolev, Shlomi (2000), Self-Stabilization, MIT Press, ISBN 978-0-262-04178-2.
  15. ↑ Gouda, Mohamed (1995), > The Triumph and Tribulation of System Stabilization, Proceedings of the 9th international workshop on distributed algorithms..
  16. ↑ Shlomi Dolev, Mohamed G. Gouda, and Marco Schneider. Memory requirements for silent stabilization. In PODC '96: Proceedings of the fifteenth annual ACM Symposium on Principles of Distributed Computing, pages 27--34, New York, NY, USA, 1996. ACM Press. Online extended abstract.
  17. ↑ Dolev, Shlomi; Herman, Ted (1997), "Superstabilizing protocols for dynamic distributed systems", Chicago Journal of Theoretical Computer Science, 3: 1–40, doi:10.4086/cjtcs.1997.004, article 4.

बाहरी संबंध

  • libcircle - An implementation of self-stabilization using token passing for termination.
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=स्व-स्थिरीकरण&oldid=15564’