Document Open Access Logo

Stably Computing Order Statistics with Arithmetic Population Protocols

Authors George B. Mertzios, Sotiris E. Nikoletseas, Christoforos L. Raptopoulos, Paul G. Spirakis



PDF
Thumbnail PDF

File

LIPIcs.MFCS.2016.68.pdf
  • Filesize: 0.52 MB
  • 14 pages

Document Identifiers

Author Details

George B. Mertzios
Sotiris E. Nikoletseas
Christoforos L. Raptopoulos
Paul G. Spirakis

Cite AsGet BibTex

George B. Mertzios, Sotiris E. Nikoletseas, Christoforos L. Raptopoulos, and Paul G. Spirakis. Stably Computing Order Statistics with Arithmetic Population Protocols. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 68:1-68:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.MFCS.2016.68

Abstract

In this paper we initiate the study of populations of agents with very limited capabilities that are globally able to compute order statistics of their arithmetic input values via pair-wise meetings. To this extent, we introduce the Arithmetic Population Protocol (APP) model, embarking from the well known Population Protocol (PP) model and inspired by two recent papers in which states are treated as integer numbers. In the APP model, every agent has a state from a set Q of states, as well as a fixed number of registers (independent of the size of the population), each of which can store an element from a totally ordered set S of samples. Whenever two agents interact with each other, they update their states and the values stored in their registers according to a joint transition function. This transition function is also restricted; it only allows (a) comparisons and (b) copy / paste operations for the sample values that are stored in the registers of the two interacting agents. Agents can only meet in pairs via a fair scheduler and are required to eventually converge to the same output value of the function that the protocol globally and stably computes. We present two different APPs for stably computing the median of the input values, initially stored on the agents of the population. Our first APP, in which every agent has 3 registers and no states, stably computes (with probability 1) the median under any fair scheduler in any strongly connected directed (or connected undirected) interaction graph. Under the probabilistic scheduler, we show that our protocol stably computes the median in O(n^6) number of interactions in a connected undirected interaction graph of n agents. Our second APP, in which every agent has 2 registers and O(n^2 log{n}) states, computes to the correct median of the input with high probability in O(n^3 log{n}) interactions, assuming the probabilistic scheduler and the complete interaction graph. Finally we present a third APP which, for any k, stably computes the k-th smallest element of the input of the population under any fair scheduler and in any strongly connected directed (or connected undirected) interaction graph. In this APP every agent has 2 registers and n states. Upon convergence every agent has a different state; all these states provide a total ordering of the agents with respect to their input values.
Keywords
  • arithmetic population protocols
  • order statistics
  • median
  • k-minimum element

Metrics

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

References

  1. Dan Alistarh, Rati Gelashvili, and Milan Vojnovic. Fast and exact majority in population protocols. In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing (PODC), pages 47-56, 2015. Google Scholar
  2. Dana Angluin, James Aspnes, Zoë Diamadi, Michael J. Fischer, and René Peralta. Computation in networks of passively mobile finite-state sensors. Distributed Computing, 18:235-253, 2006. Google Scholar
  3. Dana Angluin, James Aspnes, and David Eisenstat. Stably computable predicates are semilinear. In Proceedings of the 25th Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 292-299, 2006. Google Scholar
  4. Dana Angluin, James Aspnes, and David Eisenstat. A simple population protocol for fast robust approximate majority. Distributed Computing, 21(2):87-102, 2008. Google Scholar
  5. James Aspnes and Eric Ruppert. An introduction to population protocols. In Benoît Garbinato, Hugo Miranda, and Luís Rodrigues, editors, Middleware for Network Eccentric and Mobile Applications, pages 97-120. Springer-Verlag, 2009. Google Scholar
  6. Matthew Cook, David Soloveichik, Erik Winfree, and Jehoshua Bruck. Programmability of chemical reaction networks. In Anne Condon, David Harel, Joost N. Kok, Arto Salomaa, and Erik Winfree, editors, Algorithmic Bioprocesses, Natural Computing Series, pages 543-584. Springer Berlin Heidelberg, 2009. URL: http://dx.doi.org/10.1007/978-3-540-88869-7_27.
  7. Fabian Kuhn, Thomas Locher, and Stefan Schmid. Distributed computation of the mode. In Proceedings of the 27th Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 15-24, 2008. Google Scholar
  8. Thomas G. Kurtz. Approximation of Population Processes. Society for Industrial and Applied Mathematics, 1987. Google Scholar
  9. George B. Mertzios, Sotiris E. Nikoletseas, Christoforos L. Raptopoulos, and Paul G. Spirakis. Determining majority in networks with local interactions and very small local memory. In Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP), volume 1, pages 871-882, 2014. Google Scholar
  10. Othon Michail, Ioannis Chatzigiannakis, and Paul G. Spirakis. New Models for Population Protocols. Synthesis Lectures on Distributed Computing Theory. Morgan &Claypool Publishers, 2011. Google Scholar
  11. Yves Mocquard, Emmanuelle Anceaume, James Aspnes, Yann Busnel, and Bruno Sericola. Counting with population protocols. In Proceedings of the 14th International Symposium on Network Computing and Applications (NCA), pages 35-42, 2015. Google Scholar
  12. Prasad Tetali and Peter Winkler. On a random walk problem arising in self-stabilizing token management. In Proceedings of the 10th Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 273-280, 1991. 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