<-previous home next->

Method 1: Self-Maintaining Line
A self-maintaining line does not explicity detect a break. Instead, it will constantly adjust itself to the current configuration of the system. It does this by dynamically growing the line as dictated by the current gradient. If the gradient changes, so will the line.
Adjusting Gradient
Gradients in this model are time-sensitive. If the information a processor used to define it's gradient value is too old, it will decrement the value by one until it has established an up-to-date value. Note that finding this up-to-date value will also cause a processor to choose a new successor, since the successor-id is defined as the id of the neighbor who caused the processor to set its current gradient value. This means that the gradient will always reflect the current layout of the system.
original gradient propogation localized processor death gradient adjusts to new processor layout
Simply making the gradients in this model time-sensitive, and thus adjusting, the system automatically becomes self repairing. The time period after which information is considered 'too old' is some value larger than the time between broadcasts of a normally functioning processor. A gradient in this model will adjust if processors are excised or malfunction, causing the information they previously broadcasted to timeout. This timeout will cause any neighbors for which the dead processor was a successor to choose another successor from its remaining functioning neighbors. In this way, the line is always being traced back to a the gradient's origin, along the same route that the gradient propogated.
A gradient, originating from one endpoint, propogates. The other endpoint sets it's state value to indicate that it is part of the line. The line grows from left to right. Processors in black region are killed. The gradient begins to adjust to the new layout and the portion of the line that has become disconnected to the left endpoint de-differentiates. The line begins to follow the new gradient. Connectivity is re-established.
Evaluation
As long as it is possible for a message to travel between endpoints (for a gradient to propogate from one to the other), connectivity will be re-established. The self-repairing ability of this method is almost a side effect of the way in which the line is grown. The line will always reflect the newest information available. This method works particularly well for large faults, which may require a large amount of rearrangement, as well as for multiple breaks in connectivity. It may be somewhat inefficient for smaller faults, requiring the entire line to be rerouted instead of simply growing a small new segment to reconnect disjointed pieces.

<-previous home next->