वितरित अभिकलन

From Vigyanwiki
Revision as of 23:05, 17 February 2023 by alpha>Saurabh
Not to be confused with Decentralized computing.

वितरित प्रणाली ऐसी प्रणाली है जिसके घटक विभिन्न संगणक तंत्र पर स्थित होते हैं, जो दूसरे को संदेश भेजकर अपने कार्यों का संचार और समन्वय करते हैं।[1]Cite error: Invalid <ref> tag; invalid names, e.g. too many वितरित संगणना कंप्यूटर विज्ञान का क्षेत्र है जो वितरित प्रणालियों का अध्ययन करता है।

सामान्य लक्ष्य को प्राप्त करने के लिए वितरित प्रणाली के घटक दूसरे के साथ बातचीत करते हैं। वितरित प्रणालियों की तीन महत्वपूर्ण चुनौतियाँ हैं: घटकों की संगति बनाए रखना, घड़ी के समकालीन पर काबू पाना और घटकों की स्वतंत्र विफलता का प्रबंधन करना।[1]जब प्रणाली का कंपोनेंट फेल हो जाता है, तो संपूर्ण प्रणाली विफल नहीं होती है।[2] वितरित प्रणाली के उदाहरण सेवा उन्मुख संरचना | SOA- आधारित प्रणाली से लेकर बड़े पैमाने पर मल्टीप्लेयर ऑनलाइन गेम से लेकर समकक्ष को समकक्ष | समकक्ष-को-समकक्ष एप्लिकेशन तक भिन्न होते हैं।

कंप्यूटर योजना जो वितरित प्रणाली के भीतर चलता है, वितरित योजना कहलाता है, Cite error: Invalid <ref> tag; invalid names, e.g. too many और वितरित प्रोग्रामिंग ऐसे योजना लिखने की प्रक्रिया है।

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

परिचय

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

जबकि वितरित प्रणाली की कोई परिभाषा नहीं है,[5] निम्नलिखित पारिभाषिक गुण आमतौर पर इस रूप में उपयोग किए जाते हैं:

  • कई स्वायत्त कम्प्यूटेशनल संस्थाएँ (कंप्यूटर या नोड (नेटवर्किंग)) हैं, जिनमें से प्रत्येक की अपनी स्थानीय मेमोरी (कंप्यूटर) है।
  • संदेश पास करके संस्थाएँ दूसरे से संवाद करती हैं।



वितरित प्रणाली का सामान्य लक्ष्य हो सकता है, जैसे कि बड़ी कम्प्यूटेशनल समस्या को हल करना;

वितरित प्रणालियों के अन्य विशिष्ट गुणों में निम्नलिखित शामिल हैं:

  • प्रणाली की संरचना (नेटवर्क टोपोलॉजी, नेटवर्क लेटेंसी, कंप्यूटर की संख्या) पहले से ज्ञात नहीं है, प्रणाली में विभिन्न प्रकार के कंप्यूटर और नेटवर्क लिंक शामिल हो सकते हैं, और वितरित योजना के निष्पादन के दौरान प्रणाली बदल सकता है।
  • प्रत्येक कंप्यूटर में प्रणाली का केवल सीमित, अधूरा दृश्य होता है। प्रत्येक कंप्यूटर इनपुट के केवल भाग को जान सकता है।

समानांतर और वितरित संगणना

(ए), (बी): वितरित प्रणाली।
(सी): समानांतर प्रणाली।

वितरित प्रणाली नेटवर्क वाले कंप्यूटरों के समूह हैं जो अपने काम के लिए सामान्य लक्ष्य साझा करते हैं।

समवर्ती संगणना, समानांतर संगणना और वितरित संगणना में बहुत अधिक ओवरलैप है, और उनके बीच कोई स्पष्ट अंतर मौजूद नहीं है।[6] ही प्रणाली को समानांतर और वितरित दोनों के रूप में वर्णित किया जा सकता है; विशिष्ट वितरित प्रणाली में प्रोसेसर समवर्ती समानांतर में चलते हैं।[7] समानांतर संगणना को वितरित संगणना के विशेष कसकर युग्मित रूप के रूप में देखा जा सकता है,[8] और वितरित संगणना को समानांतर संगणना के ढीले युग्मित रूप के रूप में देखा जा सकता है।

  • समानांतर संगणना में, प्रोसेसर के बीच सूचनाओं के आदान-प्रदान के लिए सभी प्रोसेसर के पास साझा स्मृति वास्तुकला तक पहुंच हो सकती है।[9]
  • वितरित संगणना में, प्रत्येक प्रोसेसर की अपनी निजी मेमोरी (वितरित मेमोरी) होती है। सूचना का आदान-प्रदान प्रोसेसर के बीच संदेश भेजकर किया जाता है।[10]

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

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


