Population protocol
વસ્તી પ્રોટોકોલ એ સંસાધન-મર્યાદિત મોબાઇલ એજન્ટો દ્વારા રચાયેલ વિતરિત કમ્પ્યુટિંગ મોડેલ છે જે ક્રિયાપ્રતિક્રિયા ગ્રાફ અનુસાર અવ્યવસ્થિત રીતે મળે છે. કાર્યોની ગણતરી એજન્ટોની સ્થિતિને અપડેટ કરીને કરવામાં આવે છે જ્યારે પણ તેઓ તેમની અગાઉની સ્થિતિના આધારે મળે છે, અને ગણતરીનું પરિણામ એકવાર ગણતરી થઈ જાય પછી એજન્ટોની સ્થિતિમાં વાંચી શકાય છે. મોડેલ ત્યાં નોડ્સનો સમૂહ છે. દરેક નોડ સ્થિતિઓ સાથે મર્યાદિત ઓટોમેટન છે. વસ્તી પ્રોટોકોલનો એક મહત્વપૂર્ણ વર્ગ બહુમતી અલ્ગોરિધમ્સ છે, જ્યાં ધ્યેય બહુમતી બીટની ગણતરી કરવાનો છેઃ દરેક નોડ વિશ્વાસ બીટ સાથે શરૂ થાય છે અને ધ્યેય એક પ્રોટોકોલ ડિઝાઇન કરવાનો છે, જેના અંતે દરેક નોડનો વિશ્વાસ બીટ સાચો પ્રારંભિક બહુમતી બીટ છે. મોડેલનું સ્વતંત્ર સમય સંસ્કરણ નીચે મુજબ છેઃ સમયના દરેક તબક્કે, કેટલાક નોડ રેન્ડમ રીતે સમાન રીતે પસંદ કરવામાં આવે છે. પછી નોડને અન્ય નોડ સાથે સરખાવવામાં આવે છે, જે નોડના પડોશીઓના સમૂહમાંથી એકસરખી રીતે પસંદ કરવામાં આવે છે. પછી, નોડ્સ અને મેમરી સામગ્રીઓનું વિનિમય કરો અને તેમની સ્થિતિને અપડેટ કરો. વૈકલ્પિક રીતે, કોઈ પણ વ્યક્તિ સતત સમયના નમૂનાને ધ્યાનમાં લઈ શકે છે જ્યાં દરેક નોડમાં પોઈસન ઘડિયાળ હોય છે જે એકમ દરે વળે છે. જ્યારે નોડની ઘડિયાળ વળે છે, ત્યારે તે નોડ રેન્ડમ પડોશી સાથે વાતચીત કરે છે. પ્રોટોકોલ ઘણીવાર અભિસરણ સમય અથવા નોડ દીઠ જરૂરી મેમરીની માત્રા અથવા બંનેને ઘટાડવા માટે રચવામાં આવે છે. થ્રી સ્ટેટ પ્રોટોકોલ બહુમતી (સર્વસંમતિ) ની ગણતરીની સમસ્યા માટે, એક જાણીતું પ્રોટોકોલ છે જેમાં નોડ દીઠ માત્ર ત્રણ મેમરી સ્ટેટ્સની જરૂર પડે છે અને સંપૂર્ણ ક્રિયાપ્રતિક્રિયા આલેખ માટે તેનું વિશ્લેષણ કરવામાં આવ્યું છે. આ પ્રોટોકોલ નીચે પ્રમાણે કામ કરે છે. દરેક નોડને તેની મેમરી સ્થિતિને તેમના પ્રારંભિક માન્યતા બીટમાં પ્રારંભ કરવા દો દરેક સમયે, જ્યારે બે નોડ વાતચીત કરે છે, ત્યારે તેઓ નીચે આપેલા કોષ્ટક અનુસાર તેમની સ્થિતિને અપડેટ કરે છે. પંક્તિ લેબલો આરંભકર્તાની સ્થિતિ આપે છે અને સ્તંભ પ્રતિભાવ આપનારની સ્થિતિને લેબલ કરે છે. શબ્દોમાં કહીએ તો, જો માન્યતા સાથે નોડ માન્યતા સાથે નોડ સાથે મેળ ખાય છે, તો પછી બંને નોડ તેમની માન્યતા જાળવી રાખે છે; જો બંને માન્યતાઓ હોય અથવા બંને હોય તો અપડેટ સમાન છે. જો કે, જો આરંભકર્તાની માન્યતા છે અને પ્રતિસાદકર્તાની માન્યતા છે, તો પછી પ્રતિવાદી તેમની માન્યતાને અપડેટ કરે છે. જો બીજી બાજુ આરંભ કરનારને વિશ્વાસ હોય અને જવાબ આપનારને વિશ્વાસ હોય, તો જવાબ આપનાર તેમની માન્યતામાં ફેરફાર કરે છે. નોંધ લો કે આ પ્રોટોકોલ એક તરફી છેઃ દરેક ક્રિયાપ્રતિક્રિયા જવાબ આપનારની સ્થિતિમાં મોટાભાગે બદલાય છે; આમ તે એક તરફી સંદેશાવ્યવહાર સાથે અમલ કરી શકાય છે. એંગ્લુઇન, એસ્પનેસ અને આઈઝેનસ્ટેટએ દર્શાવ્યું હતું કે, કોઈપણ પ્રારંભિક રૂપરેખાંકન કે જેમાં તમામનો સમાવેશ થતો નથી, ત્રણ-સ્થિતિ અંદાજિત બહુમતી પ્રોટોકોલ ક્યાં તો માન્યતા ધરાવતા તમામ ગાંઠો અથવા ઉચ્ચ સંભાવના સાથેની ક્રિયાપ્રતિક્રિયાઓમાં માન્યતા ધરાવતા તમામ ગાંઠોમાં એકરૂપ થાય છે. વધુમાં, પસંદ કરેલ મૂલ્ય બહુમતી બિન-પ્રારંભિક મૂલ્ય હશે, જો કે તે લઘુમતી કરતાં પૂરતા માર્જિનથી વધી જાય. નીચેનું ચિત્ર નોડ્સના સમૂહ પર ત્રણ રાજ્ય પ્રોટોકોલની ઉત્ક્રાંતિ દર્શાવે છે, જ્યાં એક તૃતીયાંશ નોડ્સમાં પ્રારંભિક માન્યતા બીટ હોય છે, જ્યારે બાકીના બે તૃતીયાંશમાં પ્રારંભિક માન્યતા બીટ હોય છે. નોડ્સનો અપૂર્ણાંક (નારંગીમાં) શૂન્યથી શરૂ થાય છે, થોડા સમય માટે વધે છે, અને પછી ફરીથી શૂન્ય પર જાય છે. ઇતિહાસ વસ્તી પ્રોટોકોલ ડાના એંગ્લુઇન એટ અલ દ્વારા રજૂ કરવામાં આવ્યા હતા. ગણતરીના પ્રથમ નમૂનાઓમાંના એક તરીકે સંપૂર્ણપણે વિકેન્દ્રિત અને અત્યંત મર્યાદિત સંસાધનો ધરાવતા એજન્ટોને સામેલ કરવા માટે, દા. ત., સેન્સર નેટવર્કમાં જોવા મળતા. ત્યારથી, આ અમૂર્ત ગણતરી મોડેલને રોબોટિક્સ અને રસાયણશાસ્ત્રમાં ઉપયોગો મળ્યા. સ્વાર્મ ઇન્ટેલિજન્સ રેફરન્સ ડિસ્ટ્રિબ્યુટેડ કમ્પ્યુટિંગ પણ જુઓ