Stability of Multi-Valued Continuous Consensus1

Multi-valued consensus functions defined from a vector of inputs (and possibly the previous output) to a single output are investigated. The consensus functions are designed to tolerate t faulty inputs. Two classes of multi-valued consensus functions are defined, the exact value and the range value, which require the output to be one of the non-faulty inputs or in the range of the non-faulty inputs, respectively. The instability of consensus functions is examined, counting the maximal number of output changes along a geodesic path of input changes, a path in which each input is changed at most once. Lower and upper bounds for the instability of multi-valued consensus functions are presented. A new technique for obtaining such lower bounds, using edgewise simplex subdivision is presented.