Trustful population protocols

Olivier Bournez; Jonas Lefevre; Mikaël Rabie

doi:10.1007/978-3-642-41527-2_31

Trustful population protocols

Olivier Bournez, Jonas Lefevre, Mikaël Rabie

Laboratoire d'Informatique (LIX)

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

Population protocols have been introduced by Angluin et al. as a model in which passively mobile anonymous finite-state agents stably compute a predicate of the multiset of their inputs via interactions by pairs. Stably computable predicates under this model have been characterized as exactly semi-linear predicates, that is to say exactly those definable in Presburger's arithmetic. We consider several variants of the models. In all these variants, the agents are called trustful : agents with a similar opinion that meet do not change their common opinion. We provide a characterization of the computational power of the obtained models, considering both the case when agents have finitely many states, and when agents can possibly be arbitrary Turing machines. We also provide some time complexity considerations.

Original language	English
Title of host publication	Distributed Computing - 27th International Symposium, DISC 2013, Proceedings
Pages	447-461
Number of pages	15
DOIs	https://doi.org/10.1007/978-3-642-41527-2_31
Publication status	Published - 1 Dec 2013
Event	27th International Symposium on Distributed Computing, DISC 2013 - Jerusalem, Israel Duration: 14 Oct 2013 → 18 Oct 2013

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	8205 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	27th International Symposium on Distributed Computing, DISC 2013
Country/Territory	Israel
City	Jerusalem
Period	14/10/13 → 18/10/13

Access to Document

10.1007/978-3-642-41527-2_31

Cite this

@inproceedings{f303acc1e03d4e43b8762628b325008e,

title = "Trustful population protocols",

abstract = "Population protocols have been introduced by Angluin et al. as a model in which passively mobile anonymous finite-state agents stably compute a predicate of the multiset of their inputs via interactions by pairs. Stably computable predicates under this model have been characterized as exactly semi-linear predicates, that is to say exactly those definable in Presburger's arithmetic. We consider several variants of the models. In all these variants, the agents are called trustful : agents with a similar opinion that meet do not change their common opinion. We provide a characterization of the computational power of the obtained models, considering both the case when agents have finitely many states, and when agents can possibly be arbitrary Turing machines. We also provide some time complexity considerations.",

author = "Olivier Bournez and Jonas Lefevre and Mika{\"e}l Rabie",

year = "2013",

month = dec,

day = "1",

doi = "10.1007/978-3-642-41527-2\_31",

language = "English",

isbn = "9783642415265",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "447--461",

booktitle = "Distributed Computing - 27th International Symposium, DISC 2013, Proceedings",

note = "27th International Symposium on Distributed Computing, DISC 2013 ; Conference date: 14-10-2013 Through 18-10-2013",

}

Bournez, O, Lefevre, J & Rabie, M 2013, Trustful population protocols. in Distributed Computing - 27th International Symposium, DISC 2013, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8205 LNCS, pp. 447-461, 27th International Symposium on Distributed Computing, DISC 2013, Jerusalem, Israel, 14/10/13. https://doi.org/10.1007/978-3-642-41527-2_31

Trustful population protocols. / Bournez, Olivier; Lefevre, Jonas; Rabie, Mikaël.
Distributed Computing - 27th International Symposium, DISC 2013, Proceedings. 2013. p. 447-461 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8205 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Trustful population protocols

AU - Bournez, Olivier

AU - Lefevre, Jonas

AU - Rabie, Mikaël

PY - 2013/12/1

Y1 - 2013/12/1

N2 - Population protocols have been introduced by Angluin et al. as a model in which passively mobile anonymous finite-state agents stably compute a predicate of the multiset of their inputs via interactions by pairs. Stably computable predicates under this model have been characterized as exactly semi-linear predicates, that is to say exactly those definable in Presburger's arithmetic. We consider several variants of the models. In all these variants, the agents are called trustful : agents with a similar opinion that meet do not change their common opinion. We provide a characterization of the computational power of the obtained models, considering both the case when agents have finitely many states, and when agents can possibly be arbitrary Turing machines. We also provide some time complexity considerations.

AB - Population protocols have been introduced by Angluin et al. as a model in which passively mobile anonymous finite-state agents stably compute a predicate of the multiset of their inputs via interactions by pairs. Stably computable predicates under this model have been characterized as exactly semi-linear predicates, that is to say exactly those definable in Presburger's arithmetic. We consider several variants of the models. In all these variants, the agents are called trustful : agents with a similar opinion that meet do not change their common opinion. We provide a characterization of the computational power of the obtained models, considering both the case when agents have finitely many states, and when agents can possibly be arbitrary Turing machines. We also provide some time complexity considerations.

U2 - 10.1007/978-3-642-41527-2_31

DO - 10.1007/978-3-642-41527-2_31

M3 - Conference contribution

AN - SCOPUS:84893790859

SN - 9783642415265

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 447

EP - 461

BT - Distributed Computing - 27th International Symposium, DISC 2013, Proceedings

T2 - 27th International Symposium on Distributed Computing, DISC 2013

Y2 - 14 October 2013 through 18 October 2013

ER -

Trustful population protocols

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this