Bounds and approximations for self-initiating distributed simulation without lookahead

Abstract

We provide upper and lower bounds and an approximation for speedup of an optimistic self-initiated distributed simulation using a very simple model. We assume an arbitrary number of processors and a uniform connection topology. By showing that the lower bound increases essentially linearly with P , the number of processors, we find that the optimistic approach scales well as P increases. The model tracks the progress of Global Virtual Time (GVT) and eliminates the need to know the virtual time positions of all processors, thus making the analysis quite straightforward.