Abstract-The computational model of population protocols is a formalism that allows the analysis of properties emerging from simple and pairwise interactions among a very large number of anonymous finite-state agents. Significant work has been done so far to determine which problems are solvable in this model and at which cost in terms of states used by the agents and time needed to converge. The problem tackled in this paper is the population proportion problem: each agent starts independently from each other in one of two states, say A or B, and the objective is for each agent to determine the proportion of agents that initially started in state A, assuming that each agent only uses a finite set of states, and does not know the number n of agents. We pro pose a solution which guarantees that in presence of a uniform probabilistic scheduler every agent outputs the population proportion with any precision c: E (0,1) with any high probability after having interacted O(log n ) times. The number of states maintained by every agent is optimal and is equal to 2i3/(4c:)l + 1. Finally, we show that our solution is optimal in time and space to solve the counting problem, a generalization of the proportion problem. Finally, simulation results illustrate our theoretical analysis. Keywords Population protocols ; Proportion ; Majority ; Count ing ; Performance evaluation. In 2004 , Angluin et a1. [4] have proposed a model that allows the analysis of emergent global properties based on pair wise interactions. This model , named the population protocol , provides minimalist assumptions on the computational power of the agents : agents are finite-state automata , identically programmed , with no identity , unaware of the population size n, and they progress in their computation through random pairwise interactions. The objective of this model is to ulti mately converge to a state from wh ich the sought property can be derived from any agent [8] . Examples of systems whose behavior can be modeled by population protocols range from molecule interactions of a chemical process to sensor networks in which agents , which are small devices embedded on animals , interact each time two animals are in the same radio range. A considerable amount of work has been done so far to determine which properties can emerge from pair wise interactions between finite-state agents , together with the derivation of lower bounds on the time and space needed to reach such properties (e.g. , 978-1-5090-3216-7/16/$31.00 @2016 IEEE 216 each other in one of two input states , say A and B , and the objective for each agent is to eventually output yes if a majority of agents started their execution in input state A and no otherwise. Section I V provides an overview of the results recently obtained for the majority task. In this paper , we focus on a related but more general question. Namely , instead of having each agent answer yes if a majority of agents initially started their execution in input state A, one may ask the following question : "Is it feasible for each agent to compute quickly and with any high precision the proportion of agents that started in the input state A?". Answering such a question is very important in the con text of , for example , infectious-disease surveillance of large scale animal populations. In this context , different kinds of alerts could be triggered according to the infected population proportion (e.g., Alert 1 is triggered if less than 0. 05% of the population is infected , Alert 2 if this proportion lies in [0. 05%,3. 0%), Alert 3 if it lies in [3. 0%,10. 0%), and so on ... ). Input state A would manifest an excessive tem perature of an animal while input state B would indicate a safe temperature. By relying on the properties exhibited by our population protocol (convergence time logarithmic in the population size and memory space proportional to the sought precision) , one can easily implement a regular and self autonomous monitoring of large-scale populations. We answer affirmatively to this question , and we propose a population protocol that allows each agent to converge to a state which , when queried , provides the proportion of agents that started in a given input state. Specifically , each agent is a (2m + 1 )-finite state machine , m ?: 1 , where m is the value associated to input state A and -m is the one associated to input state B. Each agent starts its execution with m or -m , and each pair of agents that meet , adopt the average of their values (or as close as they can get when values are restricted to integers , as will be clarified in Section V). The rationale of this method [3] , [16] , [1] is to preserve the sum of the initial values , and after a small number of pairwise interactions , to ensure that every agent converges with high probability to a state from which it derives the proportion of agents that started in a given state. Technically , our protocol guarantees that each agent is capable of computing with any precision c E (0, 1 ) the proportion of agents that initially started in a specific input state by using 213/ (4c) l + 1 states. This is achieved in no more than (-2In c + 8. 47 In n -13. 291n 0 -2.88) in teractions with probability at least 1 -0, for any 0 E (0,1).
In a more recent work REF , we have provided an analysis which shows that when nodes can only manipulate integers, then our solution to both the counting problem and the proportion one are optimal both in time and space.
Optimal proportion computation with population protocols
2016 IEEE 15th International Symposium on Network Computing and Applications (NCA)
2016 IEEE 15th International Symposium on Network Computing and Applications (NCA)
Mathematics Computer Science