Counting with Population ProtocolsReport as inadecuate




Counting with Population Protocols - Download this document for free, or read online. Document in PDF available to download.

1 UR1 - Université de Rennes 1 2 CIDRE - Confidentialité, Intégrité, Disponibilité et Répartition CentraleSupélec, Inria Rennes – Bretagne Atlantique , IRISA-D1 - SYSTÈMES LARGE ÉCHELLE 3 YALE - Department of Computer Science 4 DIONYSOS - Dependability Interoperability and perfOrmance aNalYsiS Of networkS Inria Rennes – Bretagne Atlantique , IRISA-D2 - RÉSEAUX, TÉLÉCOMMUNICATION ET SERVICES 5 ENSAI - Ecole Nationale de la Statistique et de l-Analyse de l-Information

Abstract : —The population protocol model provides theoretical foundations for analyzing the properties emerging from simple and pairwise interactions among a very large number n of anonymous agents. The problem tackled in this paper is the following one: is there an efficient population protocol that exactly counts the difference κ between the number of agents that initially and independently set their state to A and the one that initially set it to B, assuming that each agent only uses a finite set of states ? We propose a solution which guarantees with any high probability that after Olog n interactions any agent outputs the exact value of κ. Simulation results illustrate our theoretical analysis.

Keywords : -Population protocol Majority algorithm Counting problem Performance evaluation





Author: Yves Mocquard - Emmanuelle Anceaume - James Aspnes - Yann Busnel - Bruno Sericola -

Source: https://hal.archives-ouvertes.fr/



DOWNLOAD PDF




Related documents