Name
Abstract | ||
|---|---|---|
We study strategies that minimize the instability of a fault-tolerant consensus system. More precisely, we find the strategy than minimizes the number of output changes over a random walk sequence of input vectors (where each component of the vector corresponds to a particular sensor reading). We analyze the case where each sensor can read three possible inputs. The proof of this result appears to be much more complex than the proof of the binary case (previous work). In the binary case the problem can be reduced to a minimal cut in a graph. We succeed in three dimensions by using the fact that an auxiliary graph (projected graph) is planar. For four and higher dimensions this auxiliary graph is not planar anymore and the problem remains open. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1007/978-3-642-13284-1_10 | SIROCCO |
Keywords | Field | DocType |
possible input,minimal cut,particular sensor reading,three-value case,output change,projected graph,average long-lived memoryless consensus,fault-tolerant consensus system,binary case,input vector,auxiliary graph,higher dimension,three dimensions,random walk,fault tolerant | Strength of a graph,Discrete mathematics,Combinatorics,Random walk,String graph,Null graph,Graph bandwidth,Voltage graph,Mathematics,Planar graph,Complement graph | Conference |
Volume | ISSN | ISBN |
6058 | 0302-9743 | 3-642-13283-9 |
Citations | PageRank | References |
3 | 0.47 | 11 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ivan Rapaport | 1 | 199 | 21.93 |
| Eric Rémila | 2 | 329 | 45.22 |