^{1}, G. Korniss

^{2}and Z. Toroczkai

^{3}

### Abstract

We study the statistics and scaling of extreme fluctuations in noisy task-completion landscapes, such as those emerging in synchronized distributed-computing networks, or generic causally constrained queuing networks, with scale-free topology. In these networks the average size of the fluctuations becomes finite (synchronized state) and the extreme fluctuations typically diverge only logarithmically in the large system-size limit ensuring synchronization in a practical sense. Provided that local fluctuations in the network are short tailed, the statistics of the extremes are governed by the Gumbel distribution. We present large-scale simulation results using the exact algorithmic rules, supported by mean-field arguments based on a coarse-grained description.

The understanding of the characteristics of fluctuations in task-completion landscapes in distributed processing networks is important from both fundamental and system-design viewpoints. Here, we study the statistics and scaling of the extreme fluctuations in synchronization landscapes of task-completion networks with scale-free topology. These systems have a large number of coupled components and the tasks performed on each component (node) evolve according to the local synchronization scheme. We consider short-tailed local stochastic task increments, motivated by certain distributed-computing algorithms implemented on networks. In essence, in order to perform certain tasks, processing nodes in the network must often wait for others, since their assigned task may need the output of other nodes. Typically, large fluctuations in these networks are to be avoided for performance reasons. Understanding the statistics of the extreme fluctuations in our model will help us to better understand the generic features of backlog formations and worst-case delays in networked processing systems. We find that the average size of the fluctuations in the associated landscape on scale-free networks becomes finite and the largest fluctuations diverge only logarithmically in the large system-size limit. This weak divergence ensures an autonomously synchronized, near-uniform progress in the distributed processing network. The statistics of the maximum fluctuations on the landscape is governed by the Gumbel distribution.

We thank S. Majumdar for providing us with the numerically evaluated Airy distribution (Refs. 53 and 54) shown in Fig. 1(b) for comparison. We also thank Z. Rácz for valuable discussions. H.G. was supported by the U.S. DOE through Grant No. DE-AC52-06NA25396. G.K. acknowledges the financial support of the NSF through Grant No. DMR-0426488 and RPI’s Seed Grant. Z.T. has been supported by the University of Notre Dame.

I. INTRODUCTION

II. EXTREME-VALUE STATISTICS

III. TASK-COMPLETION NETWORKS

A. The model and its coarse-grained description

B. Previous work: Extreme fluctuations in regular and SW networks

IV. SCALE-FREE TASK-COMPLETION NETWORKS

A. Mean-field and exact numerical diagonalization approaches for the EW process on SF networks

B. Simulation results

V. SUMMARY AND CONCLUSIONS

### Key Topics

- Networks
- 33.0
- Network topology
- 13.0
- Synchronization
- 13.0
- Statistical analysis
- 11.0
- Cumulative distribution functions
- 9.0

## Figures

(a) The scaled distribution of the width of task-completion landscapes on a one-dimensional regular network. The inset is the same graph in log-linear scale. The dashed curve is the scaled width distribution of the KPZ/EW surface (Ref. ^{ 86 } ). (b) The scaled distribution of the maximum fluctuations in the same network. The inset is in log-linear scale and the dashed curve is the appropriately scaled Airy distribution function (Refs. ^{ 53 and 54 } ).

(a) The scaled distribution of the width of task-completion landscapes on a one-dimensional regular network. The inset is the same graph in log-linear scale. The dashed curve is the scaled width distribution of the KPZ/EW surface (Ref. ^{ 86 } ). (b) The scaled distribution of the maximum fluctuations in the same network. The inset is in log-linear scale and the dashed curve is the appropriately scaled Airy distribution function (Refs. ^{ 53 and 54 } ).

Steady-state width of the EW synchronization landscape from exact numerical diagonalization using Eq. (29) . (a) For the BA network, as a function of for various values of the minimum degree . The inset shows the same data on log-linear scales. (b) For the BA network, as a function of for different system sizes . The inset shows the behavior of the width vs ; the solid straight line represents the MF result [Eq. (28) ]. (c) For the BA and CM networks (with and ) as a function of , where is the average degree, for two system sizes. The bold straight solid and dashed lines correspond to the MF result [Eq. (28) ] with and , respectively.

Steady-state width of the EW synchronization landscape from exact numerical diagonalization using Eq. (29) . (a) For the BA network, as a function of for various values of the minimum degree . The inset shows the same data on log-linear scales. (b) For the BA network, as a function of for different system sizes . The inset shows the behavior of the width vs ; the solid straight line represents the MF result [Eq. (28) ]. (c) For the BA and CM networks (with and ) as a function of , where is the average degree, for two system sizes. The bold straight solid and dashed lines correspond to the MF result [Eq. (28) ] with and , respectively.

Average maximum fluctuations and average width for SF networks generated by the BA model. The data points are obtained by averaging over ten different network realizations. (a) Maximum fluctuations vs . (b) Maximum fluctuations vs system size. (c) Width vs . (d) Width vs system size.

Average maximum fluctuations and average width for SF networks generated by the BA model. The data points are obtained by averaging over ten different network realizations. (a) Maximum fluctuations vs . (b) Maximum fluctuations vs system size. (c) Width vs . (d) Width vs system size.

Average maximum fluctuations and the width for SF CM networks with . The data points are obtained by averaging over ten different network realizations. (a) Maximum fluctuations vs . (b) Maximum fluctuations vs system size. (c) Width vs . (d) Width vs system size.

Average maximum fluctuations and the width for SF CM networks with . The data points are obtained by averaging over ten different network realizations. (a) Maximum fluctuations vs . (b) Maximum fluctuations vs system size. (c) Width vs . (d) Width vs system size.

Distributions of (a) individual fluctuations, (b) maximum fluctuations, and (c) the width for the BA model with . The different individual fluctuations distributions in (a) are for different degree values ranging from the maximum to the minimum. The insets in (b) and (c) show the same distributions of the main graph but scaled to zero mean and unit variance in a log-linear scale. The dashed curves in the insets represent the Gumbel pdf [Eq. (16) ] in (b) and Gaussian pdf in (c) scaled in the same way. The system size is .

Distributions of (a) individual fluctuations, (b) maximum fluctuations, and (c) the width for the BA model with . The different individual fluctuations distributions in (a) are for different degree values ranging from the maximum to the minimum. The insets in (b) and (c) show the same distributions of the main graph but scaled to zero mean and unit variance in a log-linear scale. The dashed curves in the insets represent the Gumbel pdf [Eq. (16) ] in (b) and Gaussian pdf in (c) scaled in the same way. The system size is .

## Tables

Domain of attractions of the most common distributions for the maximum of iid random variables.

Domain of attractions of the most common distributions for the maximum of iid random variables.

Article metrics loading...

Full text loading...

Commenting has been disabled for this content