Consider a distributed network on a finite simple graph @math with diameter @math and maximum degree @math , where each node has a phase oscillator revolving on @math 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 @math synchronizes by time @math if @math is a tree and @math . 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 @math by time @math if @math is a tree. As an application, we obtain a universal randomized distributed clock synchronization algorithm, which uses @math memory per node and converges on any @math with expected worst case running time of @math .
For synchronous systems with discrete phase clocks taking values from @math , a number of algorithms which are self-stabilizing on trees with constant memory per node are known: e.g., for @math by Herman and Ghosh @cite_36 , for all odd @math by @cite_39 . Upper bounds of @math for convergence time is known for such algorithms. More recently, the author proposed a class of @math -state inhibitory pulse-couplings which are called the (FCAs) @cite_12 . In the reference and in @cite_23 , we showed that the @math -color FCA is self-stabilizing on finite paths for arbitrary @math , and on finite trees if and only if @math . The 4-coupling we introduced in this work is a continuous-state and asynchronous-update generalization of the 4-color FCA. That is, if the initial phases for the 4-coupling are discretized on a 1 4 grid points on @math , i.e., @math for all @math , then the trajectory @math follows the 4-color FCA dynamics.
@cite_36 @cite_23 @cite_12 @cite_39
2059435667 2528943279 1584976403
Abstract This note considers the problem of synchronizing a network of digital clocks: the clocks all run at the same rate, however, an initial state of the network may place the clocks in arbitrary phases. The problem is to devise a protocol to advance or retard clocks so that eventually all clocks are in phase. The solutions presented in this note are protocols in which all processes are identical and use a constant amount of space per process. One solution is a deterministic protocol for a tree network; another solution is a probabilistic protocol for a network of arbitrary topology. We study a one-parameter family of discrete dynamical systems called the @math -color firefly cellular automata (FCAs), which were introduced recently by the author. At each discrete time @math , each vertex in a graph has a state in @math , and a special state @math is designated as the blinking' state. At step @math , simultaneously for all vertices, the state of a vertex increments from @math to @math unless @math and at least one of its neighbors is in the state @math . A central question about this system is that on what class of network topologies synchrony is guaranteed to emerge. In a previous work, we have shown that for @math , every @math -coloring on a finite tree synchronizes iff the maximum degree is less than @math , and asked whether this behavior holds for all @math . In this paper, we answer the question positively for @math and negatively for all @math by constructing counterexamples on trees with maximum degree at most @math . We address the self-stabilizing unison problem in tree networks. We propose two self-stabilizing unison protocols without any reset correcting system. The first one, called Protocol SU_Min, being scheduled by a synchronous daemon, is self-stabilizing to synchronous unison in at most D steps, where D is the diameter of the network. The second one, Protocol WU_Min, being scheduled by an asynchronous daemon, is self-stabilizing to asynchronous unison in at most D rounds. Moreover, both are optimal in space. The amount of required space is independent of any local or global information on the tree. Furthermore, they work on dynamic trees networks, in which the topology may change during the execution.