Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, Epiciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation
Conference papers

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 metadata

Cited literature [32 references]  Display  Hide  Download

https://hal-polytechnique.archives-ouvertes.fr/hal-00760669
Contributor : Olivier Bournez Connect in order to contact the contributor
Submitted on : Tuesday, December 4, 2012 - 11:29:36 AM
Last modification on : Friday, May 13, 2022 - 10:18:05 PM
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

201

Files downloads

229