इतिहास

समवर्ती प्रक्रियाओं का उपयोग जो संदेश-प्रेषण के माध्यम से संचार करता है, इसकी जड़ें 1960 के दशक में अध्ययन किए गए ऑपरेटिंग प्रणाली आर्किटेक्चर में हैं।[12] पहली व्यापक वितरित प्रणालियाँ ईथरनेट जैसे स्थानीय क्षेत्र नेटवर्क थीं, जिसका आविष्कार 1970 के दशक में किया गया था।[13] ARPANET, इंटरनेट के पूर्ववर्तियों में से , 1960 के दशक के अंत में पेश किया गया था, और ARPANET ईमेल का आविष्कार 1970 के दशक की शुरुआत में किया गया था। ई-मेल ARPANET का सबसे सफल अनुप्रयोग बना,[14] और शायद यह बड़े पैमाने पर वितरित अनुप्रयोग का सबसे पहला उदाहरण है। ARPANET (और इसके उत्तराधिकारी, वैश्विक इंटरनेट) के अलावा, अन्य शुरुआती विश्वव्यापी कंप्यूटर नेटवर्क में 1980 के दशक से यूज़नेट और फिडोनेट शामिल थे, दोनों का उपयोग वितरित चर्चा प्रणालियों का समर्थन करने के लिए किया गया था।[15] वितरित संगणना का अध्ययन 1970 के दशक के अंत और 1980 के दशक की शुरुआत में कंप्यूटर विज्ञान की अपनी शाखा बन गया। क्षेत्र में पहला सम्मेलन, वितरित कम्प्यूटिंग (पीओडीसी) के सिद्धांतों पर संगोष्ठी, 1982 की तारीखें, और वितरित संगणना (डीआईएससी) पर इसके समकक्ष अंतर्राष्ट्रीय संगोष्ठी को पहली बार 1985 में ओटावा में ग्राफ पर वितरित एल्गोरिदम पर अंतर्राष्ट्रीय कार्यशाला के रूप में आयोजित किया गया था।[16]


आर्किटेक्चर

वितरित संगणना के लिए विभिन्न हार्डवेयर और सॉफ्टवेयर आर्किटेक्चर का उपयोग किया जाता है। निचले स्तर पर, किसी प्रकार के नेटवर्क के साथ कई सीपीयू को आपस में जोड़ना आवश्यक है, भले ही वह नेटवर्क सर्किट बोर्ड पर मुद्रित हो या ढीले युग्मित उपकरणों और केबलों से बना हो। उच्च स्तर पर, उन सीपीयू पर चलने वाली प्रक्रिया ( संगणना) को किसी प्रकार की संचार प्रणाली से जोड़ना आवश्यक है।Cite error: Closing </ref> missing for <ref> tag इस आर्किटेक्चर के उदाहरणों में बिटटोरेंट और बिटकॉइन नेटवर्क शामिल हैं।

वितरित संगणना आर्किटेक्चर का अन्य बुनियादी पहलू समवर्ती प्रक्रियाओं के बीच संचार और समन्वय कार्य की विधि है। विभिन्न संदेश पासिंग प्रोटोकॉल के माध्यम से, प्रक्रियाएं दूसरे के साथ सीधे संवाद कर सकती हैं, आमतौर पर मास्टर/स्लेव (प्रौद्योगिकी) | मास्टर/स्लेव संबंध में। वैकल्पिक रूप से, डेटाबेस-केंद्रित आर्किटेक्चर | डेटाबेस-केंद्रित आर्किटेक्चर साझा डेटाबेस का उपयोग करके वितरित संगणना को किसी भी प्रकार के प्रत्यक्ष अंतर-प्रक्रिया संचार के बिना सक्षम कर सकता है।[17] डेटाबेस-केंद्रित आर्किटेक्चर विशेष रूप से लाइव पर्यावरण रिले के लिए योजनाबद्ध आर्किटेक्चर में रिलेशनल प्रोसेसिंग एनालिटिक्स प्रदान करता है। यह नेटवर्क किए गए डेटाबेस के पैरामीटर के भीतर और बाहर वितरित संगणना कार्यों को सक्षम बनाता है।[18]


अनुप्रयोग

