Re: Central Control

["David A. Fisher" <dfisher@cert.org>]

>It's interesting that you brought this up.  Our group was just talking
>about
>a related issue yesterday.  Consider the circle model (found in the
>Sample Models/
>Mathematics folder of the Starlogo 2.0 distribution).  The algorithm
>works like this - each turtle knows it's left and right turtle, based
>on a total ordering of turtles.  It makes sure to stay a fixed distance
>from each of it's two neighbors.  BUT it also chooses a random turtle
>from the entire set of turtles, and moves away from that random turtle.
>
>Now, what emerges is a circle.  We could argue that the individual
>turtles are using local rules, that they only see their 2 immediate
>neighbors, and that they each pick the turtle to repel from in a local
>way, BUT these local rules have an underlying global structure!
>
>1. The turtles are totally ordered, and the ring emerges because of this
>2. The random repelling is uniformly distributed across the global
>population of turtles.  The circle emerges because of this GLOBAL
>UNIFORM DISTRIBUTION.  To see this, try putting a curtain down the
>middle of the screen, not allowing any turtles to repel from turles on
>the other side of the screen.  I'm not sure what you'll get, but I
>don't think it will be a circle.
>
>Thoughts?
>
>Larry Latour
>UMaine CS Dept.

In the emergent circle example, global information and central control are
used in the setup, but that setup is a one time event occurring before the
emergent algorithm begins.

The adjust function which maintains equal distance to a turtles two
neighbors involves neither global information nor central control.

The repel function however requires that each turtle be able to compute the
distance to any random turtle from the entire population and thus cannot be
performed without global information.

A more interesting question might be whether the emergent circle can be
achieved without global information.

Consider a modification to the algorithm in which the repel-turtle is
computed once as part of setup rather than dynamically at each step.  The
repel-turtle then becomes a third "neighbor" and the emergent algorithm
does not require global information.

This almost works but the resulting figure is often less than an oval and
tends to have more perturbation.  A better result is obtained by setting
each repel-turtle to (who + (total-turtles / 2)) mod total-turtles during
setup.  Here again the emergent algorithm depends only on a fixed third
neighbor for each turtle, but that neighbor is at maximum distance in the
chain of nodes.