On the algebraic numbers computable by some generalized Ehrenfest urns
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 numbe...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2012-12-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/565/pdf |
| _version_ | 1827323840756187136 |
|---|---|
| author | Marie Albenque Lucas Gerin |
| author_facet | Marie Albenque Lucas Gerin |
| author_sort | Marie Albenque |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-25T02:00:05Z |
| format | Article |
| id | doaj.art-e60472d8776043bd854f374cb0767b41 |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T02:00:05Z |
| publishDate | 2012-12-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-e60472d8776043bd854f374cb0767b412024-03-07T15:27:40ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502012-12-01Vol. 14 no. 210.46298/dmtcs.565565On the algebraic numbers computable by some generalized Ehrenfest urnsMarie AlbenqueLucas GerinThis 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.https://dmtcs.episciences.org/565/pdfpopulation protocolsdistributed computing : approximation of markov chainsehrenfest[info.info-dc] computer science [cs]/distributed, parallel, and cluster computing [cs.dc] |
| spellingShingle | Marie Albenque Lucas Gerin On the algebraic numbers computable by some generalized Ehrenfest urns Discrete Mathematics & Theoretical Computer Science population protocols distributed computing : approximation of markov chains ehrenfest [info.info-dc] computer science [cs]/distributed, parallel, and cluster computing [cs.dc] |
| title | On the algebraic numbers computable by some generalized Ehrenfest urns |
| title_full | On the algebraic numbers computable by some generalized Ehrenfest urns |
| title_fullStr | On the algebraic numbers computable by some generalized Ehrenfest urns |
| title_full_unstemmed | On the algebraic numbers computable by some generalized Ehrenfest urns |
| title_short | On the algebraic numbers computable by some generalized Ehrenfest urns |
| title_sort | on the algebraic numbers computable by some generalized ehrenfest urns |
| topic | population protocols distributed computing : approximation of markov chains ehrenfest [info.info-dc] computer science [cs]/distributed, parallel, and cluster computing [cs.dc] |
| url | https://dmtcs.episciences.org/565/pdf |
| work_keys_str_mv | AT mariealbenque onthealgebraicnumberscomputablebysomegeneralizedehrenfesturns AT lucasgerin onthealgebraicnumberscomputablebysomegeneralizedehrenfesturns |