Paper Info
Title
Stably Computing Order Statistics with Arithmetic Population Protocols.
Abstract
In this paper we initiate 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 Arithmetic Population Protocol (APP) model, embarking from well known Population Protocol (PP) model and inspired by two recent papers in which states are treated as integer numbers. In APP model, every agent has a state from a set Q of states, as well as a fixed number of registers (independent of size of 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 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 sample values that are stored in registers of two interacting agents.Agents can only meet in pairs via a fair scheduler and are required to eventually converge to same output value of function that protocol globally and stably computes.We present two different APPs for stably computing median of input values, initially stored on agents of 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 probabilistic scheduler, we show that our protocol stably computes 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 correct median of input with high probability in O(n^3 log{n}) interactions, assuming probabilistic scheduler and complete interaction graph. Finally we present a third APP which, for any k, stably computes k-th smallest element of input of 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 agents with respect to their input values.
Year
Venue
Field
2016
MFCS
Integer,Convergence (routing),Discrete mathematics,Population,Combinatorics,Computer science,Total order,Arithmetic,Population protocol,Probabilistic logic,Order statistic,Strongly connected component
DocType
Citations 
PageRank 
Conference
1
0.37
References 
Authors
0
4
Name
Order
Citations
PageRank
George B. Mertzios123931.68
Sotiris E. Nikoletseas21027107.41
Christoforos Raptopoulos319222.39
Paul G. Spirakis42222299.05