Efficient Assignment of Identities in Anonymous Populations
Gasieniec, Leszek ; Jansson, Jesper LU ; Levcopoulos, Christos LU
and Lingas, Andrzej
LU
(2022)
25th International Conference on Principles of Distributed Systems (OPODIS 2021)
In Leibniz International Proceedings in Informatics (LIPIcs)
217.
p.1-21
- 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. Their efficiency is expressed in terms of the number of states utilized by agents, the size of the range from which the labels are drawn, and the expected number of interactions required by our solutions. Our primary goal is to provide efficient protocols for this fundamental problem complemented with tight lower bounds in all the three aspects. W.h.p. (with high probability), our labeling protocols are silent, i.e., eventually each agent reaches its final state and remains in it forever, and they... (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. Their efficiency is expressed in terms of the number of states utilized by agents, the size of the range from which the labels are drawn, and the expected number of interactions required by our solutions. Our primary goal is to provide efficient protocols for this fundamental problem complemented with tight lower bounds in all the three aspects. W.h.p. (with high probability), our labeling protocols are silent, i.e., eventually each agent reaches its final state and remains in it forever, and they are safe, i.e., never update the label assigned to any single agent. We first present a silent w.h.p. and safe labeling protocol that draws labels from the range [1,2n]. Both the number of interactions required and the number of states used by the protocol are asymptotically optimal, i.e., O(n log n) w.h.p. and O(n), respectively. Next, we present a generalization of the protocol, where the range of assigned labels is [1,(1+ε) n]. The generalized protocol requires O(n log n / ε) interactions in order to complete the assignment of distinct labels from [1,(1+ε) n] to the n agents, w.h.p. It is also silent w.h.p. and safe, and uses (2+ε)n+O(n^c) states, for any positive c < 1. On the other hand, we consider the so-called pool labeling protocols that include our fast protocols. We show that the expected number of interactions required by any pool protocol is ≥ (n²)/(r+1), when the labels range is 1,… , n+r < 2n. Furthermore, we provide a protocol which uses only n+5√ n +O(n^c) states, for any c < 1, and draws labels from the range 1,… ,n. The expected number of interactions required by the protocol is O(n³). Once a unique leader is elected it produces a valid labeling and it is silent and safe. On the other hand, we show that (even if a unique leader is given in advance) any silent protocol that produces a valid labeling and is safe with probability > 1-(1/n), uses ≥ n+√{(n-1)/2}-1 states. Hence, our protocol is almost state-optimal. We also present a generalization of the protocol to include a trade-off between the number of states and the expected number of interactions. Finally, we show that for any silent and safe labeling protocol utilizing n+t < 2n states, the expected number of interactions required to achieve a valid labeling is ≥ (n²)/(t+1). (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/a22f1cd9-7271-4b5b-a7e7-de80f8bda353
- author
- Gasieniec, Leszek
; Jansson, Jesper
LU
; Levcopoulos, Christos
LU
and Lingas, Andrzej
LU
- organization
- publishing date
- 2022
- type
- Chapter in Book/Report/Conference proceeding
- publication status
- published
- subject
- host publication
- 25th International Conference on Principles of Distributed Systems (OPODIS 2021)
- series title
- Leibniz International Proceedings in Informatics (LIPIcs)
- volume
- 217
- article number
- 12
- pages
- 21 pages
- publisher
- Schloss Dagstuhl - Leibniz-Zentrum für Informatik
- conference name
- 25th International Conference on Principles of Distributed Systems (OPODIS 2021)
- conference dates
- 2021-12-13 - 2021-12-15
- external identifiers
-
- scopus:85127423813
- ISBN
- 978-3-95977-219-8
- DOI
- 10.4230/LIPIcs.OPODIS.2021.12
- language
- English
- LU publication?
- yes
- id
- a22f1cd9-7271-4b5b-a7e7-de80f8bda353
- date added to LUP
- 2022-02-28 10:47:33
- date last changed
- 2022-04-26 05:11:45
@inproceedings{a22f1cd9-7271-4b5b-a7e7-de80f8bda353,
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. Their efficiency is expressed in terms of the number of states utilized by agents, the size of the range from which the labels are drawn, and the expected number of interactions required by our solutions. Our primary goal is to provide efficient protocols for this fundamental problem complemented with tight lower bounds in all the three aspects. W.h.p. (with high probability), our labeling protocols are silent, i.e., eventually each agent reaches its final state and remains in it forever, and they are safe, i.e., never update the label assigned to any single agent. We first present a silent w.h.p. and safe labeling protocol that draws labels from the range [1,2n]. Both the number of interactions required and the number of states used by the protocol are asymptotically optimal, i.e., O(n log n) w.h.p. and O(n), respectively. Next, we present a generalization of the protocol, where the range of assigned labels is [1,(1+ε) n]. The generalized protocol requires O(n log n / ε) interactions in order to complete the assignment of distinct labels from [1,(1+ε) n] to the n agents, w.h.p. It is also silent w.h.p. and safe, and uses (2+ε)n+O(n^c) states, for any positive c < 1. On the other hand, we consider the so-called pool labeling protocols that include our fast protocols. We show that the expected number of interactions required by any pool protocol is ≥ (n²)/(r+1), when the labels range is 1,… , n+r < 2n. Furthermore, we provide a protocol which uses only n+5√ n +O(n^c) states, for any c < 1, and draws labels from the range 1,… ,n. The expected number of interactions required by the protocol is O(n³). Once a unique leader is elected it produces a valid labeling and it is silent and safe. On the other hand, we show that (even if a unique leader is given in advance) any silent protocol that produces a valid labeling and is safe with probability > 1-(1/n), uses ≥ n+√{(n-1)/2}-1 states. Hence, our protocol is almost state-optimal. We also present a generalization of the protocol to include a trade-off between the number of states and the expected number of interactions. Finally, we show that for any silent and safe labeling protocol utilizing n+t < 2n states, the expected number of interactions required to achieve a valid labeling is ≥ (n²)/(t+1).}},
author = {{Gasieniec, Leszek and Jansson, Jesper and Levcopoulos, Christos and Lingas, Andrzej}},
booktitle = {{25th International Conference on Principles of Distributed Systems (OPODIS 2021)}},
isbn = {{978-3-95977-219-8}},
language = {{eng}},
pages = {{1--21}},
publisher = {{Schloss Dagstuhl - Leibniz-Zentrum für Informatik}},
series = {{Leibniz International Proceedings in Informatics (LIPIcs)}},
title = {{Efficient Assignment of Identities in Anonymous Populations}},
url = {{http://dx.doi.org/10.4230/LIPIcs.OPODIS.2021.12}},
doi = {{10.4230/LIPIcs.OPODIS.2021.12}},
volume = {{217}},
year = {{2022}},
}