वितरित प्रणाली और वितरित संगणना का उपयोग करने के कारणों में शामिल हो सकते हैं:

  • किसी एप्लिकेशन की प्रकृति के लिए संचार नेटवर्क के उपयोग की आवश्यकता हो सकती है जो कई कंप्यूटरों को जोड़ता है: उदाहरण के लिए, भौतिक स्थान में उत्पादित डेटा और दूसरे स्थान पर आवश्यक।
  • ऐसे कई मामले हैं जिनमें ही कंप्यूटर का उपयोग सिद्धांत रूप में संभव होगा, लेकिन वितरित प्रणाली का उपयोग व्यावहारिक कारणों से फायदेमंद होता है। उदाहरण के लिए:
    • यह मशीन की तुलना में अधिक बड़े भंडारण और मेमोरी, तेज गणना और उच्च बैंडविड्थ की अनुमति दे सकता है।
    • यह गैर-वितरित प्रणाली की तुलना में अधिक विश्वसनीयता प्रदान कर सकता है, क्योंकि विफलता का भी बिंदु नहीं है। इसके अलावा, अखंड यूनिप्रोसेसर प्रणाली की तुलना में वितरित प्रणाली का विस्तार और प्रबंधन करना आसान हो सकता है।[19]
    • ल हाई-एंड कंप्यूटर की तुलना में कई लो-एंड कंप्यूटरों के क्लस्टर ( संगणना) का उपयोग करके प्रदर्शन का वांछित स्तर प्राप्त करना अधिक लागत प्रभावी हो सकता है।

उदाहरण

वितरित प्रणालियों और वितरित संगणना के अनुप्रयोगों के उदाहरणों में निम्नलिखित शामिल हैं:[20]

सैद्धांतिक नींव

Main article: Distributed algorithm


मॉडल

कई कार्य जिन्हें हम कंप्यूटर का उपयोग करके स्वचालित करना चाहते हैं, वे प्रश्न-उत्तर प्रकार के होते हैं: हम प्रश्न पूछना चाहते हैं और कंप्यूटर को उत्तर देना चाहिए। सैद्धांतिक कंप्यूटर विज्ञान में, ऐसे कार्यों को कम्प्यूटेशनल समस्याएँ कहा जाता है। औपचारिक रूप से, कम्प्यूटेशनल समस्या में प्रत्येक उदाहरण के समाधान के साथ-साथ उदाहरण होते हैं। उदाहरण वे प्रश्न हैं जो हम पूछ सकते हैं, और समाधान इन प्रश्नों के वांछित उत्तर हैं।

सैद्धांतिक कंप्यूटर विज्ञान यह समझने की कोशिश करता है कि कंप्यूटर (कम्प्यूटेबिलिटी थ्योरी (कंप्यूटर साइंस)) और कितनी कुशलता से (कम्प्यूटेशनल जटिलता सिद्धांत) का उपयोग करके कौन सी कम्प्यूटेशनल समस्याओं को हल किया जा सकता है। परंपरागत रूप से, यह कहा जाता है कि कंप्यूटर का उपयोग करके समस्या को हल किया जा सकता है यदि हम एल्गोरिदम डिज़ाइन कर सकते हैं जो किसी दिए गए उदाहरण के लिए सही समाधान उत्पन्न करता है। इस तरह के कलन विधि को कंप्यूटर योजना के रूप में लागू किया जा सकता है जो सामान्य-उद्देश्य वाले कंप्यूटर पर चलता है: योजना सूचना से समस्या का उदाहरण पढ़ता है, कुछ संगणना करता है, और आउटपुट ( संगणना) के रूप में समाधान का उत्पादन करता है। रैंडम-्सेस मशीन या यूनिवर्सल ट्यूरिंग मशीन जैसी औपचारिकताएं इस तरह के एल्गोरिदम को क्रियान्वित करने वाले अनुक्रमिक सामान्य-उद्देश्य वाले कंप्यूटर के अमूर्त मॉडल के रूप में उपयोग की जा सकती हैं।[22][23] समवर्ती और वितरित संगणना का क्षेत्र या तो कई कंप्यूटरों के मामले में समान प्रश्नों का अध्ययन करता है, या कंप्यूटर जो इंटरेक्टिंग प्रक्रियाओं के नेटवर्क को निष्पादित करता है: ऐसे नेटवर्क में कौन सी कम्प्यूटेशनल समस्याओं को हल किया जा सकता है और कितनी कुशलता से? हालाँकि, यह बिल्कुल स्पष्ट नहीं है कि समवर्ती या वितरित प्रणाली के मामले में किसी समस्या को हल करने का क्या मतलब है: उदाहरण के लिए, एल्गोरिथम डिज़ाइनर का कार्य क्या है, और अनुक्रमिक सामान्य के समवर्ती या वितरित समतुल्य क्या है- उद्देश्य कंप्यूटर?[citation needed] नीचे दी गई चर्चा कई कंप्यूटरों के मामले पर केंद्रित है, हालांकि कंप्यूटर पर चलने वाली समवर्ती प्रक्रियाओं के लिए कई मुद्दे समान हैं।

