"Extreme Fluctuations in Small-Worlds with Relaxational Dynamics and Applications to Scalable Parallel Computing"
Synchronization is a fundamental problem in natural and artificial coupled multi-component systems. We investigate to what extent small-world couplings (extending the original local relaxational dynamics through the random links) lead to the suppression of the extreme fluctuations in noisy small-world-coupled systems. We use the framework of non-equilibrium surface growth to study and characterize the degree of synchronization in the system. In the absence of the random links, the surface in the steady state is ``rough'' (strongly de-synchronized state) and the average and the extreme height fluctuations diverge in the same power-law fashion with the system size (number of nodes). With small-world links present, the average size of the fluctuations becomes finite (synchronized state) [1,2] and the extreme heights diverge only logarithmically in the large system-size limit . This latter property ensures synchronization in a practical sense in coupled multi-component autonomous systems with short-tailed noise and effective relaxation through the links. The statistics of the extreme heights is governed by the Fisher-Tippett-Gumbel distribution . We illustrate our findings through an actual synchronization problem in the context of scalable parallel computing .  G. Korniss, M.A. Novotny, H. Guclu, Z. Toroczkai, and P.A. Rikvold, ``Suppressing Roughness of Virtual Times in Parallel Discrete-Event Simulations'', Science 299, 677--679 (2003).  B. Kozma, M.B. Hastings, and G. Korniss, ``Roughness Scaling for Edwards-Wilkinson Relaxation in Small-World Networks'', Phys. Rev. Lett. 92, 108701 (2004).  H. Guclu and G. Korniss, ``Extreme Fluctuations in Small-Worlds with Relaxational Dynamics'', arXiv:cond-mat/0311575 (2003).