Synchronization Landscapes in Small-World-Connected Computer Networks

Abstract

Motivated by a synchronization problem in distributed computing we studied a simple growth model on regular and small-world networks, embedded in one and two-dimensions. We find that the synchronization landscape (corresponding to the progress of the individual processors) exhibits Kardar-Parisi-Zhang-like kinetic roughening on regular networks with short-range communication links. Although the processors, on average, progress at a nonzero rate, their spread (the width of the synchronization landscape) diverges with the number of nodes (desynchronized state) hindering efficient data management. When random communication links are added on top of the one and two-dimensional regular networks (resulting in a small-world network), large fluctuations in the synchronization landscape are suppressed and the width approaches a finite value in the large system-size limit (synchronized state). In the resulting synchronization scheme, the processors make close-to-uniform progress with a nonzero rate without global intervention. We obtain our results by ``simulating the simulations", based on the exact algorithmic rules, supported by coarse-grained arguments.

20 pages, 22 figures

References in corpus (63)

• Emergence of scaling in random networks
• Statistical mechanics of complex networks
• The structure and function of complex networks
• The diameter of the world wide web
• The architecture of complex weighted networks
• The large-scale organization of metabolic networks
• Evolution of networks
• Mean-field theory for scale-free random networks
• The worldwide air transportation network: Anomalous centrality, community structure, and cities' global roles
• Synchronization in small-world systems
• Renormalization group analysis of the small-world network model
• Synchronization on small-world networks
• Ising Model on Networks with an Arbitrary Distribution of Connections
• Universality Classes for Extreme Value Statistics
• Ferromagnetic ordering in graphs with arbitrary degree distribution
• Universal Fluctuations in Correlated Systems
• Diffusion, localization and dispersion relations on ``small-world'' lattices
• Airy Distribution Function: From the Area Under a Brownian Excursion to the Maximal Height of Fluctuating Interfaces
• Exact Maximal Height Distribution of Fluctuating Interfaces
• Dynamic Phase Transition, Universality, and Finite-size Scaling in the Two-dimensional Kinetic Ising Model in an Oscillating Field
• Ising model in small-world networks
• 1/f Noise and Extreme Value Statistics
• Suppressing Roughness of Virtual Times in Parallel Discrete-Event Simulations
• Critical phenomena in networks
• Critical Exponents of the KPZ Equation via Multi-Surface Coding Numerical Simulations
• XY model in small-world networks
• Maximal Height Scaling of Kinetically Growing Surfaces
• Width Distributions and the Upper Critical Dimension of KPZ Interfaces
• Small-World Networks: Links with long-tailed distributions
• From Massively Parallel Algorithms and Fluctuating Time Horizons to Non-equilibrium Surface Growth
• Global fluctuations and Gumbel statistics
• Roughness distributions for 1/f^alpha signals
• Relaxation Properties of Small-World Networks
• Comment on "Ising model on a small world network"
• Mapping Monte Carlo to Langevin dynamics: A Fokker-Planck approach
• Efficient Parallel Simulations of Asynchronous Cellular Arrays
• Statistics of extremal intensities for Gaussian interfaces
• Spatial small-world networks: A wiring-cost perspective
• Fluctuations in finite critical and turbulent systems
• Mean-Field and Anomalous Behavior on a Small-World Network
• Parallelization of a Dynamic Monte Carlo Algorithm: a Partially Rejection-Free Conservative Approach
• Characterizing the structure of small-world networks
• Diffusion Processes on Power-Law Small-World Networks
• Exact Solution of Ising Model on a Small-World Network
• Universal fluctuations and extreme value statistics
• Testing the Collective Properties of Small-World Networks through Roughness Scaling
• Scaling in Small-World Resistor Networks
• Dynamic Scaling of Width Distribution in Edwards--Wilkinson Type Models of Interface Dynamics
• Extremal-point Densities of Interface Fluctuations
• Extreme Fluctuations in Small-Worlds with Relaxational Dynamics
• Phase ordering on small-world networks with nearest-neighbor edges
• 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
• Critical Properties of an Ising Model with Dilute Long-range Interactions
• On the Evolution of Time Horizons in Parallel and Grid Simulations
• Algorithmic scalability in globally constrained conservative parallel discrete event simulations of asynchronous systems
• An $\epsilon$-expansion for Small-World Networks
• Chemical fracture and distribution of extreme values
• Update statistics in conservative parallel discrete event simulations of asynchronous systems
• Virtual Time Horizon Control via Communication Network Design
• Discrete-Event Analytic Technique for Surface Growth Problems
• Reply to Comment on " Universal Fluctuations in Correlated Systems"

Cited by in corpus (12)

• Synchronization in complex networks
• Network synchronization landscape reveals compensatory structures, quantization, and the positive effect of negative interactions
• Nature-Inspired Interconnects for Self-Assembled Large-Scale Network-on-Chip Designs
• Network Coordination and Synchronization in a Noisy Environment with Time Delays
• Extreme fluctuations in noisy task-completion landscapes on scale-free networks
• Synchronizabilities of Networks: A New index
• Extreme Fluctuations in Stochastic Network Coordination with Time Delays
• Synchronization of Conservative Parallel Discrete Event Simulations on a Small-World Network
• Site and bond percolation thresholds in $K_{n,n}$-based lattices: Vulnerability of quantum annealers to random qubit and coupler failures on chimera topologies
• On Irregular Interconnect Fabrics for Self-Assembled Nanoscale Electronics
• Diffusion Processes on Small-World Networks with Distance-Dependent Random-Links
• Ad-hoc Limited Scale-Free Models for Unstructured Peer-to-Peer Networks