आमतौर पर तीन दृष्टिकोणों का उपयोग किया जाता है:

साझा-स्मृति मॉडल में समानांतर एल्गोरिदम
  • सभी प्रोसेसर की साझा मेमोरी तक पहुंच होती है। एल्गोरिथ्म डिजाइनर प्रत्येक प्रोसेसर द्वारा निष्पादित योजना को चुनता है।
  • सैद्धांतिक मॉडल है समानांतर RAM | समानांतर रैंडम-्सेस मशीन (PRAM) जिनका उपयोग किया जाता है।[24] हालाँकि, शास्त्रीय PRAM मॉडल साझा मेमोरी में सिंक्रोनस ्सेस को मानता है।
  • साझा-मेमोरी योजना को वितरित प्रणाली तक बढ़ाया जा सकता है यदि अंतर्निहित ऑपरेटिंग प्रणाली नोड्स के बीच संचार को एनकैप्सुलेट करता है और वस्तुतः सभी अलग-अलग प्रणाली में मेमोरी को ीकृत करता है।
  • मॉडल जो वास्तविक-विश्व मल्टीप्रोसेसर मशीनों के व्यवहार के करीब है और मशीन निर्देशों के उपयोग को ध्यान में रखता है, जैसे कि तुलना-और-स्वैप (CAS), अतुल्यकालिक साझा मेमोरी है। इस मॉडल पर काम का विस्तृत निकाय है, जिसका सारांश साहित्य में पाया जा सकता है।[25][26]
संदेश-पासिंग मॉडल में समानांतर एल्गोरिदम
  • एल्गोरिथ्म डिजाइनर नेटवर्क की संरचना, साथ ही प्रत्येक कंप्यूटर द्वारा निष्पादित योजना को चुनता है।
  • बूलियन सर्किट और छँटाई नेटवर्क जैसे मॉडल का उपयोग किया जाता है।[27] बूलियन सर्किट को कंप्यूटर नेटवर्क के रूप में देखा जा सकता है: प्रत्येक गेट कंप्यूटर है जो अत्यंत सरल कंप्यूटर योजना चलाता है। इसी तरह, सॉर्टिंग नेटवर्क को कंप्यूटर नेटवर्क के रूप में देखा जा सकता है: प्रत्येक तुलनित्र कंप्यूटर है।
संदेश-पासिंग मॉडल में वितरित एल्गोरिदम
  • एल्गोरिदम डिजाइनर केवल कंप्यूटर योजना चुनता है। सभी कंप्यूटर ही योजना चलाते हैं। नेटवर्क की संरचना की परवाह किए बिना प्रणाली को सही ढंग से काम करना चाहिए।
  • आमतौर पर इस्तेमाल किया जाने वाला मॉडल ग्राफ़ (असतत गणित) है जिसमें प्रति नोड परिमित-राज्य मशीन होती है।

वितरित एल्गोरिदम के मामले में, कम्प्यूटेशनल समस्याएं आमतौर पर ग्राफ़ से संबंधित होती हैं। अक्सर कंप्यूटर नेटवर्क की संरचना का वर्णन करने वाला ग्राफ समस्या का उदाहरण है। यह निम्नलिखित उदाहरण में सचित्र है।[citation needed]


उदाहरण

किसी दिए गए ग्राफ G का रंग खोजने की कम्प्यूटेशनल समस्या पर विचार करें। विभिन्न क्षेत्रों में निम्नलिखित तरीके अपनाए जा सकते हैं:

केंद्रीकृत एल्गोरिदम[citation needed]
  • ग्राफ G को स्ट्रिंग के रूप में एन्कोड किया गया है, और स्ट्रिंग को कंप्यूटर में इनपुट के रूप में दिया गया है। कंप्यूटर योजना ग्राफ का रंग ढूंढता है, रंग को स्ट्रिंग के रूप में एन्कोड करता है, और परिणाम को आउटपुट करता है।
