I detta arbete fokuserar vi på en naturlig klass av populationsprotokoll vars dynamik modelleras av den diskreta versionen av Lotka-Volterra ekvationer. I sådana protokoll, när en agent a av typ (art) i interagerar med en agent b av typ (art) j med en som initiativtagare, då b typ blir i med sannolikhet P ij. I ett sådant samspel tänker vi på ett som rovdjuret, b som bytet, och typen av bytet omvandlas antingen till rovdjurets eller förblir som det är. Sådana protokoll fångar dynamiken i vissa åsikter sprida modeller och generalisera den välkända Rock-Paper-Scissors diskret dynamik. Vi anser att de parvisa interaktionerna mellan agenter som schemaläggs enhetligt på måfå. Vi börjar med att överväga konvergenstiden och visar att alla Lotka-Volterra-typ protokoll på en n-agent befolkning konvergerar till några absorberande tillstånd i tid polynom i n, w.h.p., när något par av agenter tillåts interagera. Däremot, när interaktionsgrafen är en stjärna, även Rock-Paper-Scissors protokoll kräver exponentiellt tid att konvergera. Vi studerar sedan tröskeleffekter som visas av Lotka-Volterra-typ protokoll med 3 och fler arter under interaktioner mellan något par av agenter. Vi börjar med att presentera ett enkelt 4-type protokoll där sannolikhetsskillnaden för att nå de två möjliga absorberande tillstånden kraftigt förstärks av förhållandet mellan de initiala populationerna av de två andra typerna, som är övergående, men "kontroll" konvergens. Vi bevisar sedan att Rock-Paper-Scissors protokollet når var och en av sina tre möjliga absorberande tillstånd med nästan lika stor sannolikhet, från varje konfiguration som uppfyller några sub-linjära lägre gräns på den ursprungliga storleken på varje art. Det vill säga, Rock-Paper-Scissors är ett förverkligande av ett "mynt-flipp samförstånd" i ett distribuerat system. Vissa av våra tekniker kan vara av oberoende värde.
Czyzowicz m.fl. REF har nyligen studerat relationen mellan populationsprotokoll och artmotsättning, med dynamik modellerad av diskreta Lotka-Volterra ekvationer.
On Convergence and Threshold Properties of Discrete Lotka-Volterra Population Protocols
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}