Average long-lived binary consensus: Quantifying the stabilizing role played by memory

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.We introduce the definition of instability of the system, which consists in the number of output changes over a random sequence of input vectors. We first design optimal (with respect to the instability measure) consensus systems: D0 without memory, and D1 with memory. Then we quantify the gain factor due to memory by computing cn(t), the number of decision changes performed by D0 per decision change performed by D1.