LIPIcs.DISC.2017.49.pdf
- Filesize: 304 kB
- 3 pages
Document
Brief Announcement: Fast Aggregation in Population Protocols
Authors
-
Part of:
Volume:
31st International Symposium on Distributed Computing (DISC 2017)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Symposium on Distributed Computing (DISC) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2017-10-12
Cite As Get BibTex
Ryota Eguchi and Taisuke Izumi. Brief Announcement: Fast Aggregation in Population Protocols. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 49:1-49:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.DISC.2017.49
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.
Subject Classification
Keywords
- population protocol
- aggregation
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Dan Alistarh, James Aspnes, David Eisenstat, Rati Gelashvili, and Ronald L Rivest. Time-space trade-offs in population protocols. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2560-2579. SIAM, 2017. URL: http://dx.doi.org/10.1137/1.9781611974782.169.
- Dana Angluin, James Aspnes, Zoë Diamadi, MichaelJ. Fischer, and Rene Peralta. Computation in networks of passively mobile finite-state sensors. Distributed Computing, 18(4):235-253, 2006. URL: http://dx.doi.org/10.1007/s00446-005-0138-3.
- Dana Angluin, James Aspnes, and David Eisenstat. Fast computation by population protocols with a leader. Distributed Computing, 21(3):183-199, September 2008. URL: http://dx.doi.org/10.1007/s00446-008-0067-z.
-
Leszek Gasieniec and Grzegorz Stachowiak. Fast space optimal leader election in population protocols. arXiv preprint arXiv:1704.07649, 2017.
