next up previous
Next: Monitoring the Line Segment Up: line-segment Previous: Representational Organization

Example: A Simple Line Segment

As our first example of a self-healing structure, we consider the special case of a simple line segment. As we recall from the previous section, starting with two distantly located endpoints, we wish to organize the intermediate processors such that a set of labelled processors lies on the shortest path between the two endpoints. The shortest path metric is determined by a gradient field which has been initiated by one of the endpoints.

In this example, we can use a number of properties of the line segment algorithm to help us maintain its connectivity. In order to be more precise about the problem we are trying to solve, we propose the following definitions:

Definition 1.1 Let L be a labelling of processors, N(a) be a neighborhood of processor a. Then two identically labelled processors $a,b\in\,L$ are connected C(a,b), iff each processor lies within the communication radius of the other.


\begin{displaymath}C(a,b) = \{a\in\,N(b) \wedge b\in\,N(a)\}\end{displaymath}

Two identically labelled processors a and b are pairwise connected Cp if a message can be transmitted from one endpoint to the other only through pairs of connected elements. i.e. for $a,b,\{c_m\}\in\,L,$


\begin{displaymath}C_p(a,b) = C(a,c_1)\cup \bigcup_{m=1}^{M-1}C(c_{m},c_{m+1})\cup C(c_{M},b)\end{displaymath}

Processors labelled with A-material are responsible for detecting the failure of a structure to maintain invariants after they have been generated by the A-to-B-segment growing point. In this case, the invariant to be maintained is the continuity of the materials which connect point a to point b. The natural candidates to inform the structure that a connection has been broken are the materials themsleves.

Our algorithms will initially run on processors we know to be pairwise connected.




next up previous
Next: Monitoring the Line Segment Up: line-segment Previous: line-segment
Jeremy Zucker
2000-06-10