<-previous home next->
Method 2: Self-Repairing Line

A self-repairing line relies on the active detection of a break. Elements of the line moniter their neighbors to the left and right. If one of these neighbors stops communicating, a new gradient will be sent out from the location of the break, so that the two disjoined segments can be reconnected.


Temporary Gradients
Instead of using an adjusting gradient, this method uses temporary gradients. Instead of one endpoint constantly sending out a gradient value, a gradient will only propogate once, and then be forgotten (reset to zero). While the gradient values are forgotten, processors do not forget who their successors are. Successors will only change if a new gradient is propogated after the previous gradient has been forgotten.

In this method, every element in the backbone of the line moniters the processor that comes before it (its predecessor) and the processor that comes after it (its successor). These neighbors are monitered simply by creating a timestamp when a message from them is received. If a very long amount of time passes (more than should reasonably pass between broadcasts by a functioning processor) then it is assumed that this neighbor is dead. A processor whose predecessor is dead will send out a new gradient, while a processor whose successor is dead will listen for this gradient and follow it back to the origin, thus reconnecting the two disjoined segments.
Unlike in method 1, elements that are part of the line will always remain part of the line. Also, these processors will never reset their successor-id, (as non-line processors will) when a new gradient propogates, except in the case where the processor's successor is dead, when resetting the successor-id will initiate the growth that repairs the break.


original gradient propogation



line begins to form, as processors forget
gradient values
(turn blue)


line established



localized processor death


new gradient sent out from location of break


new gradient propogates


processors forget new gradient
values (turn blue)


line regrows from location of break
according to last heard gradient


connectivity re-established



Evaluation
This method works especially well for small single breaks. Instead of abondoning a large amount of undamaged structure, only a small segment must be grown to re-establish conectivity. However, as faults become larger and more numerous the effectiveness of this method decreases.

Method 2 focuses on patching up faults, whereas method 1 reformats the entire structure to adapt to changes. This distinction is analogous to plugging a hole in a leaky pipe (method 2) or replacing the pipe (method 1). Which strategy is better may vary depending on the situation.

<-previous home next->