Marie Albenque ; Lucas Gerin - On the algebraic numbers computable by some generalized Ehrenfest urns

dmtcs:565 - Discrete Mathematics & Theoretical Computer Science, December 4, 2012, Vol. 14 no. 2 -
On the algebraic numbers computable by some generalized Ehrenfest urns

Authors: Marie Albenque ; Lucas Gerin

    This article deals with some stochastic population protocols, motivated by theoretical aspects of distributed computing. We modelize the problem by a large urn of black and white balls from which at every time unit a fixed number of balls are drawn and their colors are changed according to the number of black balls among them. When the time and the number of balls both tend to infinity the proportion of black balls converges to an algebraic number. We prove that, surprisingly enough, not every algebraic number can be ''computed'' this way.

    Volume: Vol. 14 no. 2
    Published on: December 4, 2012
    Accepted on: June 9, 2015
    Submitted on: April 29, 2011
    Keywords: population protocols,distributed computing : approximation of Markov chains,Ehrenfest,[INFO.INFO-DC] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]
      Source : OpenAIRE Graph
    • Combinatorial methods, from enumerative topology to random discrete structures and compact data representations.; Funder: European Commission; Code: 208471

    Linked publications - datasets - softwares

    Source : ScholeXplorer IsRelatedTo DOI 10.1145/1146381.1146425
    • 10.1145/1146381.1146425
    Stably computable predicates are semilinear

    Consultation statistics

    This page has been seen 686 times.
    This article's PDF has been downloaded 447 times.