{'fraction_non_alphanumeric': 0.06236421094212917, 'fraction_numerical': 0.01713411021133715, 'mean_word_length': 4.3693001060445384, 'pattern_counts': {'":': 1, '<': 5, '<?xml version=': 0, '>': 6, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 2, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Synchronization of Pulse-Coupled Oscillators and Clocks under Minimal Connectivity Assumptions

Populations of flashing fireflies, claps of applauding audience, cells of cardiac and circadian pacemakers reach synchrony via event-triggered interactions, referred to as pulse couplings. Synchronization via pulse coupling is widely used in wireless sensor networks, providing clock synchronization with parsimonious packet exchanges. In spite of serious attention paid to networks of pulse coupled oscillators, there is a lack of mathematical results, addressing networks with general communication topologies and general phase-response curves of the oscillators. The most general results of this type (Wang et al., 2012, 2015) establish synchronization of oscillators with a delay-advance phase-response curve over strongly connected networks. In this paper we extend this result by relaxing the connectivity condition to the existence of a root node (or a directed spanning tree) in the graph. This condition is also necessary for synchronization.


I. INTRODUCTION
Recent development of hardware and software for computation and communication has opened up the possibility of large scale control systems, whose components are spatially distributed over large areas. The necessity to use communication and energy-supply resources "parsimoniously" has given rise to rapidly growing theories of control under limited datarate [1] and event-triggered control [2], [3]. Many control and coordination algorithms, facing communication and computational constraints, have been inspired by natural phenomena, discovered long before the "network boom" in control. Early studies of the phenomenon of synchronous flashing in large populations of male fireflies in the dark [4] have disclosed a vision-based distributed protocol, enabling fireflies to synchronize their internal clocks: "each individual apparently took his cue to flash from his more immediate neighbors, so that the mass flash took the form of a very rapid chain of overlapping flashes..." [4, p. 310]. In a similar way the claps of many hands synchronize into rhythmic applause [5]. Later works revealed the role of such event-based interactions, referred to as the pulse coupling, in synchronization of neural networks [6], in particular, the cells of cardiac [7] and circadian [8] pacemakers. Self-synchronizing networks of biological pulse-coupled Anton V. Proskurnikov is with Delft Center for Systems and Control at Delft University of Technology, Delft, The Netherlands. He is also with Institute for Problems of Mechanical Engineering of the Russian Academy of Sciences (IPME RAS) and ITMO University, St. Petersburg, Russia, email: anton.p.1982@ieee.org Ming Cao is with the ENTEG institute at the University of Groningen, Groningen, The Netherlands, e-mail: ming.cao@ieee.org.
The influential papers [14], [15], addressing the dynamics of PCO networks, attracted extensive attention from applied mathematicians, physicists and engineers, since ensembles of PCO give an instructive model of self-organization in complex systems, composed of very simple units. Each unit of the ensemble is a system, which operates in a small vicinity of a stable limit cycle and is naturally represented by a scalar phase variable [16]. An oscillator's phase varies in a bounded interval; upon achieving its maximum, the phase is reset to the minimal value. At this time the oscillator fires an event, e.g. emitting electric pulse or other stimulus. The length of these pulses is usually neglected since they are very short, compared to the oscillators' periods. Unlike Kuramoto networks and other diffusively coupled oscillator ensembles [17], [18], the interactions of PCO are event-triggered. The effect of a stimulus from a neighboring oscillator on an oscillator's trajectory is modeled by a phase shift, characterized by the nonlinear phase response curve (PRC) mapping [16], [19].
In spite of significant interest in dynamics of PCO networks, the relevant mathematical results are very limited. Assuming that the oscillators are weakly coupled, the hybrid dynamics of PCO networks can be approximated by the Kuramoto model [11], [13], [15] that has been thoroughly studied [17]. The analytic results for general couplings are mostly confined to networks with special graphs [14], [20]- [22], providing a fixed order of the oscillators' firing. In recent papers [12], [23] synchronization criteria over general strongly connected graphs have been obtained, assuming that oscillators' PRC maps are delay-advance [6] and the deviations between the initial phases are less than a half of the oscillators' period. The main idea of the proof in [12], [23] is the contracting property of the network dynamics under the assumption of delay-advance PRC, enabling one to use the maximal distance between the phases (the ensemble's "diameter") as a Lyapunov function; this approach is widely used in the analysis of Kuramoto networks [24], [25].
In this paper, we further develop the approach from [12], [23], relaxing the strong connectivity assumption to the existence of a directed spanning tree (or root node) in the interaction graph, which is also necessary for synchronization. Also, unlike [11], [13] the delay-advance PRC maps are not restricted to be piecewise-linear and can be heterogeneous. Both extensions are important. Biological oscillator networks are usually "densely" connected (so the strong connectivity assumption is not very restrictive), but the piecewise linearity of PRC maps is an impractical condition. In clock synchronization problems the PRC map can be chosen piecewiselinear, but the requirement of strong connectivity excludes many natural communication graphs (e.g. the star-shaped graph with the single "master" clock and several "slaves"). The results have been partly reported in the conference paper [26].
The paper is organized as follows. Preliminary Section II introduces technical concepts and notation. The mathematical model of PCO networks is introduced in Section III. Main results are formulated in Section IV and confirmed in Section V by numerical simulations. Section VI concludes the paper.

II. PRELIMINARIES AND NOTATION
Given t 0 ∈ R and a function f (·), defined at least on the interval left-continuous at t 0 . The limit f (t 0 +) and right-continuity are defined similarly. A function f : [0; +∞) → R is piecewise continuous, if it is continuous at any t ≥ 0 except for a sequence {t n } ∞ n=1 , such that t n → ∞ and at each of the points t n the left and right limits f (t n −), f (t n +) exist.
A (directed) graph is a pair (V, E), where V and E ⊆ V ×V are finite sets, whose elements are referred to as the nodes and arcs respectively. A walk in the graph is a sequence of nodes v 1 , v 2 , . . . , v k , where consecutive nodes are connected by arcs A root is a node, from which the walks to all other nodes exist. A graph having a root is called rooted (this is equivalent to the existence of a directed spanning tree); a graph in which any node is a root is called strongly connected.
Any solution x(t), staying in the cycle's basin of attraction, converges as t → ∞ to the function x 0 (θ(t)/ω). Here θ(t) ∈ [0; 2π) is a piecewise-linear function, referred to as phase and treated as "a normalized time, evolving on the unit circle" [16]. The phase grows linearly until it reaches 2π and then is reset: In this paper we deal with ensembles of multiple oscillators (1), whose interactions are event triggered. Upon resetting, an oscillator fires an event by sending out some stimulus such as a short electric pulse or message. If an oscillator receives a stimulus from one of its neighbors, its phase jumps θ(t+) = Ψ(θ(t−)) mod 2π, Ψ(θ) after which the "free run" (1) continues. Typically it is assumed that Φ(0) = Φ(2π) = 0 so that if an oscillator is triggering an event at time t, then the stimuli received from the remaining oscillators do not violate (2). The map Ψ : [0; 2π] → R is referred to as the oscillator's phase transition curve (PTC) [6]. The PTC is determined as in (3) by the map Φ : [0; 2π] → R, referred to as the phase response (or resetting) curve (PRC) [6], [19], and the scalar coupling gain c > 0. In networks of biological oscillators, the PRC maps depend on the stimuli waveforms and the gain c depends on the stimulus' intensity [6], [16], [19], [27]. In time synchronization problems [9], [12], [13] the PRC map Φ and the coupling gain c are the parameters to be designed.
Henceforth we assume 1 , following [21], that k > 1 simultaneous events, affecting an oscillator, superpose as follows Taking Ψ 0 (θ) ∆ = θ, (4) holds for k = 0: if the neighbors fire no events, the phase is continuous unless it has reached 2π. Note that θ(t+) < 2π at any point; in particular, the oscillator cannot be forced to fire due to its neighbors' stimuli.
At the points of discontinuity one can define θ(t) arbitrarily; for definiteness, we suppose that θ(t) = θ(t−) ∈ [0; 2π]. We also allow the initial phase θ(0) = 2π: the oscillator fires an event and is immediately reset to 0.

A. Mathematical model of the PCO network
Consider a group of N > 1 oscillators of the same period T = 2π/ω and PTC mappings Ψ 1 (θ), . . . , Ψ N (θ), corresponding to PRC maps Φ i and coupling gains c i > 0. The vector of oscillators' phases is denoted byθ(t) The interactions among the oscillators are encoded by a graph G = (V, E), whose nodes are in one-to-one correspondence with oscillators V = {1, . . . , N }. The arc (j, i) exists if and only if oscillator j influences oscillator i; we denote N i ∆ = {j : (j, i) ∈ E} to denote the set of oscillators, affecting oscillator i; it is convenient to assume that i ∈ N i ∀i.
The dynamics of the PCO network is as followṡ Here | · | denotes the cardinality of a set. The phases obey (1) until some oscillators fire; I(θ(t)) = ∅ stands for the set of their indices. Oscillator i is affected by k i ≥ 0 firing neighbors, and its phase jumps in accordance with (4).
2π] N is said to be a solution to the system (5), (6) on the interval ∆ ⊆ [0; ∞) if the following conditions hold 1) on any compact interval ∆ ′ ⊆ ∆ only a finite number of events are fired ∆ ′ ∩ t : I(θ(t)) = ∅ < ∞; Fig. 1: Illustration to Assumption 1: the jump (3) decreases the distance between the oscillator i and its firing neighbor j.
2) the functionθ(t) is left-continuous and obeys (5) at any t ≥ 0 except for the points where some oscillators fire; at such pointsθ(t) switches in accordance with (6).
Remark 1: Our definition of a solution is more restrictive than the definitions in [22], [23], which replace the discontinuous mappingΨ in (6) by an outer-semicontinuous [28] multivalued map. Unlike the "generalized" solutions from [22], [23], the solution from Definition 1 is uniquely determined by its initial conditionθ(0) and depends continuously on it.
Our goal is to establish conditions, under which the solution θ(t) to the system (5), (6) exists on [0; ∞) and the oscillators' phases become synchronous in the following sense.

