वितरित एल्गोरिथ्म

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

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

परमाणु प्रतिबद्ध

परमाणु प्रतिबद्ध ऐसा संचालन है जहां भिन्न-भिन्न परिवर्तनों का समुच्चय ही संचालन के रूप में प्रारम्भ किया जाता है। यदि परमाणु प्रतिबद्धता सफल होती है, तो इसका अर्थ है कि सभी परिवर्तन प्रारम्भ हो गए हैं। यदि परमाणु कमिट पूर्ण होने से पूर्व कोई विफलता होती है, तो "प्रतिज्ञा" निरस्त कर दी जाती है और कोई परिवर्तन प्रारम्भ नहीं किया जाएगा।

परमाणु प्रतिबद्ध समस्या का समाधान करने के लिए एल्गोरिदम में टू-फेज कमिट प्रोटोकॉल और दो-चरण प्रतिबद्ध प्रोटोकॉल सम्मिलित हैं।

सर्वसम्मति (कंप्यूटर विज्ञान)

सर्वसम्मति एल्गोरिदम साधारण निर्णय पर सहमत होने वाली कई प्रक्रियाओं की समस्या को समाधान करने का प्रयास करते हैं।

अधिक स्थिर रूप से, सर्वसम्मति शिष्टाचार को नीचे चार औपचारिक गुणों को पूर्ण करना चाहिए।

• समाप्ति: प्रत्येक सही प्रक्रिया कुछ मूल्य निर्धारित करती है।
• वैधता: यदि सभी प्रक्रियाएं समान मान $v$ प्रस्तावित करती हैं, तब प्रत्येक सही प्रक्रिया $v$ निर्धारित करती है।

* अखंडता: प्रत्येक सही प्रक्रिया अधिकतम मूल्य निर्धारित करती है, और यदि यह कुछ मूल्य निर्धारित करती है $v$, तब $v$ किसी प्रक्रिया द्वारा प्रस्तावित किया गया होगा।

• समाधान: यदि सही प्रक्रिया $v$ निर्धारित करती है, तब प्रत्येक सही प्रक्रिया $v$ निर्धारित करती है।

सर्वसम्मति का समाधान करने के लिए सामान्य एल्गोरिदम पैक्सोस एल्गोरिथम और रफ़ एल्गोरिथम (कंप्यूटर विज्ञान) हैं।

वितरित खोज

लीडर इलेक्शन

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

आपसी बहिष्कार

अन्य-अवरुद्ध डेटा संरचनाएं

विश्वसनीय प्रसारण को समाप्त करना

विश्वसनीय प्रसारण वितरित प्रणालियों में संचार आदिम है। विश्वसनीय प्रसारण निम्नलिखित गुणों द्वारा परिभाषित किया गया है।

• वैधता - यदि कोई सही प्रक्रिया संदेश भेजती है, तो कोई सही प्रक्रिया अंततः उस संदेश को पहुंचा देगी।
• समाधान - यदि सही प्रक्रिया संदेश देती है, तो सभी सही प्रक्रियाएँ अंततः उस संदेश को वितरित करती हैं।
• अखंडता - प्रत्येक सही प्रक्रिया संदेश को केवल तभी वितरित करती है जब वह संदेश किसी प्रक्रिया द्वारा भेजा गया हो।

विश्वसनीय प्रसारण में अनुक्रमिक, कारणात्मक या कुल क्रम हो सकता है।

प्रतिकृति (कंप्यूटर विज्ञान)

संसाधनों का आवंटन

फैले पेड़ पीढ़ी

समरूपता विभक्त, उदाहरण शीर्ष रंग।

अग्रिम पठन

• Christian Cachin; Rachid Guerraoui; Luís Rodrigues (2011), Introduction to Reliable and Secure Distributed Programming (2. ed.), Springer, Bibcode:2011itra.book.....C, ISBN 978-3-642-15259-7
• C. Rodríguez, M. Villagra and B. Barán, Asynchronous team algorithms for Boolean Satisfiability, Bionetics2007, pp. 66–69, 2007.

बाप्रत्येकी संबंध

• Media related to Distributed algorithms at Wikimedia Commons
• MIT Open Courseware - Distributed Algorithms