\section{Example: A Simple Line Segment}\sectlabel{ls}
\newtheorem{definition}{Definition}[section]

As our first example of a self-healing structure, we consider the
special case of a simple line segment.  As we recall from
\sect{intro::so}, 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:
\begin{definition}
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 {\bf connected} $C(a,b)$, iff each processor lies within the communication
radius of the other. 

\[C(a,b) = \{a\in\,N(b) \wedge b\in\,N(a)\}\]

 Two identically labelled processors $a$ and $b$ are {\bf pairwise
connected} $C_p$ 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,$ 

\[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{definition}


Processors labelled with {\tt A-material} are responsible for
detecting the failure of a structure to maintain invariants after they
have been generated by the {\tt A-to-B-segment} growing point.  In
this case, the invariant to be maintained is the continuity of the
materials which connect point {\tt a} to point {\tt 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.

\subsection{Monitoring the Line Segment}\sectlabel{ls::monitor}
The main idea behind our monitoring algorithm is to establish a
periodic wave that only runs on labelled procesors.  If the
connectivity of intermediate processors is broken, the wave algorithm
will be unable to progress, thereby alerting processors that a problem
exists.

We may also express this idea from an algorithmic point of view:
\begin{enumerate}
\item   Endpoint {\tt b} broadcasts a message to its neighbors with an
argument counter initially set to $0$.
\item  Processors labelled with {\tt A-material} rebroadcast this
message to their neighbors, without changing the argument value.  In
addition, a timestamp of the message arrival is stored.
\item  When the other endpoint receives the message, it increments the
argument modulo $4$ and broadcasts the message.
\item   Processors  labelled with {\tt A-material} rebroadcast the
incremented message to their neighbors, and record the interval of time
between messages.
\item  Repeat 3 and 4.
\end{enumerate}

 Intermediate processors can estimate the amount of time
they should wait before deciding that the segment is disconnected.
The counter allows the intermediate processors to determine whether
they have heard the message before, or if they are receiving new
information.  Furthermore by looking at the parity of the argument,
each processor knows which direction the wave came from. 

\subsection{Diagnosing a Disconnect}\sectlabel{ls::diagnosis}

In order for a group of processors to determine that they
have been disconnected from an endpoint, we return to the wave
propagation algorithm.   

\begin{enumerate}

\item As we showed in \sect{ls::monitor}, intermediate materials can
determine which direction they received the last message from, and
when.  After a few iterations, processors can refine their
expectations about when they should receive a new update.
As long as they are receiving new updates within their expectations,
the process continues.  However, if this time has elapsed, the processor 
polls its neighbors to see if they have heard any more recent
messages.  

\item If they haven't either, the processor labels itself as
{\tt DISCONNECTED}.

\item If a processor later receives a wave propagation update, it
resets the {\tt DISCONNECTED} label.

\end{enumerate}


Once we have diagnosed the problem, it remains up to the rest of the
structure how to best go about repairing the injury. 

\subsection{Selecting a Repair Mechanism}\sectlabel{ls::repair}



In the case of the broken line segment, additional tools must be brought to bear on the problem.
The following algorithm demonstrates how to repair a line segment if it is known when and where the break occurs.
\begin{enumerate}
\item  A broken segment is composed of two pieces.  Materials know which end they are on, so they secrete the pheremone associated with their polarity.  
\item  Next, start a growing point at the processor which senses the greatest presence of the opposite polarity's pheremone.
\item  Move in a direction ortho+ towards the opposite polarity and ortho- from own polarity.
\item  Terminate when sensing an opposite polarity material.
\end{enumerate}
Inspired by the DNA language, an alternate method of repair involves a peer pressure algorithm in which the materials themselves grow towards each other.
\begin{enumerate}
\item   A broken segment is composed of 2 or more pieces.  Each piece
creates a unique identifier based on a HINUM algorithm.
\item   Each piece secretes a pheremone with its label.
\item   Unlabelled processors detect the presence of multiple pheremones dedifferentiate so they might be recruited as fresh material.
\item   Dedifferentiated materials nearby labelled materials become labelled materials.
\item  This continues until the broken ends meet. 
\end{enumerate}