Asynchronous updates in large parallel systems

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.