Skip to main content

Research Repository

Advanced Search

Stably computing order statistics with arithmetic population protocols

Mertzios, G.B.; Nikoletseas, S.E.; Raptopoulos, C.L.; Spirakis, P.G.

Stably computing order statistics with arithmetic population protocols Thumbnail


Authors

S.E. Nikoletseas

C.L. Raptopoulos

P.G. Spirakis



Contributors

P. Faliszewski
Editor

A. Muscholl
Editor

R. Niedermeier
Editor

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.

Citation

Mertzios, G., Nikoletseas, S., Raptopoulos, C., & Spirakis, P. (2016). Stably computing order statistics with arithmetic population protocols. In P. Faliszewski, A. Muscholl, & R. Niedermeier (Eds.), 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016) (68:1-68:14). https://doi.org/10.4230/lipics.mfcs.2016.68

Conference Name 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016).
Conference Location Krakow, Poland
Start Date Aug 22, 2016
End Date Aug 26, 2016
Acceptance Date Jun 5, 2016
Online Publication Date Aug 1, 2016
Publication Date Aug 19, 2016
Deposit Date Jun 12, 2016
Publicly Available Date Mar 28, 2024
Pages 68:1-68:14
Series Title Leibniz international proceedings in informatics
Series Number 58
Series ISSN 1868-8969
Book Title 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016).
DOI https://doi.org/10.4230/lipics.mfcs.2016.68
Public URL https://durham-repository.worktribe.com/output/1150283

Files






You might also like



Downloadable Citations