Time Complexity of Synchronization of Discrete Pulse-coupled Oscillators on Trees
Hanbaek Lyu
We study a one-parameter family of discrete pulse-coupled inhibitory oscillators called the κ-color firefly cellular automata (FCA) on finite trees.We show that for κ ≤ 6, recurrence of oscillation cycles for every oscillator is a necessary and sufficient condition for synchronization on finite trees, while for κ ≥ 7 this condition is only necessary. As a corollary, we show that any non-synchronizing dynamics for κ ≤ 6 on trees decompose into synchronized subtrees partitioned by ‘dead’ oscillators. Furthermore, on trees with diameter 𝑑 and maximum degree at most κ, we show that the worst-case number of iterations until synchronization is of order 𝑂(κ𝑑) for κ ∈ {3, 4, 5}, 𝑂(κ𝑑2) for κ = 6, and infinity for κ ≥ 7. Lastly, we report simulation results of FCA on lattices and conjecture that on a finite square lattice, arbitrary initial configuration eventually synchronizes under the κ-color FCA if and only if κ = 4.
Keywords: Synchronization, coupled oscillators, cellular automata, trees, time complexity