Robust Methods of Amorphous Synchronization
a.k.a. Synchronization of Pulse-Coupled Oscillators
Amorphous Computing
An amorphous computer is one in which many weak processors communicate to achieve tasks sometimes similar to those a "regular" processor could achieve. We assume that we have on the order of thousdands or hundreds of thousands of these processors working together, and that each processor has no knowledge of its global environment, only its local surroundings. Each processor can communicate with nearby processors, and can perhaps take readings from sensors or move. Because of the scale (both size and number) of processors, we assume as little regularity as possible: communications my not be bidirectional or even stable, processors may die or malfunction randomly, and so on. The problem of amorphous computing is to design algorithms to achieve global behavior through local interactions, and to ensure that these algorithms are robust to the irregularities inherent in the system.
The Synchronization Problem
In many amorphous computing situations, it is necessary or advantageous to effectively have a global clock. For example, in an amorphous sensor network, it is often useful to have all of the processors taking readings at the same time. This requires that all of the processors synchronize to a single period (much longer than a single tick of the processor) and that each of the processors starts this period at the same time. In order to do this, the processors will communicate, often at the same time they take readings (in order to say "I'm reading now"), but sometimes in between readings. The event being synchronized will be referred to as spiking or firing, and any other communication activites will be referred to as transmissions.
Simplifications
Since this is a very difficult problem, we start easy and work our way up. The simplest version of the problem is as follows: an all-to-all network of oscillators (when we remove this assumption we still assume the network is connected), each firing at the same frequency but not at the same time. All connections are bi-directional and radially symmetric (each node can communicate to within a certain radius of itself...no weird radio transmission areas), no node ever dies, starts up or loses data, there are no message collisions, and there is no processing or transmission time for messages. We also assume that knowledge of the network is complete: i.e. the connections in the network are determined in advance based on distance, rather than which processor can hear which processor at any given time. It is unclear which of these assumptions are realistic, and this will often depend on the particular application, but we know that some of them are unrealistic (e.g. it obviously takes time to process a message).
Solutions
First, we must define what a solution is. There are many different types of "synchronization:"
Full, or in-phase, synchronization is when the entire network fires at exactly the same time and at the same frequency (note: this does not require that the phase difference always be zero, only that the phase difference is zero when the network "fires")
Phase-locking, or out-of-phase synchronization, is when an entire network fires at the same frequency, but not at the same time (difference in phases between any two nodes is constant)
Noisy synchronization (Mirollo & Strogatz, 1990) is when an entire network fires within some constant alpha
Alpha-synchronization (Mathar & Mattfeldt, 1996) is when the entire network fires within some constant alpha times the diameter of the network (used in laggy situations)
Frequency-locking is defined in Mirollo & Strogatz, 1990 as the state in which all of the nodes fire at the same average frequency; while this seems more useful, it would be consistent to define frequency- or period-locking as the state in which the difference between any two frequencies is fixed
I have been working on three main algorithms, and several variations of each of those. All of the details and the variations will be discussed shortly. The first is integrate-and-fire, which takes in inputs, and when it's voltage reaches a certain threshold, fires. This appears to work perfectly when there is no lag and on a random spatial distribution. The second is to have the network "agree" on a processor ID, which I call basic symmetry-breaking, which works as long as we know the lag time and there is no noise. The third is a variation on integrate-and-fire called protected-aggressor, which is designed to achieve noisy synchronization in networks with unknown lag, and appears to be doing pretty well (I am currently working on this and haven't done any numerical analysis on the results yet). The grouping algorithm developed by Jake Beal discussed at the end is a scale-invariant algorithm for grouping networks (not necessarily of pulse-coupled oscillators), which is to be used in combination with any one of the synchronization algorithms.
Research
All of the research I have found has been in the area of neural computation, and much of it works with the standard integrate-and-fire model of a neuron, which turns out to be quite useful for synchronizing networks. All of these papers are studies of what happens when you use a certain model of neuron, or vary a certain parameter, etc. Because they are studies of biology rather than algorithms, they are very limited for our purposes. But they do give a good introduction to the subject and its methods of analysis (though many of these will not apply to more complicated algorithms). Unfortunately, almost all of the studies I have found have been on very simple networks: all-to-all, a ring, or a lattice of some type. I will soon be posting a summary of the articles I have collected under the heading "Research Summary." If you are looking for articles yourself, you will find a wealth of articles which reference Mirollo & Strogatz (1990), and the name of the problem is "synchronization of pulse-coupled oscillators." Mirollo & Strogatz (1990) is the seminal paper in its field, which started the research into pulse-coupled (as opposed to smoothly coupled) oscillators. I have recently gotten in touch with an author who wrote on this topic in the late 40s (Selfridge, 1949), but I have yet to get a copy of the article to see how relevent or in-depth it is. I will often reference Mirollo & Strogatz (1990) as the integrate-and-fire model I use is almost exactly the one they use.