<< Prev Next >>

Basic Symmetry-Breaking

The first step in these algorithms is to have some type of symmetry breaking: one node cannot simply say to the other "synchronize with me." While this works on an all-to-all graph, in a less well connected network, synchronized domains will appear which are never gauranteed to merge into one large domain. This algorithm is one of the simplest ways to perform symmetry-breaking.

    1) Each processor assigns itself an integer ID randomly (the likelihood of duplicate IDs being chosen can be made insignificant by increasing the storage space for the ID, and also obviously depends on how many processors you are working with).
    2) Each processor transmits its ID when it spikes.
    3) If a processor hears an ID higher than its own, it changes its ID to match and spikes immediately (this obviously assumes no lag)

This algorithm works in O(d*T) where d is the diameter of the network and T is the period of oscillation: this is the maximum amount of time it can take for one ID to spread across the entire network. Unfortunately, if any processor storing the highest ID loses its state or change unpredictably, we've run right back into the symmetry breaking problem. I am currently thinking about ways around this: some involve local synchronization-checks (looking at your neighbors), having processors store their original IDs and transmit that along with their current ID. (This will be updated shortly when I've thought about this some more.)


If we include lag the processors cannot spike immediately and synchronize (step 3). If all of the periods are the same and we know the lag time, then the receiving processor can instead wait T - (processing time) - (transmission time) and will fire with the transmitting processor the next time it fires. If the periods are not identical, then we can have the processors transmit their periods to get around this. If we do not know the lag times, then this method fails completely.