  We examine the question of the influence of sparse long-range communications
on the synchronization in parallel discrete event simulations (PDES). We build
a model of the evolution of local virtual times (LVT) in a conservative
algorithm including several choices of local links. All network realizations
belong to the small-world network class. We find that synchronization depends
on the average shortest path of the network. The time profile dynamics are
similar to the surface profile growth, which helps to analyze synchronization
effects using a statistical physics approach. Without long-range links of the
nodes, the model belongs to the universality class of the Kardar--Parisi--Zhang
equation for surface growth. We find that the critical exponents depend
logarithmically on the fraction of long-range links. We present the results of
simulations and discuss our observations.
