WIXLIB

The Impact of Time Delays onNetwork Synchronization and Coordination in aNoisy EnvironmentG. KornissDavid HuntB.K. SzymanskiSupported by DTRA, ARL NS‐CTA, NSF

Delay Differential Equations Macrodynamic theory of business cyclesKalecki, 1935,Frisch & Holme, 1935dJ a J (t ) c J (t )dtinvestment orders(relative to constant demand)“gestation period”of an investment 0.1 1yearsT 10 yearsKalecki, Econometrica 3, 327 (1935).2

Hutchinson model(logistic growth with delay in population dynamics) 0population size( N 0), N K N (t ) ) t N (t ) rN (t ) 1 KK intrinsic growth ratecarrying capacityN (t ) S. Ruan, in NATO Sci. Ser. II Math. Phys. Chem. (Springer, 2006) p. 477N (t ) K x(t ) t x(t ) rx(t ) Hutchinson (1948); Maynard Smith (1971); R.M. May (1973)3

Balancing (noise, feedback, delay, coordination)postural sway[fluctuations in the center of pressure]Milton et al., PTRSA (2011); EPL (2008).stick balancing at a fingertipCabrera et al., PRL (2002);FNL (2004); CMP (2006);Stépán & Kollár, MCM (2000).(biological/neurological systems: switch‐type/discontinuous/threshold control)4

Synchronization/Coordination in Coupled Systems individual units or agents (represented by static or mobile nodes)attempt to adjust their local state variables (e.g., pace, load,alignment, coordination) in a decentralized fashion.Craig Reynolds (1987); Vicsek et al. (1995); Cavagna et al. (2010). nodes interact or communicate only with their local neighbors in thenetwork, possibly to improve global performance or coordination. nodes react (perform corrective actions) to the information or signalreceived from their neighbors possibly with some time lag (as resultof finite transmission, queuing, processing, or execution delays)Applications: autonomous coordination, unmanned aerial vehicles,microsatellite clusters, sensor and communication networks, loadbalancing, flocking, distributed decision making in social networks http://www.youtube.com/watch?v VaQ66lDZ‐08flocking birdshttp://www.youtube.com/watch?v 6AmSpHxnKm8spontaneous brain activity (fMRI)IP activity(Justin Vincent; http://martinos.org/ vincent/ )(Zeus load balancer)5

Delays in Microscopic Vehicular FlowHuman drivers have reaction delays(awareness, decision, and execution delays), which,in part, depend on the drivers’ cognitive andphysiological statesY. Sugiyama, M. Fukui, M. Kikuchi, K. Hasebe, A. Nakayama, K. Nishinari,S.‐i. Tadaki, S. Yukawa, New Journal of Physics 10 033001 033001 .Shockwave traffic jam recreated for first time, New e/dn13402http://www.youtube.com/watch?v Suugn‐p5C1MSipahi et al., “Stability and Stabilization of Systems with Time Delay”,IEEE Control Systems Magazine (2011);http://dx.doi.org/10.1109/MCS.2010.939135v i (t ) [vi 1 (t ) vi (t )]G. Orosz, E. Wilson, and G. Stépán (Eds.), “Traffic jams: dynamics and control”, Philos. Trans . R. Soc.A 368, 4455 (2010).G. Orosz and G. Stépán, “Subcritical Hopf bifurcations in a car‐following model with reaction‐timedelay”, Proc. R. Soc. A 462 2643 (2006).D. Helbing, “Traffic and related self‐driven many‐particle systems,” Rev. Mod. Phys. 73, 1067, (2001).6

Synchronization/Coordination in Networks hi(t): local state variable a measure of synchronization, coordination, orload balancing efficiency:the spread of the synchronization landscape, w:N12hiw2 (t ) [h(t) h(t)] iN i 1h (t ) hl (t )wlsynchronizability:w ( ) 2i [index of node]7

Synchronization/Coordinationin a Noisy Environment with Time Delays t hi (t ) CCijijij[[hhiii((tt) h))j ( t )]hhjj((tt )])] i (t )jjjnetwork/coupling strength t hi (t ) ij h j (t ) i (t )j t hk (t ) k hk (t ) k (t )eigenvalues:delaynoisenetwork Laplacian: ij ij Ci Cij12w (t ) N0 0 1 2 N 1 maxN 1 k 1 2hk (t )8

