# Presentation: 690760

## Stochastic Growth in a Small World and 

- Stochastic Growth in a Small World and
- Applications to Scalable Parallel Discrete-Event Simulations ** **
- H. Guclu1, B. Kozma1, G. Korniss1, M.A. Novotny2, Z. Toroczkai3, P.A. Rikvold4
**1***Department of Physics, Applied Physics, and Astronomy, Rensselaer Polytechnic Institute, 110 8**th** Street, Troy, NY, 12180-3590, U.S.A.*
* ***2***Department of Physics and Astronomy, and Engineering Research Center, Mississippi State University, P.O. Box 5167, Mississippi State, MS, 39762-5167, U.S.A.*
**3***Complex Systems Group, Theoretical Division, Los Alamos National Laboratory, MS B-213 Los Alamos, NM 87545, U.S.A.*
**4***Department of Physics, Center for Materials Research and Technology and School of Computational Science and Information Technology, Florida State University, Tallahassee, FL 32306 U.S.A.*

- We consider a simple stochastic growth model on a small-world network. The same process on a regular lattice exhibits kinetic roughening governed by the Kardar-Parisi-Zhang equation. In contrast, when the interaction topology is extended to include a ***finite*** number of random links for each site, the surface becomes macroscopically smooth. The correlation length of the surface fluctuations becomes finite and the surface grows in a mean-field fashion. Our finding provides a possible way to establish control ***without*** global intervention in non-frustrated agent-based systems. A recent application is the construction of a fully scalable algorithm for parallel discrete-event simulation.

- Rensselaer Polytechnic Institute

**Acknowledgment**
-   We thank B.D. Lubachevsky, G. Istrate, Z. Rácz and G. Györgyi for discussions. We acknowledge the financial support of NSF through DMR-0113049 and DMR-9981815, the Research Corporation through RI0761, and (Z.T.) DOE through W-7405-ENG-36.

**Abstract**

**References and Contact**
- [1] G. Korniss, Z. Toroczkai, M.A. Novotny, and P.A. Rikvold, Phys. Rev. Lett., **84**, 1351 (2000).
- [2] G. Korniss, M.A. Novotny, H. Guclu, Z. Toroczkai, and P.A. Rikvold, *Science, ***299**, 677 (2003).
**Contact:**   korniss@rpi.edu,  http://www.rpi.edu/~korniss

- Los Alamos National Laboratory

- Mississippi State University

- Florida State University

**Phase transitions in Small-World (SW) Networks**

-  Watts&Strogatz (1998):     “... enhanced signal-propagation speed,  ***computational power***, and ***synchronizability***”.
*** ******Finite number*** of random links per site (average connectivity is not extensive)
-  ***Phase transition*** or phase ordering is possible even when random links are added to an originally ***one-dimensional*** substrate:
-  Barrat&Weight (2000), Gitterman (2000), Kim et al. (2001):  Ising model on SW network
-  Hong et al. (2002): XY-model and Kuramoto oscillators on SW network.
-  These systems exhibit a phase transition of ***mean-field*** kind.

**Synchronization in Parallel Discrete-Event Simulations**

- Parallelization for asynchronous dynamics

**Paradoxical task:**
-  (algorithmically) parallelize (physically) non-parallel dynamics

**Difficulties**:
-  Discrete events (updates) are not synchronized by  a
-    global clock
- Traditional algorithms appear inherently serial (e.g.,  Glauber attempt one site/spin  update at a time)

- However, these algorithms are not inherently serial (Lubachevsky, 1987)

**Two Approaches for Synchronization**

**Conservative**
-  PE “idles” if causality is not guaranteed
-  Utilization, *******u*******: fraction of non-idling PEs

- *i*

- (site index)* **i*

*d*=1

**Optimistic (or speculative)**
-  PEs assume no causality violations
* **Rollbacks* to previous states once causality violation is
-   found (extensive state saving or reverse simulation)
-  Rollbacks can cascade (“avalanches”)

**Basic Conservative Approach**

- (nn: nearest neighbors)

-  one-site-per PE, *N*PE=*L**d*
* **t*=0,1,2,... parallel steps
-  *i*(*t*)* *local simulated time
-  local time increments are
-   iid exponential random variables
-  advance only if

**Scalability modeling**
***utilization***** **(efficiency) *u*(*t*)
-   (fraction of non-idling PEs)
-   density of local minima
***width*** (spread) of time surface:

**Simulating the Parallel Simulations**

- Universality/roughness

- (*d*=1)

- exact KPZ:
- =1/3
- =1/2

- G.K. et al., *PRL* **84**, 1351 (2000)

**Utilization (Efficiency)**

- Finite-size effects for the density of local minima/average growth rate (steady state):

- (*d*=1)

**Implications for Scalability**

- Simulation reaches steady state for
- (arbitrary *d*)

- Simulation phase: scalable

- Measurement (_data management_) phase: not scalable

- *u*∞ asymptotic average growth rate (simulation speed or utilization ) is non-zero

- measurement at meas:
- (e.g., simple averages)

- small-world-like connections: (used with probability *p>0*)

- (steady-state structure factor)

**Synchronization/Time-Horizon Control Via Small-World Communication Network Design**** **

- Roughness (Width)

- Utilization (fraction of non-idling PEs)

**Utilization Trade-off/Scalable Data Management**** **

- Speedup
- (utilization  *N**PE *)

- G.K. et al., *Science* **299**, 677 (2003)

**EW Model on a Small-World Network **

- eigenvalues of *ij*

- for a single realization of the random network

*N* sites

- with sh.p.b.c:

- only nn. interactions

- nn. + regular LR interactions (of range *N/2*)

- nn. + quenched random links

**Roughness And the Density of States**

* **p*=*0*: ***(****)* 1/ for *** 0   **  *integral and* *[*w**2*]* ** diverges*
-  sufficiently fast vanishing ***(****)* as *** 0   *  * **finite** *[*w**2*]

- density of eigenvalues

- disorder average

- Monasson, EPJB **12**, 555 (1999) for diffusion on SWN

- Exact numerical diagonalization of *ij*
- and comparison with the results for the simple massive coupling matrix

**Summary**

- Synchronizability of large non-frustrated agent-based systems with **SW **Network: application to construct fully scalable parallel simulations ***without*** global synchronizations
- Spectrum exhibits pseudo-gap or possibly a gap, yielding a ***finite width*** for stochastic growth on a small-world network ***for all*** *p*>0
- Possible flat-rough transition if range of random links is not uniformly distributed, but instead a power law

- (Foltin et.al., 1994)

- (Krug and Meakin, 1990)