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

From Vigyanwiki
Not to be confused with विकेंद्रीकृत कंप्यूटिंग.

वितरित प्रणाली ऐसी प्रणाली है जिसके घटक विभिन्न संगणक तंत्र पर स्थित होते हैं, जो दूसरे को संदेश भेजकर अपने कार्यों का संचार और समन्वय करते हैं।[1][2] वितरित संगणना कंप्यूटर विज्ञान का क्षेत्र है जो वितरित प्रणालियों का अध्ययन करता है।

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

कंप्यूटर योजना जो वितरित प्रणाली के अंदर चलता है, वितरित योजना कहलाती है, [4] और वितरित कार्यक्रम निर्माण ऐसे योजना लिखने की प्रक्रिया है।

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

परिचय

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

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

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



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

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

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

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

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

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

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

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

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

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


इतिहास

समवर्ती प्रक्रियाओं का उपयोग जो संदेश-प्रेषण के माध्यम से संचार करता है, इसकी जड़ें 1960 के दशक में अध्ययन किए गए ऑपरेटिंग प्रणाली वास्तुकला में हैं।[14] पहली व्यापक वितरित प्रणालियाँ ईथरनेट जैसे स्थानीय क्षेत्र नेटवर्क थीं, जिसका आविष्कार 1970 के दशक में किया गया था।[15]

अरपानेट, इंटरनेट के पूर्ववर्तियों में से , 1960 के दशक के अंत में प्रस्तुत किया गया था, और अरपानेट ईमेल का आविष्कार 1970 के दशक की प्रारंभिकमें किया गया था। ई-मेल अरपानेटका सबसे सफल अनुप्रयोग बना,[16] और संभवतः यह बड़े मापदंड पर वितरित अनुप्रयोग का सबसे पहला उदाहरण है। अरपानेट (और इसके उत्तराधिकारी, वैश्विक इंटरनेट) के अतिरिक्त, अन्य प्रारंभिकी विश्वव्यापी कंप्यूटर नेटवर्क में 1980 के दशक से यूज़नेट और फिडोनेट सम्मिलित थे, दोनों का उपयोग वितरित चर्चा प्रणालियों का समर्थन करने के लिए किया गया था।[17]

वितरित संगणना का अध्ययन 1970 के दशक के अंत और 1980 के दशक की प्रारंभिकमें कंप्यूटर विज्ञान की अपनी शाखा बन गया। क्षेत्र में पहला सम्मेलन, वितरित कम्प्यूटिंग (पीओडीसी) के सिद्धांतों पर संगोष्ठी, 1982 की तारीखें, और वितरित संगणना (डीआईएससी) पर इसके समकक्ष अंतर्राष्ट्रीय संगोष्ठी को पहली बार 1985 में ओटावा में ग्राफ पर वितरित एल्गोरिदम पर अंतर्राष्ट्रीय कार्यशाला के रूप में आयोजित किया गया था।[18]



वास्तुकला

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

वितरित प्रोग्रामिंग आमतौर पर कई बुनियादी आर्किटेक्चर में से एक में आती है: क्लाइंट-सर्वर मॉडल | क्लाइंट-सर्वर, त्रि-स्तरीय (कंप्यूटिंग) | थ्री-टियर, मल्टीटियर आर्किटेक्चर | एन-टियर, या पीयर-टू-पीयर; या श्रेणियाँ: ढीला युग्मन, या कंप्यूटर क्लस्टर। [20]

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

[21]: 227  इसके बजाय सभी जिम्मेदारियों को सभी मशीनों के बीच समान रूप से विभाजित किया जाता है, जिन्हें पीयर के रूप में जाना जाता है। सहकर्मी क्लाइंट और सर्वर दोनों के रूप में सेवा कर सकते हैं।[22] इस वास्तुकला के उदाहरणों में बिटटोरेंट और बिटकॉइन नेटवर्क सम्मिलित हैं।

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






अनुप्रयोग

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

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

उदाहरण

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

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

Main article: वितरित एल्गोरिथ्म


मॉडल

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

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

नीचे दी गई चर्चा कई कंप्यूटरों के स्थितियोंपर केंद्रित है, चूंकि कंप्यूटर पर चलने वाली समवर्ती प्रक्रियाओं के लिए कई उद्देश्य समान हैं।

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

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

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


उदाहरण

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

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

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

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

जटिलता उपाय

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