समानांतर एल्गोरिदम
  • फिर से, ग्राफ G को स्ट्रिंग के रूप में एन्कोड किया गया है। हालाँकि, कई कंप्यूटर ही स्ट्रिंग को समानांतर में ्सेस कर सकते हैं। प्रत्येक कंप्यूटर ग्राफ़ के भाग पर ध्यान केंद्रित कर सकता है और उस भाग के लिए रंग उत्पन्न कर सकता है।
  • मुख्य ध्यान उच्च-प्रदर्शन संगणना पर है जो समानांतर में कई कंप्यूटरों की प्रसंस्करण शक्ति का शोषण करता है।
वितरित एल्गोरिदम
  • ग्राफ जी कंप्यूटर नेटवर्क की संरचना है। जी के प्रत्येक नोड के लिए कंप्यूटर है और जी के प्रत्येक किनारे के लिए संचार लिंक है। प्रारंभ में, प्रत्येक कंप्यूटर केवल ग्राफ जी में अपने निकटतम पड़ोसियों के बारे में जानता है; जी की संरचना के बारे में अधिक जानने के लिए कंप्यूटरों को दूसरे के साथ संदेशों का आदान-प्रदान करना चाहिए। प्रत्येक कंप्यूटर को आउटपुट के रूप में अपना रंग बनाना चाहिए।
  • मुख्य ध्यान मनमाना वितरित प्रणाली के संचालन के समन्वय पर है।[citation needed]

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

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

जटिलता उपाय

समानांतर एल्गोरिदम में, समय और स्थान के अतिरिक्त अन्य संसाधन कंप्यूटरों की संख्या है। दरअसल, चलने के समय और कंप्यूटर की संख्या के बीच अक्सर समझौता होता है: समस्या को तेजी से हल किया जा सकता है यदि समानांतर में अधिक कंप्यूटर चल रहे हों (गति बढ़ाना देखें)। यदि प्रोसेसर की बहुपद संख्या का उपयोग करके बहुलगणकीय समय में निर्णय समस्या को हल किया जा सकता है, तो समस्या को एनसी (जटिलता) वर्ग में कहा जाता है।[30] कक्षा एनसी को प्रैम औपचारिकता या बूलियन सर्किट का उपयोग करके समान रूप से अच्छी तरह से परिभाषित किया जा सकता है- PRAM मशीनें बूलियन सर्किट को कुशलता से अनुकरण कर सकती हैं और इसके विपरीत।[31] वितरित एल्गोरिदम के विश्लेषण में, आमतौर पर कम्प्यूटेशनल चरणों की तुलना में संचार संचालन पर अधिक ध्यान दिया जाता है। शायद वितरित संगणना का सबसे सरल मॉडल तुल्यकालिक प्रणाली है जहां सभी नोड लॉकस्टेप फैशन में काम करते हैं। यह मॉडल आमतौर पर स्थानीय मॉडल के रूप में जाना जाता है। प्रत्येक संचार दौर के दौरान, समानांतर में सभी नोड्स (1) अपने पड़ोसियों से नवीनतम संदेश प्राप्त करते हैं, (2) मनमाना स्थानीय गणना करते हैं, और (3) अपने पड़ोसियों को नए संदेश भेजते हैं। ऐसी प्रणालियों में, केंद्रीय जटिलता माप कार्य को पूरा करने के लिए आवश्यक समकालिक संचार दौरों की संख्या है।[32] यह जटिलता माप नेटवर्क के व्यास (ग्राफ सिद्धांत) से निकटता से संबंधित है। बता दें कि D नेटवर्क का व्यास है। ओर, किसी भी संगणनीय समस्या को लगभग 2D संचार दौरों में तुल्यकालिक वितरित प्रणाली में तुच्छ रूप से हल किया जा सकता है: बस सभी सूचनाओं को स्थान (डी राउंड) में इकट्ठा करें, समस्या को हल करें, और प्रत्येक नोड को समाधान (डी राउंड) के बारे में सूचित करें। .

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

अन्य आमतौर पर इस्तेमाल किया जाने वाला माप नेटवर्क में प्रसारित बिट्स की कुल संख्या है (cf. संचार जटिलता)।[34] इस अवधारणा की विशेषताओं को आम तौर पर CONGEST(B) मॉडल के साथ कैप्चर किया जाता है, जिसे समान रूप से LOCAL मॉडल के रूप में परिभाषित किया जाता है, लेकिन जहां ल संदेशों में केवल B बिट्स हो सकते हैं।

