1999 · 33 citations · 0 references
We study the propagation of information in a network in the presence of permanent faults, to detect the patterns of initial faults which may lead the entire system to fail. Such patterns, called dynamos, have been already studied in different contexts and topologies, and under different laws of fault propagation. In our model each node assumes a new state according to the majority of the states of its neighbours. We investigate dynamos for networks of the butterfly family, estabilishing lower and upper bounds on their cardinality. Keywords: Distributed Computing, Butterfly, CCC, Dynamo, Majority Rule, Fault Tolerance. 1 Introduction Consider an arbitrary network whose vertices are initially colored black or white. A white vertex becomes black if the majority of its neighbours is black, and a black vertex never changes its color. The process goes on for all vertices until no further change of color occurs. A standard problem [19] is to find the initial configurations (assignme...