Global synchronization of pulse-coupled oscillators on trees

Consider a distributed network on a finite simple graph G=(V,E) with diameter d and maximum degree Delta, where each node has a phase oscillator revolving on S1=ℝ/mathbbZ with unit speed. Pulse-coupling is a class of distributed time evolution rule for such networked phase oscillators inspired by biological oscillators, which depends only upon event-triggered local pulse communications. In this paper, we propose a novel inhibitory pulse-coupling and prove that arbitrary phase configuration on G synchronizes by time 51d if G is a tree and Delta ≤ 3. We extend this pulse-coupling by letting each oscillator throttle the input according to an auxiliary state variable. We show that the resulting adaptive pulse-coupling synchronizes arbitrary initial configuration on G by time 83d if G is a tree. As an application, we obtain a universal randomized distributed clock synchronization algorithm, which uses O(log Delta) memory per node and converges on any G with expected worst case running time of O(|V|+(d5+Delta2)log |V|).