[Busec] Seminar Wednesday Dec 6: The population stability problem
Yilei Chen
chenyl at bu.edu
Mon Dec 4 20:51:57 EST 2017
Title: The population stability problem
Speaker: Adam Sealfon (MIT)
Wednesday Dec 6, 2017, 10 am - 11 am.
BU Hariri Institute Seminar room. 111 Cummington St, Boston MA 02215.
We introduce a new coordination problem in distributed computing that we
call the population stability problem. A system of processors 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 processors chosen arbitrarily and (2) insert
additional processors 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.
We present a population stability protocol in a communication model that is
a synchronous variant of the population model of Angluin et al. (DISC
2007). In each round, pairs of processors selected at random meet and
exchange messages, where at least a constant fraction of processors is
matched in each round. Our protocol uses constant-size messages and O(log
log N) memory per processor. The protocol relies on a novel coloring
strategy in which the population size is encoded in the variance of the
distribution of colors. Individual processors 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.
Joint work with Shafi Goldwasser, Rafail Ostrovsky, and Alessandra Scafuro.
--
Yilei Chen
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs-mailman.bu.edu/pipermail/busec/attachments/20171204/9a1e8379/attachment.html>
More information about the Busec
mailing list