Synchronization in Complex Systems

Summary:

Task-completion system is a general term used for many complex systems such as causally constrained queuing networks and parallel discrete event simulation with a high number of components interacting on a network at which coupled processes occur. In these systems the updates in the local field variables carried by the nodes are done through some simple rules giving very rich global properties, e.g., the field variable at a node is updated if it is smaller than the variables at neighboring nodes. The aim of this work is an understanding of the relation between the topology/structure and global dynamical properties as a result of coupled processes in the network. We analyzed the properties of the virtual time horizon or synchronization landscape (corresponding to the progress of the processing elements) of these networks. To do that, we mapped the synchronization landscape into a non-equilibrium surface growth problem. We showed that when the communication topology among the components mimics that of the short-range interacting underlying system, the virtual time horizon exhibits Kardar-Parisi-Zhang (KPZ) kinetic roughening. Although the virtual times, on average, progress at a nonzero rate, their statistical spread of the virtual times diverges with the number of processing elements, hindering efficient data collection. We also showed that when the synchronization topology is extended to include random small-world links between the processing elements, they make a close-to-uniform progress with a nonzero rate, without global intervention. We developed a coarse-grained description for the small-world-synchronized virtual-time horizon and compared the findings to those obtained by simulating the simulations based on the exact algorithmic rules. Recently, we used scale-free network model as the basis for this system and found that the full scalability is again reachable. This study showed that a fully scalable system can be developed by changing the underlying topology from short-range to random (small world or scale free) one on top of short-range.

We also investigated to what extent small-world (or scale-free) couplings (extending the original local relaxational dynamics through the random links) lead to the suppression of extreme fluctuations in the synchronization landscape. In the absence of the random links, the steady-state landscape 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). For exponential-like noise the extreme heights diverge only logarithmically with the number of nodes, while for power-law noise they diverge in a power-law fashion. The statistics of the extreme heights are governed by the Gumbel (or Fisher-Tippet Type I) and the Frechet distribution, respectively.

Publications:

1. Hierarchical, Regular Small-World Networks, S. Boettcher, B. Goncalves, and H Guclu, Journal of Physics A: Mathematical and Theoretical 41, 252001 (2008).
   
   
2. Synchronization and extreme fluctuations in noisy task-completion landscapes, H. Guclu, G. Korniss and Z. Toroczkai, Chaos 17, 026104 (2007).
   
   
3. Synchronization Landscapes in Smallworld-connected Computer Networks, H. Guclu, G. Korniss, M.A. Novotny, Z. Toroczkai, and Z. Racz, Physical Review E 73, 066115 (2006).
   
   
4. Suppressing Roughness of Virtual Times in Parallel Discrete-Event Simulations, G. Korniss, M.A. Novotny, H. Guclu, Z. Toroczkai, and P.A. Rikvold, Science 299, 677 (2003).