अन्य समस्याएं

पारंपरिक कम्प्यूटेशनल समस्याएं इस परिप्रेक्ष्य में लेती हैं कि उपयोगकर्ता प्रश्न पूछता है, कंप्यूटर (या वितरित प्रणाली) प्रश्न को संसाधित करता है, फिर उत्तर उत्पन्न करता है और रुक जाता है। हालाँकि, ऐसी समस्याएँ भी हैं जहाँ प्रणाली को रुकने की आवश्यकता नहीं है, जिसमें डाइनिंग फिलोसोफर्स समस्या और अन्य समान पारस्परिक बहिष्करण समस्याएं शामिल हैं। इन समस्याओं में, वितरित प्रणाली को साझा संसाधनों के उपयोग को लगातार समन्वयित करना चाहिए ताकि कोई विरोध या गतिरोध न हो।

मूलभूत चुनौतियाँ भी हैं जो वितरित संगणना के लिए अद्वितीय हैं, उदाहरण के लिए दोष-सहिष्णुता से संबंधित। संबंधित समस्याओं के उदाहरणों में आम सहमति (कंप्यूटर विज्ञान),[35] बीजान्टिन दोष सहिष्णुता,[36] और आत्म-स्थिरीकरण।[37] वितरित प्रणालियों की अतुल्यकालिक प्रकृति को समझने पर बहुत अधिक शोध भी केंद्रित है:

  • सिंक्रोनाइज़र (एल्गोरिदम) का उपयोग एसिंक्रोनस प्रणाली में तुल्यकालन (एल्गोरिदम) को चलाने के लिए किया जा सकता है।[38]
  • तार्किक घड़ियाँ घटनाओं के क्रम से पहले घटित होने का कारण प्रदान करती हैं।[39]
  • घड़ी तुल्यकालन एल्गोरिदम विश्व स्तर पर लगातार भौतिक समय टिकट प्रदान करते हैं।[40]


नेता चुनाव

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

इस समस्या की परिभाषा का श्रेय अक्सर LeLann को दिया जाता है, जिन्होंने इसे टोकन रिंग नेटवर्क में नया टोकन बनाने के लिए विधि के रूप में औपचारिक रूप दिया, जिसमें टोकन खो गया है।[42] समन्वयक चुनाव एल्गोरिदम को प्रेषित कुल बाइट्स और समय के मामले में किफायती होने के लिए डिज़ाइन किया गया है। Gallager, Humblet, और Spira द्वारा सुझाए गए एल्गोरिथम [43] सामान्य रूप से अप्रत्यक्ष रेखांकन के लिए वितरित एल्गोरिदम के डिजाइन पर मजबूत प्रभाव पड़ा है, और वितरित संगणना में प्रभावशाली पेपर के लिए दिकस्ट्रा पुरस्कार जीता है।

विभिन्न प्रकार के नेटवर्क ग्राफ़ (असतत गणित) के लिए कई अन्य एल्गोरिदम सुझाए गए थे, जैसे अप्रत्यक्ष छल्ले, यूनिडायरेक्शनल रिंग, पूर्ण ग्राफ़, ग्रिड, निर्देशित यूलर ग्राफ़ और अन्य। समन्वयक चुनाव एल्गोरिथम के डिजाइन से ग्राफ परिवार के मुद्दे को अलग करने वाली सामान्य विधि कोराच, कुटेन और मोरन द्वारा सुझाई गई थी।[44] समन्वय करने के लिए, वितरित प्रणालियाँ समन्वयकों की अवधारणा को नियोजित करती हैं। समन्वयक चुनाव समस्या केंद्रीय समन्वयक के रूप में कार्य करने के लिए वितरित प्रणाली में विभिन्न प्रोसेसरों पर प्रक्रियाओं के समूह के बीच से प्रक्रिया का चयन करना है। कई केंद्रीय समन्वयक चुनाव एल्गोरिदम मौजूद हैं।[45]


वितरित प्रणाली के गुण

