Abstract | ||
---|---|---|
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. |
Year | DOI | Venue |
---|---|---|
2009 | 10.1016/j.entcs.2009.02.015 | Electronic Notes in Theoretical Computer Science |
Keywords | DocType | Volume |
Fault-tolerance,sensors,boolean functions,consensus,stability | Journal | 230 |
ISSN | Citations | PageRank |
1571-0661 | 3 | 0.44 |
References | Authors | |
7 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Lior Davidovitch | 1 | 20 | 2.97 |
Shlomi Dolev | 2 | 2962 | 260.61 |
Sergio Rajsbaum | 3 | 1367 | 115.89 |