Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Efficient assignment of identities in anonymous populations

Gasieniec, Leszek ; Jansson, Jesper LU ; Levcopoulos, Christos LU orcid and Lingas, Andrzej LU (2025) In Information and Computation 303.
Abstract
We consider the fundamental problem of assigning distinct labels to agents in the
probabilistic model of population protocols. Our protocols operate under the assumption
that the size n of the population is embedded in the transition function. W.h.p. (with
high probability), they are silent, i.e., eventually each agent reaches its nal state and
remains in it forever, and they are safe, i.e., never change a label that has already been
assigned to an agent. We provide efficient protocols for this problem complemented with
tight lower bounds. Our fast labeling protocol uses only O((n logn)/ε) interactions w.h.p.,
(2 + ε)n + O(na) states, and the label range [1,(1 + ε)n], where 1 ≥ ε > 0 and 0 < a <... (More)
We consider the fundamental problem of assigning distinct labels to agents in the
probabilistic model of population protocols. Our protocols operate under the assumption
that the size n of the population is embedded in the transition function. W.h.p. (with
high probability), they are silent, i.e., eventually each agent reaches its nal state and
remains in it forever, and they are safe, i.e., never change a label that has already been
assigned to an agent. We provide efficient protocols for this problem complemented with
tight lower bounds. Our fast labeling protocol uses only O((n logn)/ε) interactions w.h.p.,
(2 + ε)n + O(na) states, and the label range [1,(1 + ε)n], where 1 ≥ ε > 0 and 0 < a < 1,
while our nearly state-optimal protocol uses only n + 5
√n + O(log logn) states, the label
range [1,n], and w.h.p., O(n3) interactions. (Less)
Please use this url to cite or link to this publication:
author
; ; and
organization
publishing date
type
Contribution to journal
publication status
published
subject
in
Information and Computation
volume
303
article number
105265
publisher
Elsevier
external identifiers
  • scopus:85214705267
ISSN
1090-2651
DOI
10.1016/j.ic.2025.105265
language
English
LU publication?
yes
id
8dd6132f-9d76-42b2-8aa5-6f1c65d9c214
date added to LUP
2025-01-14 16:28:26
date last changed
2025-04-04 15:16:42
@article{8dd6132f-9d76-42b2-8aa5-6f1c65d9c214,
  abstract     = {{We consider the fundamental problem of assigning distinct labels to agents in the<br/>probabilistic model of population protocols. Our protocols operate under the assumption<br/>that the size n of the population is embedded in the transition function. W.h.p. (with<br/>high probability), they are silent, i.e., eventually each agent reaches its nal state and<br/>remains in it forever, and they are safe, i.e., never change a label that has already been<br/>assigned to an agent. We provide efficient protocols for this problem complemented with<br/>tight lower bounds. Our fast labeling protocol uses only O((n logn)/ε) interactions w.h.p.,<br/>(2 + ε)n + O(na) states, and the label range [1,(1 + ε)n], where 1 ≥ ε &gt; 0 and 0 &lt; a &lt; 1,<br/>while our nearly state-optimal protocol uses only n + 5<br/>√n + O(log logn) states, the label<br/>range [1,n], and w.h.p., O(n3) interactions.}},
  author       = {{Gasieniec, Leszek and Jansson, Jesper and Levcopoulos, Christos and Lingas, Andrzej}},
  issn         = {{1090-2651}},
  language     = {{eng}},
  publisher    = {{Elsevier}},
  series       = {{Information and Computation}},
  title        = {{Efficient assignment of identities in anonymous populations}},
  url          = {{http://dx.doi.org/10.1016/j.ic.2025.105265}},
  doi          = {{10.1016/j.ic.2025.105265}},
  volume       = {{303}},
  year         = {{2025}},
}