# Desynchronization and Speedup in an Asynchronous Conservative Parallel Update Protocol

**Authors:** A. Kolakowska, M. A. Novotny  
**arXiv:** [cs/0409032](https://arxiv.org/abs/cs/0409032)  
**Date:** 2004-09-16  
**Summary page:** https://www.summarizepaper.com/en/paper/cs--0409032v1/

## Key points

- Non-equilibrium surface growth methods can be used to analyze state update algorithms in distributed parallel discrete-event simulations (PDES)
- Authors focus on an asynchronous conservative PDES algorithm in a ring communication topology
- Global desynchronization in operation times can be deduced from kinetic roughening of the corresponding virtual-time horizon (VTH)
- Utilization of the parallel processing environment can be deduced by analyzing the microscopic structure of the VTH
- Theoretical estimates of performance as a function of L and load per processor, including approximate formulas for mean speedup and desynchronization are provided
- Theoretical upper bound for desynchronization and a theoretical non-zero lower bound for utilization exist for a given simulation size
- This approach is useful for designing new-generation algorithms that would efficiently carry out autonomous or tunable synchronization.

## Summary

This article explores the application of non-equilibrium surface growth methods to analyze state update algorithms used in distributed parallel discrete-event simulations (PDES). Specifically, the authors focus on an asynchronous conservative PDES algorithm in a ring communication topology, where a system of L asynchronous parallel processes communicate only with their nearest neighbors. The authors demonstrate that global desynchronization in operation times can be deduced from kinetic roughening of the corresponding virtual-time horizon (VTH), and the utilization of the parallel processing environment can be deduced by analyzing the microscopic structure of the VTH. To study its time evolution, they simulate it numerically as an asynchronous cellular automaton whose update rule corresponds to that followed by this algorithm. They provide theoretical estimates of performance as a function of L and load per processor, including approximate formulas for mean speedup and desynchronization. The authors establish that for a given simulation size there is a theoretical upper bound for desynchronization and a theoretical non-zero lower bound for utilization. This new approach to performance studies outlined in this chapter is particularly useful for designing new-generation algorithms that would efficiently carry out autonomous or tunable synchronization. This research provides insights into how non-equilibrium surface growth methods can be applied to uncover properties of state update algorithms used in PDES which could lead to more efficient and effective parallel computing systems.