Computing with Large Populations Using InteractionsReport as inadecuate

Computing with Large Populations Using Interactions - Download this document for free, or read online. Document in PDF available to download.

1 LIX - Laboratoire d-informatique de l-École polytechnique Palaiseau 2 LIAFA - Laboratoire d-informatique Algorithmique : Fondements et Applications

Abstract : We define a general model capturing the behavior of a population of anonymous agents that interact in pairs. This model captures some of the main features of opportunistic networks, in which nodes such as the ones of a mobile ad hoc networks meet sporadically. For its reminiscence to Population Protocol, we call our model \emph{Large-Population Protocol}, or LPP. We are interested in the design of LPPs enforcing, for every $ u\in0,1$, a proportion $ u$ of the agents to be in a specific subset of marked states, when the size of the population grows to infinity; In which case, we say that the protocol \emph{computes} $ u$. We prove that, for every $ u\in0,1$, $ u$ is computable by a LPP if and only if $ u$ is algebraic. Our positive result is constructive. That is, we show how to construct, for every algebraic number $ u\in0,1$, a protocol which computes $ u$.

Author: Olivier Bournez - Pierre Fraigniaud - Xavier Koegler -



Related documents