अब तक वितरित प्रणाली को डिजाइन करने पर ध्यान केंद्रित किया गया है जो किसी समस्या को हल करता है। पूरक शोध समस्या वितरित प्रणाली के गुणों का अध्ययन कर रही है।[46][47] हॉल्टिंग प्रॉब्लम सेंट्रलाइज्ड कम्प्यूटेशन के क्षेत्र से समान उदाहरण है: हमें कंप्यूटर योजना दिया जाता है और कार्य यह तय करना है कि यह रुकता है या हमेशा के लिए चलता है। सामान्य स्थिति में रुकने की समस्या अनिर्णीत समस्या है, और स्वाभाविक रूप से कंप्यूटर नेटवर्क के व्यवहार को समझना कम से कम उतना ही कठिन है जितना कि कंप्यूटर के व्यवहार को समझना।[48] हालांकि, कई दिलचस्प विशेष मामले हैं जो निर्णायक हैं। विशेष रूप से, परिमित-राज्य मशीनों के नेटवर्क के व्यवहार के बारे में तर्क देना संभव है। उदाहरण बता रहा है कि क्या परस्पर क्रिया (अतुल्यकालिक और गैर-नियतात्मक) परिमित-राज्य मशीनों का दिया गया नेटवर्क गतिरोध तक पहुँच सकता है। यह समस्या पीएसपीएसीई-पूर्ण है,[49] यानी, यह निर्णायक है, लेकिन इसकी संभावना नहीं है कि कुशल (केंद्रीकृत, समानांतर या वितरित) एल्गोरिथम है जो बड़े नेटवर्क के मामले में समस्या को हल करता है।

यह भी देखें


