Seminario: "Stability of Consensus Functions"

El lunes 14 a las 11:30 Sergio Rajsbaum (U. Autónoma de México) dará
la siguiente charla en la sala 103, Departamental II, Campus de
Móstoles:

Título: "Stability of Consensus Functions"

Joint work with:
L. Davidovitch, S. Dolev (Ben-Gurion U., Israel)
F. Becker (Lyon), I. Rapaport (U. Chile), E. Rémila (Lyon)
Publications in SIROCCO'08, J. Comp. and System Sciences 2003, and
SIAM J. on Comp. 2007.

Abstract

Consider a system composed of $n$ sensors operating in synchronous
rounds. In each round an \emph{input vector} of sensor readings $x$
is produced, where the $i$-th entry of $x$ is a binary value
produced by the $i$-th sensor. The sequence of input vectors is
assumed to be \emph{smooth}: exactly one entry of the vector changes
from one round to the next one. The system implements a
fault-tolerant averaging \emph{consensus function} $f$. This
function returns, in each round, a representative \emph{output
value} $v$ of the sensor readings $x$. Assuming that at most $t$
entries of the vector can be erroneous, $f$ is required to return a
value that appears at least $t+1$ times in $x$. It is desired that
such a
function has good stability, changing its output value as few
times as possible. We describe results and open questions about this
research area.

Como llegar: http://gsyc.es/Campus/