Coordination, Noise, Time Delay t h(t ) h(t ) (t )delay (t ) (t ) 2 D (t t )noisecoupling strength Other applications: stochastic model for TCP Congestion Window Misra, Gong, and Towsley (1999), T. Ott and J. Swanson (2006); T. Ott (2006) deterministic: Frisch & Holme (1935); Hayes (1950); Hutchinson (1948); Maynard Smith (1971);R.M. May (1973) stochastic: Küchler and Mensch, SSR 40, 23 (1992); Ohira & Yamane, PRE (2000); Frank & Beek,PRE (2001); Hunt, Korniss, Szymanski, PRL (2010)9

Coordination, Noise, Time Delay (t ) (t ) 2 D (t t ) t h(t ) h(t ) (t )characteristic equation: (h(t ) ce st )g ( s ) s e ss s ( , ), 1,2, 0infinitely many relaxation “rates”, h (t ) 2 , 2 D [1 e( s s ) t]g ( s ) g ( s )( s s )synchronizability: h ( ) 2, for 0synchronizability condition:Re(s ) 0 / 2Frisch & Holme (1935); Hayes (1950); Hutchinson (1948); Maynard Smith (1971); R.M. May (1973)10

Coordination, Noise, Time Delay(a)2 c / 2 1.570 h(t)h(t) 1, D 1, dt 0.01 0.104( ) c / 2 2 4120(b)6100 1.50150200 6 121200100 1.60150200 02 h(t)50(c)60 60 1201e1 e20 h(t)50 050100t150 20011

Coordination, Noise, Time Delay( ) c / 2 1, D 1, dt 0.01103102101100τ 2.00τ 1.60τ 1.50τ 1.00τ 0.30τ 0.10 1.57 2 h (t) 2 c / 24 h (t ) 1010 110 210 210 1100110t10231012

Scaling in the Synchronizable Regimesteady state: 0 / 2Küchler and Mensch, SSR 40, 23 (1992).1500 h ( ) 24020 2 h 2τ π/2τ 5π/2τ 10π/2301000030 h /τλ40 h ( ) 00.20.4λ0.60.8113