वितरित एल्गोरिदम के विश्लेषण में, सामान्यतः कम्प्यूटेशनल चरणों की तुलना में संचार संचालन पर अधिक ध्यान दिया जाता है। संभवतः वितरित संगणना का सबसे सरल मॉडल तुल्यकालिक प्रणाली है जहां सभी नोड लॉकस्टेप फैशन में काम करते हैं। यह मॉडल सामान्यतः स्थानीय मॉडल के रूप में जाना जाता है। प्रत्येक संचार दौर के समय, समानांतर में सभी नोड्स (1) अपने निकटतम से नवीनतम संदेश प्राप्त करते हैं, (2) इच्छानुसारा स्थानीय गणना करते हैं, और (3) अपने निकटतम को नए संदेश भेजते हैं। ऐसी प्रणालियों में, केंद्रीय जटिलता माप कार्य को पूरा करने के लिए आवश्यक समकालिक संचार दौरों की संख्या है।[38]

यह जटिलता माप नेटवर्क के व्यास (ग्राफ सिद्धांत) से निकटता से संबंधित है। बता दें कि डी नेटवर्क का व्यास है। ओर, किसी भी संगणनीय समस्या को लगभग 2डी संचार दौरों में तुल्यकालिक वितरित प्रणाली में तुच्छ रूप से हल किया जा सकता है: बस सभी सूचनाओं को स्थान (डी राउंड) में इकट्ठा करें, समस्या को हल करें, और प्रत्येक नोड को समाधान (डी राउंड) के बारे में सूचित करें। .

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

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

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

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

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

वितरित प्रणालियों की अतुल्यकालिक प्रकृति को समझने पर बहुत अधिक शोध भी केंद्रित है:

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


समन्वयक चुनाव

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

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

इस समस्या की परिभाषा का श्रेय अधिकांशतः लेल्न्न को दिया जाता है, जिन्होंने इसे टोकन रिंग नेटवर्क में नया टोकन बनाने के लिए विधि के रूप में औपचारिक रूप दिया, जिसमें टोकन खो गया है।[48]

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

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

समन्वय करने के लिए, वितरित प्रणालियाँ समन्वयकों की अवधारणा को नियोजित करती हैं। समन्वयक चुनाव समस्या केंद्रीय समन्वयक के रूप में कार्य करने के लिए वितरित प्रणाली में विभिन्न प्रोसेसरों पर प्रक्रियाओं के समूह के बीच से प्रक्रिया का चयन करना है। कई केंद्रीय समन्वयक चुनाव एल्गोरिदम उपस्थित हैं।[51]






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

अब तक वितरित प्रणाली को रचना करने पर ध्यान केंद्रित किया गया है जो किसी समस्या को हल करता है। पूरक शोध समस्या वितरित प्रणाली के गुणों का अध्ययन कर रही है।[52][53]

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

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

यह भी देखें


