Brief Announcement: Fast Aggregation in Population Protocols

Authors Ryota Eguchi, Taisuke Izumi



PDF
Thumbnail PDF

File

LIPIcs.DISC.2017.49.pdf
  • Filesize: 304 kB
  • 3 pages

Document Identifiers

Author Details

Ryota Eguchi
Taisuke Izumi

Cite AsGet 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.
Keywords
  • population protocol
  • aggregation

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. 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.
  2. 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.
  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.
  4. Leszek Gasieniec and Grzegorz Stachowiak. Fast space optimal leader election in population protocols. arXiv preprint arXiv:1704.07649, 2017. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail