<div dir="ltr"><div style="font-size:12.8px">Title: The population stability problem</div><div style="font-size:12.8px"><div style="font-size:12.8px"><span style="font-size:12.8px">Speaker: </span><span style="font-size:small">Adam Sealfon</span><span style="font-size:12.8px"> (MIT)</span><br></div><div style="font-size:12.8px">Wednesday Dec 6, 2017, 10 am - 11 am. </div><div style="font-size:12.8px">BU Hariri Institute Seminar room. 111 Cummington St, Boston MA 02215.</div><div><br></div></div><div style="font-size:12.8px"><div>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. </div><div><br></div><div>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.</div><div><br></div><div><span style="font-size:12.8px">Joint work with Shafi Goldwasser, Rafail Ostrovsky, and Alessandra Scafuro.</span></div></div><div><br></div>-- <br><div class="gmail_signature"><div dir="ltr"><div>Yilei Chen</div></div></div>
</div>