Computing with Large Populations Using Interactions

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 $\nu\in[0,1]$, a proportion $\nu$ 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} $\nu$. We prove that, for every $\nu\in[0,1]$, $\nu$ is computable by a LPP if and only if $\nu$ is algebraic. Our positive result is constructive. That is, we show how to construct, for every algebraic number $\nu\in[0,1]$, a protocol which computes $\nu$.
Document type :
Conference papers
Complete list of metadatas

Cited literature [32 references]  Display  Hide  Download

https://hal-polytechnique.archives-ouvertes.fr/hal-00760669
Contributor : Olivier Bournez <>
Submitted on : Tuesday, December 4, 2012 - 11:29:36 AM
Last modification on : Sunday, March 31, 2019 - 1:41:58 AM
Long-term archiving on: Saturday, December 17, 2016 - 7:42:19 PM

File

final-MFCS.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00760669, version 1

Collections

Citation

Olivier Bournez, Pierre Fraigniaud, Xavier Koegler. Computing with Large Populations Using Interactions. Mathematical Foundations of Computer Science 2012, MFCS'2012, Aug 2012, Slovakia. pp.234-246. ⟨hal-00760669⟩

Share

Metrics

Record views

353

Files downloads

213