Scaling in the Synchronizable Regime t h(t ) h(t ) (t ) 40λ 2 h ( ) 302010000.20.4λ0.60.8monotonically decreasingfunction of the coupling 1sinλcosKüchler and Mensch, SSR 40, 23 (1992).20100)1 40(Ornstein–Uhlenbeck)30 2(5050 h ( ) (t ) (t ) 2 D (t t )( )c / 200.20.4λ0.60.81non‐monotonic function ofthe coupling 14

Implications for Networks:1w (t ) N2Synchronizabilityand Coordination:N 1 k 1 2D hk (t ) NN 1 f ( )k 1Hunt et al., PRL (2010)k 2 hk ( ) k k / 2 k max / 2Olfati‐Saber and Murray (2004)(deterministic consensus problems)15

Limitations of Network SynchronizationSimple example: unweighted graphsNk max max 2k max ,N 1 max O(k max )Fiedler (1973); Anderson and Morley (1985); Mohar (1991)largest degreelargest eigenvalue of the network Laplacian16

Limitations of Network SynchronizationSimple example: unweighted graphsNk max max 2k max ,N 1 max O(k max )Fiedler (1973); Anderson and Morley (1985); Mohar (1991)k max / 4 :sufficient for synchronizability/stabilityk max / 2 :synchronization/stability breaks down networks with potentially large degrees can be extremelyvulnerable to intrinsic network delays while attempting tosynchronize, coordinate, or balance their tasks, load, etc.17

Limitations of Network Synchronizationheterogeneous vs. homogeneous random graphsFraction of Synchronizable Networksps( ,N) fractionof synchronizablenetworksComparisonof ER and BA Networks( max / 2)1ER : max k max ln( N )0.8 k 60.6psER τ 0.08ER τ 0.09ER τ 0.10ER τ 0.11BA τ 0.08BA τ 0.09BA τ 0.10BA τ 0.110.4BA : 0.2 max k max N 1/ 20101001000N18Hunt et al., PRL (2010)

Limitations of Network SynchronizationP(k ) kExample: scale‐free (BA) network ensemblewith a natural cut‐offps( ,N)fraction of synchronizable networks max k max N 1 /( 1)11 30.80.8p s ( , N ) PNmax ( / 2 )0.6 g ( N 1/( 1) )0.40.6ps0.2000.40.4N τ0.81.2synchronization and coordinationbreaks down for:τ 0.020τ 0.029τ 0.05τ 0.070.201/20400800N12001600 N1 /( 1) 1200019Hunt et al., PRL (2010)

Scaling in the Synchronizable Regimewith Uniform Coupling StrengthCij Aijw 2 ( ) , D NN 1 k ' k f ( ) g ( )k 1w 2 ( )kBA network, N 1000, k 6 , g ( )( D 1)20Hunt et al., PRE (2012)

Trade‐Offs t hi (t ) Cij [hi (t ) h j (t )] i (t )j max 1.2 / 2BA network, N 200, k 610perform local synchronizationwith rate p3synchronize frantically (at rate 1)p 1.010212 w (t) 101010100 1 210 2 110100t101102103Hunt et al., PRL (2010)21

Trade‐Offs t hi (t ) Cij [hi (t ) h j (t )] i (t )j max 1.2 / 2BA network, N 200, k 6perform local synchronizationwith rate p310p 0.82102 w (t) 110010reduce local synch. rate to 0.801010 1 2 21010 1010t101210103Hunt et al., PRL (2010)22

Trade‐Offs t hi (t ) Cij [hi (t ) h j (t )] i (t )j max 1.2 / 2BA network, N 200, k 61010synchronize frantically (at rate 1)p 1.0p 0.0p 0.82do not synchronize at all (rate 0)1 reducing the local synch.2 w (t) 10perform local synchronizationwith rate p310frequency can stabilize thesystem0reduce local synch. rate to 0.80 110 21010 210 1100t101102103(in fact, even no synchronizationat all is better than “over‐synchronization”: power‐lawdivergence vs exp. divergence ofthe fluctuations with time)Hunt et al., PRL (2010)23

Phase Boundary for Competing Time DelaysComplete Graph with N nodes (“normalized”): (t )(t ) t hik((tt)) hk ( t [ hoi ()t o ) hhjk((t t o o tr )]) tri kN 1NSynchronization 1 j i Boundary2.5N 11N 8N 5N 22g ( s ) s e o s N 1e ( o tr ) s 01.5τo o1 reentrant behavior in tr local delay is dominant (more harmful)Hunt, Korniss, and Szymanski, PLA (2011).0.50510τtr tr15202524

Synchronization and Coordination with Multiple Time Delays t hi (t ) ki A [h (t ijio) h j (t )] i (t )j o : local delays (reaction, decision, execution) : local delays transmission, queuing delays local delay is dominant (more harmful)Hunt et al., PRE (2012).25

o Global vs. Local Weighted Coupling t hi (t ) identical coupling cost: A [h (t ) h (t )] (t ) k ijijij k A kiji, j t hi (t ) kii, jAij Ni A [h (t ) h (t )] (t )ijijij26

The Impact of Time Delays inInformation and Communication Networksnodes/individuals constantly react to endogenous and exogenous ment they react to the information or signal received from their neighbors possiblywith some time lag (as result of finite transmission, decision, or executiondelays)de-coordinationde-coordination network connectivity or communication frequencylow connectivity /no communicationnetwork connectivity or communication frequencylow connectivity /no communicationhigh connectivity /“too much communication”27Hunt et al., PRL 105 , 068701 (2010)

Summary Delays can destroy synchronization/coordination in networksNetworks with large hubs can be particularly vulnerable in this regardToo much communication can cause more harm than goodOn the other hand, understanding the fundamental scaling properties of theunderlying fluctuations (in particular the ones associated with the largest‐eigenvalue mode) can guide optimization and trade‐offs to control and toreduce these large fluctuationsD. Hunt, B.K. Szymanski, and G. Korniss, Phys. Rev. Lett. 105, 068701 (2010).D. Hunt, B.K. Szymanski, and G. Korniss, Phys. Lett. A 375, 880 (2011).D. Hunt, B.K. Szymanski, and G. Korniss, Phys. Rev. E 86, 056114 (2012). 0Supported by DTRA, ARL NS‐CTA, NSF c28

Balancing (noise, feedback, delay, coordination) Milton et al., PTRSA (2011 . microsatellite clusters, sensor and communication networks, load balancing, flocking, distributed decision making in social networks IP activ