Abstract
We consider the problem of simulating spatially distributed entities which can move, see each other, and react accordingly. We provide centralized reference algorithms for both time-stepped and discrete-event simulation. Under reasonable assumptions, we then proceed to distribute the simulation among several nodes by assigning each node a subregion of the simulation space. A main characteristic of our approach is that the subregions do not form a partitioning, but a covering. That is, they partially overlap, hence causing some duplicated computation, which is apparently redundant. The amount of overlapping is a tunable parameter of our algorithms, which affects the overall performance in a non-trivial way. Through an analytical model as well as experimental results we discover a trade-off. Choosing a small overlapping requires to perform frequent synchronizations, which negatively affect performance. However, a large overlapping leads to more duplicated work, which also decreases performance. Balancing the amount of overlapping is then required to optimize performance.