2015 · 21 citations · 7 references
Natural SciencesComputer ScienceMathematicsCombinatoricsDistributed SystemsProbability TheoryMulti-agent SystemsProbabilistic CombinatoricsAgent-based Population ModelsAnonymous Communication Protocols
The population protocol model provides theoretical foundations for analyzing the properties emerging from simple and pair wise interactions among a very large number n of anonymous agents. The problem tackled in this paper is the following one: is there an efficient population protocol that exactly counts the difference k between the number of agents that initially and independently set their state to "A" and the one that initially set it to "B", assuming that each agent only uses a finite set of states? We propose a solution which guarantees with any high probability that after O(log n) interactions any agent outputs the exact value of k. Simulation results illustrate our theoretical analysis.
7
Computation in networks of passively mobile finite-state sensors
Dana Angluin, James Aspnes, Zoë Diamadi et al. · Distributed Computing · 2005 · 542 citations
The computational power of population protocols
Dana Angluin, James Aspnes, David Eisenstat et al. · Distributed Computing · 2007 · 272 citations
An Introduction to Population Protocols.
James Aspnes, Eric Ruppert · 2007 · 109 citations