| Abstract | dc.description.abstract | Consider a system composed of n sensors operating in synchronous
rounds. In each round an 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 smooth: exactly
one entry of the vector changes from one round to the next one.
The system implements a fault-tolerant averaging consensus function f.
This function returns, in each round, a representative 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. The instability of the system is the number of output changes
over a random sequence of input vectors.
Our first result is to design optimal instability consensus systems with
and without memory. Roughly, in the memoryless case, we show that
an optimal system is D0, that outputs 1 unless it is forced by the faulttolerance
requirement to output 0 (on vectors with t or less 1’s). For the
case of systems with memory, we show that an optimal system is D1, that
initially outputs the most common value in the input vector, and then
stays with this output unless forced by the fault-tolerance requirement
to change (i.e., a single bit of memory suffices).
Our second result is to quantify the gain factor due to memory by computing
cn(t), the number of decision changes performed by D0 per each
decision change performed by D1. If t = n
2 the system is always forced to
decide the simple majority and, in that case, memory becomes useless.
We show that the same type of phenomenon occurs when n
2 − t is constant.
Nevertheless, as soon as n
2 − t
pn, memory plays an important
stabilizing role because the ratio cn(t) grows like (pn). We also show
that this is an upper bound: cn(t) = O(pn) for every t.
Our results are average case versions of previous works where the sequence
of input vectors was assumed to be, in addition to smooth,
geodesic: the i-th entry of the input vector was allowed to change at
most once over the sequence. It thus eliminates some anomalies that
ocurred in the worst case, geodesic instability setting. | en_US |