B. Assumptions
In this subsection, we formulate two assumptions adopted throughout the paper. The first of these assumptions implies an important contraction property of the hybrid dynamics (5), (6).  Fig. 1. The ith "clock" is delayed by the phase jump (4) if it is ahead of its firing neighbors (Fig. 1, left part) and advanced if it is behind them (Fig. 1, right part). Such operations do not lead to "overshoots": a "retarding" oscillator cannot overrun its neighbors and become "advancing", and vice versa. A firing oscillator is not influenced by the others' events since Ψ ki i (2π) mod 2π = 0. Assumption 1 holds, in particular, for PCOs with coupling gains c i ∈ (0; 1) and piecewise-linear PRC maps
The definition of diameter is illustrated by Fig. 2: one of the two shortest arcs, containing the phases, is drawn in red.

IV. MAIN RESULT
We start with establishing basic properties of the dynamical network (5), (6) (Subsect. IV-A) and then prove the the main result of the paper, ensuring synchronization (Subsect. IV-B).
Our method extends the idea of the diameter Lyapunov function, used to prove stability of multi-agent coordination protocols [29], to the hybrid system (5), (6). We show that the diameter d(θ(t)) of the oscillator ensemble is non-increasing and, furthermore, there exists a period T N , independent of the initial condition, such that d(θ(T N )) − d(θ(0)) < 0 unless d(θ(0)) = 0. The key idea is to establish the LaSalle-type result for the hybrid system (5), (6) and the Lyapunov function d(·), stating that any solution converges to the synchronous manifold {θ ∈ [0; 2π] N : d(θ) = 0}. In the existing literature [12], [23], this is done via a straightforward estimation of the diameter's decrease d(θ(T N )) − d(θ(0)), employing the special structure of PRC maps and the strong connectivity of the graph. We extend these results to the case of rooted graphs and general delay-advanced PRC maps, deriving the mentioned LaSalle-type result from the continuity of the trajectory with respect to the initial condition.

