Sammanfattning Snabba algoritmer presenteras för att utföra beräkningar i en probabilistisk populationsmodell. Detta är en variant av standardpopulationen protokoll modell, där finita-state agenter interagerar i par under kontroll av en motståndare schemaläggare, där alla par är lika sannolikt att väljas för varje interaktion. Det visas att när en unik ledare agent tillhandahålls i den ursprungliga populationen, befolkningen kan simulera en virtuell register maskin med hög sannolikhet där standard aritmetiska operationer som jämförelse, addition, subtraktion, och multiplikation och division av konstanter kan simuleras i O(n log 5 n) interaktioner med hjälp av en enkel registerrepresentation eller i O(n log 2 n) interaktioner med hjälp av en mer sofistikerad representation som kräver en extra O(n log O(1) n)-interaktion initialisering steg. Den centrala metoden är den omfattande användningen av epidemier för att sprida information från och till ledaren, kombinerat med en epidemibaserad fasklocka som används för att upptäcka när dessa epidemier sannolikt kommer att vara fullständiga. Tillämpningar inkluderar en minskning av kostnaden för att beräkna en semilinjär predikat till O(n log 5 n) interaktioner från den tidigare mest kända gränsen av O(n 2 log n) interaktioner och simulering av en LOG-SPACE Turing maskin med hjälp av O(n log 2 n) interaktioner per steg efter en inledande O(n log O(1) n)-interaktion startfas.
I ett mycket tidigt exempel, Angluin et al. REF visade att med en förvald unik ledare kan alla semilinjära predikat beräknas i ett subkvadratiskt förväntat antal interaktioner med hög sannolikhet [(i synnerhet i interaktion med O(n log 5 n).
Fast computation by population protocols with a leader
{'venue': 'Distributed Computing', 'journal': 'Distributed Computing', 'mag_field_of_study': ['Computer Science']}