Seminario: "Stability of Consensus Functions"

El lunes 14 a las 11:30 Sergio Rajsbaum (U. Autónoma de México) dará <br />la siguiente charla en la sala 103, Departamental II, Campus de <br />Móstoles:<br /><br />Título: "Stability of Consensus Functions"<br /><br />Joint work with:<br /> L. Davidovitch, S. Dolev (Ben-Gurion U., Israel)<br />F. Becker (Lyon), I. Rapaport (U. Chile), E. Rémila (Lyon)<br />Publications in SIROCCO'08, J. Comp. and System Sciences 2003, and<br />SIAM J. on Comp. 2007.<br /><br />Abstract<br /><br />Consider a system composed of $n$ sensors operating in synchronous<br />rounds. In each round an \emph{input vector} of sensor readings $x$<br />is produced, where the $i$-th entry of $x$ is a binary value<br />produced by the $i$-th sensor. The sequence of input vectors is<br />assumed to be \emph{smooth}: exactly one entry of the vector changes<br />from one round to the next one. The system implements a<br />fault-tolerant averaging \emph{consensus function} $f$. This<br />function returns, in each round, a representative \emph{output<br />value} $v$ of the sensor readings $x$. Assuming that at most $t$<br />entries of the vector can be erroneous, $f$ is required to return a<br />value that appears at least $t+1$ times in $x$. It is desired that <br />such a<br />function has good stability, changing its output value as few<br />times as possible. We describe results and open questions about this<br />research area.<br /><br />Como llegar: http://gsyc.es/Campus/