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

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

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

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

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

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

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

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

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

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