A. Basic properties of the solutions
We first show existence and uniqueness of solutions to the system (5), (6) and establish their basic properties.
The proof of Theorem 1 relies on the following proposition, proved in Appendix A.
Henceforth we confine ourselves to the trajectories satisfying Assumption 2. It appears that such trajectories continuously depend on the initial conditions in the following sense. For a given solutionθ(t), let t ik = t ik [θ(0)] stand for the time instant when oscillator i fires its kth event.
Lemma 1: Suppose that Assumption 1 holds. Consider a sequence of solutionsθ (n) (t) such thatθ (n) To prove Lemma 1, we use a technical proposition, which is based on Assumption 1 and proved in Appendix.
We are now ready to prove Lemma 1.

B. Synchronization criterion
Up to now, we have not assumed any connectivity properties, required to provide the oscillators' synchronization. The minimal assumption of this type is the existence of a root (or, equivalently, a directed spanning tree) in the interaction graph G. In a graph without roots there exist two non-empty subsets of nodes, which have no incoming arcs and thus are "isolated" from each other and the remaining graph [29,Theorem 5]. Obviously, the corresponding two groups of oscillators are totally independent of each other and thus do not synchronize.
The following theorem shows that under Assumptions 1 and 2 rootedness is sufficient for the synchronization (9).
Theorem 2: Suppose that Assumptions 1 and 2 hold, and the interaction graph G is rooted. Then the phases get synchronous (9).
For strongly connected interaction graphs and special PRC maps Theorem 2 has been established in [12], [23]. The fundamental property of the dynamics (5), (6) (see the proofs of Theorem 1 in [12] and Theorem 1 in [23]) is "contraction" of the minimal arc, containing the phases, after each "full round" of the oscillators' firing. As soon as each of the N oscillators has fired (some of them can fire twice), the diameter of the ensemble is decreased. This property, however, does not hold for a general rooted graph, as shown by the following. Example 2. Consider N = 3 oscillators with the period T = 2πrad/s that are connected in a chain 1 → 2 → 3; thus 1 is a root node, yet the graph is not strongly connected. Suppose that the oscillators start with θ 1 (0) = 0, θ 2 (0) = θ 3 (0) = θ 0 < π. The events fired by oscillators 2 and 3 at the instant t 1 = 2π − θ 0 do not affect oscillator 1, and hence θ 1 (t 1 +) = θ 1 (t 1 ) = 2π − θ 0 . The latter oscillator fires at time t 2 = 2π after which one has θ 1 (t 2 +) = 0, θ 2 (t 2 +) = Ψ(θ 0 ) ∈ (0; θ 0 ) and θ 3 (t 2 +) = θ 0 . Thus after the full round of firing the diameter remains equal to θ 0 . Considering a similar chain of N > 3 oscillators, its diameter in fact may remain unchanged even after (N − 2) full rounds of firing (each oscillator has fired at least N − 2 times).
It appears, however, that after N − 1 "full rounds" of firing the diameter always decreases, which is the key idea of the proof of Theorem 2. Proof: Introducing the shortest arc L(t) from Theorem 1, consider the sets of its endpoints {e iθj(t) : j ∈ J − (t)} and {e iθj(t) : j ∈ J + (t)}. The shortest turn from the phases, indexed by J − (t), to those indexed by J + (t) is counterclockwise, see Fig.4. A closer look at the proof of statements 2 and 3 in Theorem 1 reveals that at any time t * , when some oscillators fire, the following alternatives are possible: is affected by the events; in this case J − (t * +) = J − (t * ), J + (t * +) = J + (t * ) and d(t * +) = d(t * ); B) some of the "extremal" oscillators are affected, however d(t * +) = d(t * ); this implies that J − (t * +) ⊆ J − (t * ), J + (t * +) ⊆ J + (t * ) and one of these inclusions is strict; C) some of the "extremal" oscillators are affected, and the diameter is decreased: d(t * +) < d(t * −).
Notice that during the "full round" of events (each oscillator fires at least once) the second or third must take place. Indeed, suppose that J − and J + remain constant during such a round. The graph's rootedness implies [29,Theorem 5] that at least one of the corresponding sets of nodes has an arc, coming from outside. That is, a node j ∈ J − (or j ∈ J + ) exists, having a neighbor i ∈ N j beyond J − (respectively, beyond J + ). At the instant t when oscillator i fires θ i (t) = 2π and thus θ j (t) ∈ {0; 2π} since otherwise θ i (t) would also be an θ 2 (t); θ 4 (t); θ 6 (t) Corollary 2: For any constants d 1 , Proof: Assume, on the contrary, that a sequence of solutionsθ (n) (t) exists such that is compact, one may assume, without loss of generality, that the limitθ 0 ∆ = lim n→∞θ (n) (0) exists. Consider the solutionθ(t) with the initial condition θ(0) = θ 0 . Arbitrarily close to T N there exists a time instant t 0 , such that none of the oscillators fires at t 0 and d(θ(t 0 )) = d(θ(T N )). Thanks to Lemma 1, one hasθ (n) (t 0 ) →θ(t 0 ) as n → ∞ and thus d(θ(T N )) = d(θ(t 0 )) ≥ d(θ(0)) ≥ d 1 > 0, arriving thus at a contradiction with Lemma 2.
The proof of Theorem 2 is now immediate.
We have simulated the dynamics of the oscillators under the interaction graph, shown in Fig. 5. Notice that the graph in Fig.5 is rooted but not strongly connected because the phase of the "leading" oscillator 1 is unaffected by the others.