टिप्पणियाँ

  1. ↑ 1.0 1.1 Tanenbaum, Andrew S.; Steen, Maarten van (2002). Distributed systems: principles and paradigms. Upper Saddle River, NJ: Pearson Prentice Hall. ISBN 0-13-088893-1. Archived from the original on 2020-08-12. Retrieved 2020-08-28.
  2. ↑ Dusseau & Dusseau 2016, p. 1-2.
  3. ↑ Lynch (1996), p. 1.
  4. ↑ Cite error: Invalid <ref> tag; no text was provided for refs named Andrews 2000
  5. ↑ Ghosh (2007), पी। 10.
  6. ↑ Ghosh (2007), p. 10. Keidar (2008).
  7. ↑ Lynch (1996), p. xix, 1–2. Peleg (2000), p. 1.
  8. ↑ Peleg (2000), p. 1.
  9. ↑ Papadimitriou (1994), Chapter 15. Keidar (2008).
  10. ↑ See references in Introduction.
  11. ↑ Bentaleb, A.; Yifan, L.; Xin, J.; et al. (2016). "Parallel and Distributed Algorithms" (PDF). National University of Singapore. Archived (PDF) from the original on 2017-03-26. Retrieved 20 July 2018.
  12. ↑ Andrews (2000), p. 348.
  13. ↑ Andrews (2000), p. 32.
  14. ↑ Peter (2004), The history of email Archived 2009-04-15 at the Wayback Machine.
  15. ↑ Banks, M. (2012). On the Way to the Web: The Secret History of the Internet and its Founders. Apress. pp. 44–5. ISBN 9781430250746. Archived from the original on 2023-01-20. Retrieved 2018-07-20.
  16. ↑ Tel, G. (2000). Introduction to Distributed Algorithms. Cambridge University Press. pp. 35–36. ISBN 9780521794831. Archived from the original on 2023-01-20. Retrieved 2018-07-20.
  17. ↑ Lind P, Alm M (2006), "A database-centric virtual chemistry system", J Chem Inf Model, 46 (3): 1034–9, doi:10.1021/ci050360b, PMID 16711722.
  18. ↑ Chiu, G (1990). "A model for optimal database allocation in distributed computing systems". Proceedings. IEEE INFOCOM'90: Ninth Annual Joint Conference of the IEEE Computer and Communications Societies.
  19. ↑ Elmasri & Navathe (2000), Section 24.1.2.
  20. ↑ Andrews (2000), p. 10–11. Ghosh (2007), p. 4–6. Lynch (1996), p. xix, 1. Peleg (2000), p. xv. Elmasri & Navathe (2000), Section 24.
  21. ↑ Haussmann, J. (2019). "Cost-efficient parallel processing of irregularly structured problems in cloud computing environments". Journal of Cluster Computing. 22 (3): 887–909. doi:10.1007/s10586-018-2879-3. S2CID 54447518.
  22. ↑ Toomarian, N.B.; Barhen, J.; Gulati, S. (1992). "Neural Networks for Real-Time Robotic Applications". In Fijany, A.; Bejczy, A. (eds.). Parallel Computation Systems For Robotics: Algorithms And Architectures. World Scientific. p. 214. ISBN 9789814506175. Archived from the original on 2020-08-01. Retrieved 2018-07-20.
  23. ↑ Savage, J.E. (1998). Models of Computation: Exploring the Power of Computing. Addison Wesley. p. 209. ISBN 9780201895391.
  24. ↑ Cormen, Leiserson & Rivest (1990), Section 30.
  25. ↑ Herlihy & Shavit (2008), Chapters 2-6.
  26. ↑ Lynch (1996)
  27. ↑ Cormen, Leiserson & Rivest (1990), Sections 28 and 29.
  28. ↑ Cole & Vishkin (1986). Cormen, Leiserson & Rivest (1990), Section 30.5.
  29. ↑ Andrews (2000), p. ix.
  30. ↑ Arora & Barak (2009), Section 6.7. Papadimitriou (1994), Section 15.3.
  31. ↑ Papadimitriou (1994), Section 15.2.
  32. ↑ Lynch (1996), p. 17–23.
  33. ↑ Peleg (2000), Sections 2.3 and 7. Linial (1992). Naor & Stockmeyer (1995).
  34. ↑ Schneider, J.; Wattenhofer, R. (2011). "Trading Bit, Message, and Time Complexity of Distributed Algorithms". In Peleg, D. (ed.). Distributed Computing. Springer Science & Business Media. pp. 51–65. ISBN 9783642240997. Archived from the original on 2020-08-01. Retrieved 2018-07-20.
  35. ↑ Lynch (1996), Sections 5–7. Ghosh (2007), Chapter 13.
  36. ↑ Lynch (1996), p. 99–102. Ghosh (2007), p. 192–193.
  37. ↑ Dolev (2000). Ghosh (2007), Chapter 17.
  38. ↑ Lynch (1996), Section 16. Peleg (2000), Section 6.
  39. ↑ Lynch (1996), Section 18. Ghosh (2007), Sections 6.2–6.3.
  40. ↑ Ghosh (2007), Section 6.4.
  41. ↑ 41.0 41.1 Haloi, S. (2015). Apache ZooKeeper Essentials. Packt Publishing Ltd. pp. 100–101. ISBN 9781784398323. Archived from the original on 2023-01-20. Retrieved 2018-07-20.
  42. ↑ LeLann, G. (1977). "Distributed systems - toward a formal approach". Information Processing. 77: 155·160 – via Elsevier.
  43. ↑ R. G. Gallager, P. A. Humblet, and P. M. Spira (January 1983). "A Distributed Algorithm for Minimum-Weight Spanning Trees" (PDF). ACM Transactions on Programming Languages and Systems. 5 (1): 66–77. doi:10.1145/357195.357200. S2CID 2758285. Archived (PDF) from the original on 2017-09-26.{{cite journal}}: CS1 maint: multiple names: authors list (link)
  44. ↑ Korach, Ephraim; Kutten, Shay; Moran, Shlomo (1990). "A Modular Technique for the Design of Efficient Distributed Leader Finding Algorithms" (PDF). ACM Transactions on Programming Languages and Systems. 12 (1): 84–101. CiteSeerX 10.1.1.139.7342. doi:10.1145/77606.77610. S2CID 9175968. Archived (PDF) from the original on 2007-04-18.
  45. ↑ Hamilton, Howard. "Distributed Algorithms". Archived from the original on 2012-11-24. Retrieved 2013-03-03.
  46. ↑ "Major unsolved problems in distributed systems?". cstheory.stackexchange.com. Archived from the original on 20 January 2023. Retrieved 16 March 2018.
  47. ↑ "How big data and distributed systems solve traditional scalability problems". theserverside.com. Archived from the original on 17 March 2018. Retrieved 16 March 2018.
  48. ↑ Svozil, K. (2011). "Indeterminism and Randomness Through Physics". In Hector, Z. (ed.). Randomness Through Computation: Some Answers, More Questions. World Scientific. pp. 112–3. ISBN 9789814462631. Archived from the original on 2020-08-01. Retrieved 2018-07-20.
  49. ↑ Papadimitriou (1994), Section 19.3.


संदर्भ

Books
Articles
Web sites


अग्रिम पठन

Books
Articles
Conference Papers
  • Rodriguez, Carlos; Villagra, Marcos; Baran, Benjamin (2007). "Asynchronous team algorithms for Boolean Satisfiability". 2007 2nd Bio-Inspired Models of Network, Information and Computing Systems. pp. 66–69. doi:10.1109/BIMNICS.2007.4610083. S2CID 15185219.


बाहरी संबंध

Wikiquote has quotations related to वितरित अभिकलन.
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=वितरित_अभिकलन&oldid=109039’