Population Stability: Regulating Size in the Presence of an Adversary
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 bounde...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Association for Computing Machinery (ACM)
2021
|
| Online Access: | https://hdl.handle.net/1721.1/129410 |
| _version_ | 1826206023056097280 |
|---|---|
| author | Goldwasser, Shafrira Ostrovsky, Rafail Scafuro, Alessandra Sealfon, Adam |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Goldwasser, Shafrira Ostrovsky, Rafail Scafuro, Alessandra Sealfon, Adam |
| author_sort | Goldwasser, Shafrira |
| collection | MIT |
| description | 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 (log2 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. |
| first_indexed | 2024-09-23T13:22:46Z |
| format | Article |
| id | mit-1721.1/129410 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T13:22:46Z |
| publishDate | 2021 |
| publisher | Association for Computing Machinery (ACM) |
| record_format | dspace |
| spelling | mit-1721.1/1294102022-10-01T14:54:16Z Population Stability: Regulating Size in the Presence of an Adversary Goldwasser, Shafrira Ostrovsky, Rafail Scafuro, Alessandra Sealfon, Adam Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science 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 (log2 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. 2021-01-13T20:16:40Z 2021-01-13T20:16:40Z 2018-07 2019-05-29T16:21:28Z Article http://purl.org/eprint/type/ConferencePaper 9781450357951 https://hdl.handle.net/1721.1/129410 Goldwasser, Shafi et al. "Population Stability: Regulating Size in the Presence of an Adversary." Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, July 2018, Egham, United Kingdom, Association for Computing Machinery, 2018. © 2018 The Authors en http://dx.doi.org/10.1145/3212734.3212747 Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Association for Computing Machinery (ACM) arXiv |
| spellingShingle | Goldwasser, Shafrira Ostrovsky, Rafail Scafuro, Alessandra Sealfon, Adam Population Stability: Regulating Size in the Presence of an Adversary |
| title | Population Stability: Regulating Size in the Presence of an Adversary |
| title_full | Population Stability: Regulating Size in the Presence of an Adversary |
| title_fullStr | Population Stability: Regulating Size in the Presence of an Adversary |
| title_full_unstemmed | Population Stability: Regulating Size in the Presence of an Adversary |
| title_short | Population Stability: Regulating Size in the Presence of an Adversary |
| title_sort | population stability regulating size in the presence of an adversary |
| url | https://hdl.handle.net/1721.1/129410 |
| work_keys_str_mv | AT goldwassershafrira populationstabilityregulatingsizeinthepresenceofanadversary AT ostrovskyrafail populationstabilityregulatingsizeinthepresenceofanadversary AT scafuroalessandra populationstabilityregulatingsizeinthepresenceofanadversary AT sealfonadam populationstabilityregulatingsizeinthepresenceofanadversary |