वितरित पारस्परिक अपवर्जन और लीडर चुनाव

पारस्परिक अपवर्जन और लीडर चुनाव शास्त्रीय समन्वय समस्याएँ हैं: यह सुनिश्चित करना कि अधिकतम एक प्रक्रिया एक महत्वपूर्ण संसाधन तक पहुँचती है, और साथियों के बीच एक विशिष्ट समन्वयक का चयन करना।

Definition

वितरित पारस्परिक अपवर्जन यह सुनिश्चित करता है कि एक समय में अधिकतम एक प्रक्रिया एक साझा संसाधन को धारण करती है, जबकि सभी अनुरोधकर्ताओं के लिए अंततः पहुँच सुनिश्चित करती है; लीडर चुनाव नियतात्मक रूप से ठीक एक प्रक्रिया को समन्वयक के रूप में चुनता है, जिसमें सभी प्रक्रियाएँ परिणाम पर सहमत होती हैं।

Scope

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

Core questions

• प्रक्रियाएँ केवल संदेशों का उपयोग करके एक साझा संसाधन तक पहुँच को कैसे क्रमबद्ध कर सकती हैं?
• अनुमति-आधारित और टोकन-आधारित योजनाओं के बीच संदेश-जटिलता और निष्पक्षता में क्या समझौता हैं?
• एक अद्वितीय लीडर का चुनाव कैसे किया जाता है, और लीडर के विफल होने के बाद चुनाव को कैसे पुनः ट्रिगर किया जाता है?

Key theories

अनुमति-आधारित पारस्परिक अपवर्जन

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

टोकन-आधारित पारस्परिक अपवर्जन

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

लीडर चुनाव

रिंगों के लिए चांग-रॉबर्ट्स और सामान्य नेटवर्कों के लिए बुली एल्गोरिदम जैसे चुनाव एल्गोरिदम एक एकल उच्चतम-प्राथमिकता वाले समन्वयक पर अभिसरण करने के लिए प्रक्रिया पहचानकर्ताओं का उपयोग करते हैं जिसे सभी सही प्रक्रियाएँ पहचानती हैं।

Clinical relevance

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

History

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

Key figures

• Leslie Lamport
• Glenn Ricart
• Ashok Agrawala
• Hector Garcia-Molina

Seminal works

• ricart1981
• garcia-molina1982
• lynch1996

Frequently asked questions

वितरित पारस्परिक अपवर्जन एक ही मशीन पर लॉक से कैसे भिन्न है?

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