Asynchronous updates in large parallel systems

Albert G. Greenberg, S. Shenker, Alexander L. Stolyar

Research output: Contribution to journalArticlepeer-review


Lubachevsky [5] introduced a new parallel simulation technique intended for systems with limited interactions between their many components or sites. Each site has a local simulation time, and the states of the sites are updated asynchronously. This asynchronous updating appears to allow the simulation to achieve a high degree of parallelism, with very low overhead in processor synchronization. The key issue for this asynchronous updating technique is: how fast do the local times make progress in the large system limit? We show that in a simple K-random interaction model the local times progress at a rate 1/(K + 1). More importantly, we find that the asymptotic distribution of local times is described by a traveling wave solution with exponentially decaying tails. In terms of the parallel simulation, though the interactions are local, a very high degree of global synchronization results, and this synchronization is succinctly described by the traveling wave solution. Moreover, we report on experiments that suggest that the traveling wave solution is universal; i.e., it holds in realistic scenarios (out of reach of our analysis) where interactions among sites are not random.

Original languageEnglish (US)
Pages (from-to)91-103
Number of pages13
JournalPerformance Evaluation Review
Issue number1
StatePublished - May 1996
Externally publishedYes

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'Asynchronous updates in large parallel systems'. Together they form a unique fingerprint.

Cite this