Abstract-Den beräkningsmodell av population protokoll är en formalism som gör det möjligt att analysera egenskaper som uppstår från enkla och parvisa interaktioner bland ett mycket stort antal anonyma finita-state agenter. Betydande arbete har hittills gjorts för att fastställa vilka problem som är möjliga att lösa i denna modell och till vilka kostnader i form av stater som används av agenter och tid som behövs för att konvergera. Det problem som behandlas i detta dokument är befolkningsandelsproblemet: varje agent börjar oberoende av varandra i en av två stater, till exempel A eller B, och målet är att varje agent ska bestämma andelen agenter som ursprungligen startade i stat A, förutsatt att varje agent endast använder en ändlig uppsättning stater, och inte känner till antalet n agenter. Vi föreslår en lösning som garanterar att i närvaro av en enhetlig probabilistisk schemaläggare varje agent utdata befolkningen proportion med någon precision c: E (0,1) med någon hög sannolikhet efter att ha interagerat O (log n ) gånger. Antalet tillstånd som upprätthålls av varje agens är optimalt och är lika med 2i3/(4c:)l + 1. Slutligen visar vi att vår lösning är optimal i tid och rum för att lösa räkneproblemet, en generalisering av proportionproblemet. Slutligen illustrerar simuleringsresultaten vår teoretiska analys. Nyckelord Befolkningsprotokoll ; Proportion ; Majoritet ; Counting ; Prestandautvärdering. År 2004, Angluin et a1. [4] har föreslagit en modell som gör det möjligt att analysera framväxande globala egenskaper baserat på parvisa interaktioner. Denna modell, namngivna befolkningen protokoll, ger minimalistiska antaganden om beräkningskraften hos agenterna : agenter är ändliga-state automata, identiskt programmerad, utan identitet, omedveten om befolkningens storlek n, och de fortskrider i sin beräkning genom slumpmässiga parvisa interaktioner. Målet med denna modell är att ulti mately konvergera till en stat från vilken ich den sökta egendomen kan härledas från någon agent [8]. Exempel på system vars beteende kan modelleras av population protokoll sträcker sig från molekyl växelverkan av en kemisk process till sensornätverk där agenter, som är små enheter inbäddade på djur, interagerar varje gång två djur är i samma radioområde. En betydande mängd arbete har gjorts hittills för att avgöra vilka egenskaper kan uppstå från par kloka interaktioner mellan finita-state agenter, tillsammans med härledning av lägre gränser på den tid och utrymme som behövs för att nå sådana egenskaper (t.ex. , 978-1-5090-3216-7/16/$31.00 @2016 IEEE 216 varandra i ett av två input stater, säger A och B, och målet för varje agent är att så småningom producera ja om en majoritet av agenter började sin avrättning i input tillstånd A och inget annat. I avsnitt I V ges en översikt över de resultat som nyligen uppnåtts för majoritetsuppgiften. I detta dokument fokuserar vi på en relaterad men mer allmän fråga. Nämligen, Istället för att ha varje agent svara ja om en majoritet av agenter började sin avrättning i input tillstånd A, kan man ställa följande fråga: "Är det möjligt för varje agent att beräkna snabbt och med någon hög precision andelen agenter som började i input tillstånd A?". Att besvara en sådan fråga är mycket viktigt i texten om t.ex. övervakning av smittsamma sjukdomar hos stora djurpopulationer. I detta sammanhang kan olika typer av varningar utlösas beroende på den infekterade befolkningens andel (t.ex., Alert 1 utlöses om mindre än 0. 05% av befolkningen är infekterad, Alert 2 om denna andel ligger i [0. Femtiofem procent. 0%), Varning 3 om den ligger i [3. 0%, 10. 0%), och så vidare... ). Inmatningstillstånd A skulle manifestera en överdriven tem perature av ett djur medan ingångstillstånd B skulle indikera en säker temperatur. Genom att förlita sig på de egenskaper som visas av vårt population protokoll (konvergenstid logaritmisk i befolkningens storlek och minne utrymme proportionell mot den eftersträvade precisionen), kan man enkelt genomföra en regelbunden och självständig övervakning av stora populationer. Vi svarar ja på denna fråga, och vi föreslår en population protokoll som tillåter varje agent att konvergera till ett tillstånd som, När frågas, ger andelen agenter som började i ett givet inmatningstillstånd. Specifikt, varje agent är en (2m + 1 )-finita tillstånd maskin, m?: 1, där m är det värde som är förknippat med indatatillstånd A och -m är det som är förknippat med indatatillstånd B. Varje agent börjar sin utförande med m eller -m, Och varje par av agenter som uppfyller, Anta genomsnittet av sina värden (eller så nära som de kan få när värden begränsas till heltal, Som kommer att klargöras i avsnitt V). Den logiska grunden för denna metod [3], [16], [1] är att bevara summan av de ursprungliga värdena, och efter ett litet antal parvisa interaktioner, För att säkerställa att varje agent konvergerar med hög sannolikhet till ett tillstånd som det härrör andelen agenter som startade i ett givet tillstånd. Tekniskt sett garanterar vårt protokoll att varje agent är kapabel att beräkna med någon precision c E (0, 1 ) andelen agenter som ursprungligen startade i ett specifikt inmatningstillstånd med hjälp av 213/ (4c) l + 1 tillstånd. Detta uppnås inte mer än (-2Inc + 8. 47 I n -13. 291n 0 -2,88 i aktioner med sannolikhet minst 1 -0, för varje 0 E (0,1).
I ett nyare arbete REF, Vi har tillhandahållit en analys som visar att när noder bara kan manipulera heltal, då vår lösning på både räkna problem och andelen man är optimala både i tid och rum.
Optimal proportion computation with population protocols
{'venue': '2016 IEEE 15th International Symposium on Network Computing and Applications (NCA)', 'journal': '2016 IEEE 15th International Symposium on Network Computing and Applications (NCA)', 'mag_field_of_study': ['Mathematics', 'Computer Science']}