Population stability. Regulating size in the presence of an adversary

DOI10.1145/3212734.3212747zbMATH Open1428.68071arXiv1803.02540OpenAlexW2962922536WikidataQ130962022 ScholiaQ130962022MaRDI QIDQ5197705FDOQ5197705

Authors: Rafail Ostrovsky, Alessandra Scafuro, Adam Sealfon, Shafi Goldwasser 

Publication date: 19 September 2019

Published in: Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Abstract: We introduce a new coordination problem in distributed computing that we call the population stability problem. A system of agents each with limited memory and communication, as well as the ability to replicate and self-destruct, is subjected to attacks by a worst-case adversary that can at a bounded rate (1) delete agents chosen arbitrarily and (2) insert additional agents with arbitrary initial state into the system. The goal is perpetually to maintain a population whose size is within a constant factor of the target size $N$. The problem is inspired by the ability of complex biological systems composed of a multitude of memory-limited individual cells to maintain a stable population size in an adverse environment. Such biological mechanisms allow organisms to heal after trauma or to recover from excessive cell proliferation caused by inflammation, disease, or normal development. We present a population stability protocol in a communication model that is a synchronous variant of the population model of Angluin et al. In each round, pairs of agents selected at random meet and exchange messages, where at least a constant fraction of agents is matched in each round. Our protocol uses three-bit messages and $omega(lo{g}^{2}N)$ states per agent. We emphasize that our protocol can handle an adversary that can both insert and delete agents, a setting in which existing approximate counting techniques do not seem to apply. The protocol relies on a novel coloring strategy in which the population size is encoded in the variance of the distribution of colors. Individual agents can locally obtain a weak estimate of the population size by sampling from the distribution, and make individual decisions that robustly maintain a stable global population size.

Full work available at URL: https://arxiv.org/abs/1803.02540

Recommendations

• A survey of size counting in population protocols
• Simple and fast approximate counting and leader election in populations
• Brief Announcement
• Simple and fast approximate counting and leader election in populations
• scientific article; zbMATH DE number 6850453

zbMATH Keywords

stabilitypopulation growthpopulation protocols

Mathematics Subject Classification ID

Distributed systems (68M14)

Cited In (5)

• A survey of size counting in population protocols
• Distributed computation with continual population growth
• Controlling a population
• A combinatorial characterization of self-stabilizing population protocols
• Density-dependence as a size-independent regulatory mechanism

This page was built for publication: Population stability. Regulating size in the presence of an adversary

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5197705)