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