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 .
A popular approach in designing a clock synchronization algorithm solving Q3 is to use un unbounded memory for each node to unravel' the cyclic phase space @math and construct an ever-increasing clock counter. As in the above mentioned technique assuming concentration condition, this effectively gives a global total ordering between local times. Then all nodes can tune toward the locally maximal time, for instance, so that the global maximum propagates and subsumes all the other nodes in @math time. This idea dates back to Lamport @cite_5 , and similar technique has been used in different contexts: for synchronous systems @cite_33 and for asynchronous systems @cite_43 . The biggest advantage of such approach includes independence of network topology and optimal time complexity of @math . However, they suffer when it comes to memory efficiency, and assuming unbounded memory on each node is far from practical, especially with the presence of faulty nodes @cite_45 .
@cite_5 @cite_45 @cite_33 @cite_43
1973501242 2139659159 1975533944
The concept of one event happening before another in a distributed system is examined, and is shown to define a partial ordering of the events. A distributed algorithm is given for synchronizing a system of logical clocks which can be used to totally order the events. The use of the total ordering is illustrated with a method for solving synchronization problems. The algorithm is then specialized for synchronizing physical clocks, and a bound is derived on how far out of synchrony the clocks can become. Distributed systems: an algorithmic approach is an important addition to the distributed computing literature. The book offers a broad overview of important distributed computing topics, and, where relevant, a touch of networking topics as well. A synchronizer with a phase counter (sometimes called asynchronous phase clock) is an asynchronous distributed algorithm, where each node maintains a local "pulse counter" that simulates the global clock in a synchronous network. In this paper, we present a time-optimal self-stabilizing scheme for such a synchronizer, assuming unbounded counters. We give a simple rule by which each node can compute its pulse number as a function of its neighbors' pulse numbers. We also show that some of the popular correction functions for phase clock synchronization are not self-stabilizing in asynchronous networks. Using our rule, the counters stabilize in time bounded by the diameter of the network, without invoking global operations. We argue that the use of unbounded counters can be justified by the availability of memory for counters that are large enough to be practically unbounded and by the existence of reset protocols that can be used to restart the counters in some rare cases where faults will make this necessary.