Stability of Multi-Valued Continuous Consensus11Preliminary Version, Some proofs are omitted from this version

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,...

Full description

Saved in:
Bibliographic Details
Published in:Electronic notes in theoretical computer science 2009-03, Vol.230, p.23-38
Main Authors: Davidovitch, Lior, Dolev, Shlomi, Rajsbaum, Sergio
Format: Article
Language:English
Subjects:
boolean functions
consensus
Fault-tolerance
sensors
stability
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1571-0661
1571-0661
DOI:10.1016/j.entcs.2009.02.015