टिप्पणियाँ

  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. ↑ "Distributed Programs". कंप्यूटर विज्ञान में ग्रंथ. London: Springer London. 2010. pp. 373–406. doi:10.1007/978-1-84882-745-5_11. ISBN 978-1-84882-744-8. ISSN 1868-0941. सिस्टम में कई भौतिक रूप से वितरित घटक होते हैं जो अपने निजी भंडारण का उपयोग करके स्वतंत्र रूप से काम करते हैं, लेकिन समय-समय पर स्पष्ट संदेश पासिंग द्वारा संचार भी करते हैं। ऐसी प्रणालियों को वितरित प्रणाली कहा जाता है।
  3. ↑ Dusseau & Dusseau 2016, p. 1-2.
  4. ↑ "Distributed Programs". कंप्यूटर विज्ञान में ग्रंथ. London: Springer London. 2010. pp. 373–406. doi:10.1007/978-1-84882-745-5_11. ISBN 978-1-84882-744-8. ISSN 1868-0941. वितरित कार्यक्रम वितरित सिस्टम के सार विवरण हैं। एक वितरित कार्यक्रम में प्रक्रियाओं का एक संग्रह होता है जो समवर्ती रूप से काम करता है और स्पष्ट संदेश पासिंग द्वारा संचार करता है। प्रत्येक प्रक्रिया वेरिएबल्स के एक सेट तक पहुंच सकती है जो वेरिएबल्स से अलग हैं जिन्हें किसी अन्य प्रक्रिया द्वारा बदला जा सकता है।
  5. ↑ 5.0 5.1 Andrews (2000), p. 291–292. Dolev (2000), p. 5.
  6. ↑ Lynch (1996), p. 1.
  7. ↑ Ghosh (2007), पी। 10.
  8. ↑ Ghosh (2007), p. 10. Keidar (2008).
  9. ↑ Lynch (1996), p. xix, 1–2. Peleg (2000), p. 1.
  10. ↑ Peleg (2000), p. 1.
  11. ↑ Papadimitriou (1994), Chapter 15. Keidar (2008).
  12. ↑ See references in Introduction.
  13. ↑ 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.
  14. ↑ Andrews (2000), p. 348.
  15. ↑ Andrews (2000), p. 32.
  16. ↑ Peter (2004), The history of email Archived 2009-04-15 at the Wayback Machine.
  17. ↑ 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.
  18. ↑ 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.
  19. ↑ Ohlídal, M.; Jaroš, J.; Schwarz, J.; et al. (2006). "Evolutionary Design of OAB and AAB Communication Schedules for Interconnection Networks". In Rothlauf, F.; Branke, J.; Cagnoni, S. (eds.). विकासवादी कंप्यूटिंग के अनुप्रयोग. Springer Science & Business Media. pp. 267–78. ISBN 9783540332374.
  20. ↑ "वास्तविक समय और वितरित कम्प्यूटिंग सिस्टम" (PDF). ISSN 2278-0661. Archived from the original (PDF) on 2017-01-10. Retrieved 2017-01-09. {{cite journal}}: Cite journal requires |journal= (help)
  21. ↑ विग्ना पी, केसी एमजे। क्रिप्टोक्यूरेंसी का युग: कैसे बिटकॉइन और ब्लॉकचैन वैश्विक आर्थिक व्यवस्था को चुनौती दे रहे हैं सेंट मार्टिन प्रेस 27 जनवरी, 2015 ISBN 9781250065636
  22. ↑ Hieu., Vu, Quang (2010). Peer-to-peer computing : principles and applications. Lupu, Mihai., Ooi, Beng Chin, 1961-. Heidelberg: Springer. p. 16. ISBN 9783642035135. OCLC 663093862.{{cite book}}: CS1 maint: multiple names: authors list (link)
  23. ↑ 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.
  24. ↑ 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.
  25. ↑ Elmasri & Navathe (2000), Section 24.1.2.
  26. ↑ Andrews (2000), p. 10–11. Ghosh (2007), p. 4–6. Lynch (1996), p. xix, 1. Peleg (2000), p. xv. Elmasri & Navathe (2000), Section 24.
  27. ↑ 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.
  28. ↑ 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.
  29. ↑ Savage, J.E. (1998). Models of Computation: Exploring the Power of Computing. Addison Wesley. p. 209. ISBN 9780201895391.
  30. ↑ Cormen, Leiserson & Rivest (1990), Section 30.
  31. ↑ Herlihy & Shavit (2008), Chapters 2-6.
  32. ↑ Lynch (1996)
  33. ↑ Cormen, Leiserson & Rivest (1990), Sections 28 and 29.
  34. ↑ Cole & Vishkin (1986). Cormen, Leiserson & Rivest (1990), Section 30.5.
  35. ↑ Andrews (2000), p. ix.
  36. ↑ Arora & Barak (2009), Section 6.7. Papadimitriou (1994), Section 15.3.
  37. ↑ Papadimitriou (1994), Section 15.2.
  38. ↑ Lynch (1996), p. 17–23.
  39. ↑ Peleg (2000), Sections 2.3 and 7. Linial (1992). Naor & Stockmeyer (1995).
  40. ↑ 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.
  41. ↑ Lynch (1996), Sections 5–7. Ghosh (2007), Chapter 13.
  42. ↑ Lynch (1996), p. 99–102. Ghosh (2007), p. 192–193.
  43. ↑ Dolev (2000). Ghosh (2007), Chapter 17.
  44. ↑ Lynch (1996), Section 16. Peleg (2000), Section 6.
  45. ↑ Lynch (1996), Section 18. Ghosh (2007), Sections 6.2–6.3.
  46. ↑ Ghosh (2007), Section 6.4.
  47. ↑ 47.0 47.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.
  48. ↑ LeLann, G. (1977). "Distributed systems - toward a formal approach". Information Processing. 77: 155·160 – via Elsevier.
  49. ↑ 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)
  50. ↑ 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.
  51. ↑ Hamilton, Howard. "Distributed Algorithms". Archived from the original on 2012-11-24. Retrieved 2013-03-03.
  52. ↑ "Major unsolved problems in distributed systems?". cstheory.stackexchange.com. Archived from the original on 20 January 2023. Retrieved 16 March 2018.
  53. ↑ "How big data and distributed systems solve traditional scalability problems". theserverside.com. Archived from the original on 17 March 2018. Retrieved 16 March 2018.
  54. ↑ 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.
  55. ↑ 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=110507’