License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2017.49
URN: urn:nbn:de:0030-drops-79981
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7998/
Eguchi, Ryota ;
Izumi, Taisuke
Brief Announcement: Fast Aggregation in Population Protocols
Abstract
The coalescence protocol plays an important role in the population protocol model. The conceptual structure of the protocol is for two agents holding two non-zero values a, b respectively to take a transition (a,b) -> (a+b, 0), where + is an arbitrary commutative binary operation. Obviously, it eventually aggregates the sum of all initial values. In this paper, we present a fast coalescence protocol that converges in O(sqrt(n) log^2 n) parallel time with high probability in the model with an initial leader (equivalently, the model with a base station), which achieves an substantial speed-up compared with the naive implementation taking Omega(n) time.
BibTeX - Entry
@InProceedings{eguchi_et_al:LIPIcs:2017:7998,
author = {Ryota Eguchi and Taisuke Izumi},
title = {{Brief Announcement: Fast Aggregation in Population Protocols}},
booktitle = {31st International Symposium on Distributed Computing (DISC 2017)},
pages = {49:1--49:3},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-053-8},
ISSN = {1868-8969},
year = {2017},
volume = {91},
editor = {Andr{\'e}a W. Richa},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7998},
URN = {urn:nbn:de:0030-drops-79981},
doi = {10.4230/LIPIcs.DISC.2017.49},
annote = {Keywords: population protocol, aggregation}
}
|
Keywords: |
|
population protocol, aggregation |
|
Collection: |
|
31st International Symposium on Distributed Computing (DISC 2017) |
|
Issue Date: |
|
2017 |
|
Date of publication: |
|
12.10.2017 |