VI. CONCLUSIONS AND FUTURE WORKS
In this paper, we have examined the dynamics of networks of pulse-coupled oscillators of the delay-advance type. The models, studied in this paper, describe some biological networks [6], [20] and naturally arise in problems of synchronization of networked clocks [11], [12]. We have proved that the oscillators get synchronized if the maximal distance between the initial phases is less than π and the interaction graph is static and rooted (has a directed spanning tree), which is the minimal possible connectivity assumption. An extension to time-varying repeatedly rooted graphs is also possible.
An important problem, which is beyond the scope of this paper and remains open even for strongly connected graphs, is synchronization under general initial conditions. The existing results deal mainly with all-to-all or cyclic graphs [14], [20]- [22], [30] which guarantee some ordering of the oscillators' events and global contraction of the return map. For instance, as was noticed in [23], for the PRC map (10), the coupling gain 0.5 ≤ c ≤ 1 and the complete interaction graph, the diameter of ensemble becomes less than π after the first event independent of the initial condition. Another result, reported in [23], ensures synchronization over "strongly rooted" (star-shaped) and connected bidirectional graphs. However, as noticed in Remark 2, in general the phases of pulse-coupled oscillators do not synchronize and can e.g. split into several clusters [21]; similar effects may occur due to communication delays and negative (repulsive) couplings [31]. Even more complicated is the problem of synchronization between oscillators of different periods. One of the first results in this direction has been obtained in the recent paper [32].