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

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

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

एटॉमिक कमिट

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

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

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

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

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

• समाप्ति: प्रत्येक सही प्रक्रिया कुछ मूल्य निर्धारित करती है।
• वैधता: यदि सभी प्रक्रियाएं समान मान $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