Synchronization in Small-World-Connected Computer Networks

Abstract

In this thesis we study synchronization phenomena in natural and artificial coupled multi-component systems, applicable to the scalability of parallel discrete-event simulation for systems with asynchronous dynamics. We analyze the properties of the virtual time horizon or synchronization landscape (corresponding to the progress of the processing elements) of these networks by using the framework of non-equilibrium surface growth. When the communication topology mimics that of the short-range interacting underlying system, the virtual time horizon exhibits Kardar-Parisi-Zhang-like kinetic roughening. Although the virtual times, on average, progress at a nonzero rate, their statistical spread diverges with the number of processing elements, hindering efficient data collection. We show that when the synchronization topology is extended to include quenched random communication links (small-world links) between the processing elements, they make a close-to-uniform progress with a nonzero rate, without global synchronization. We also provide a coarse-grained description for the small-world-synchronized virtual-time horizon and compare the findings to those obtained by simulating the simulations based on the exact algorithmic rules. We also present numerical results for the evolution of the virtual-time horizon on scale-free Barabasi-Albert networks serving as communication topology among the processing elements. Finally, we investigate to what extent small-world couplings (extending the original local relaxational dynamics through the random links) lead to the suppression of extreme fluctuations in the synchronization landscape.

Ph.D. thesis submitted to the Graduate School of Renssealer Polytechnic Institute, Troy, New York, USA. This is a far extended version of cond-mat/0601058. 82 pages, 46 figures

References in corpus (22)

• The structure and function of complex networks
• Airy Distribution Function: From the Area Under a Brownian Excursion to the Maximal Height of Fluctuating Interfaces
• Exact Maximal Height Distribution of Fluctuating Interfaces
• Suppressing Roughness of Virtual Times in Parallel Discrete-Event Simulations
• Global fluctuations and Gumbel statistics
• Statistics of extremal intensities for Gaussian interfaces
• Efficient Parallel Simulations of Asynchronous Cellular Arrays
• Spatial small-world networks: A wiring-cost perspective
• Mean-Field and Anomalous Behavior on a Small-World Network
• Diffusion Processes on Power-Law Small-World Networks
• Testing the Collective Properties of Small-World Networks through Roughness Scaling
• Extreme Fluctuations in Small-Worlds with Relaxational Dynamics
• Phase transition in the Ising model on a small-world network with distance-dependent interactions
• Comment on Bramwell et al, "Universal Fluctuations in Correlated Systems"
• Roughening of the (1+1) interfaces in two-component surface growth with an admixture of random deposition
• On the Evolution of Time Horizons in Parallel and Grid Simulations
• An $\epsilon$-expansion for Small-World Networks
• Algorithmic scalability in globally constrained conservative parallel discrete event simulations of asynchronous systems
• Update statistics in conservative parallel discrete event simulations of asynchronous systems
• Discrete-Event Analytic Technique for Surface Growth Problems
• Virtual Time Horizon Control via Communication Network Design
• Reply to Comment on " Universal Fluctuations in Correlated Systems"

Cited by in corpus (2)

• Ad-hoc Limited Scale-Free Models for Unstructured Peer-to-Peer Networks
• Scale-Free Overlay Topologies with Hard Cutoffs for Unstructured Peer-to-Peer Networks