Advertisement
Published in:
2010 | OriginalPaper | Chapter
Average Long-Lived Memoryless Consensus: The Three-Value Case
Authors : Ivan Rapaport, Eric Rémila
Published in: Structural Information and Communication Complexity
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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.