Global And Local Synchronization In Parallel Space-Aware Applications

Space-aware applications are characterized by an explicit representation of a spatial environment in which some entities live and operate by interacting with each other and with the hosting territory. A relevant space-aware application domain is the so-called urban computing, embracing issues like the simulation and implementation of public transportation systems, trac management, urban monitoring and control. The execution of such applications is often distributed on parallel computing nodes, which need to cooperate and exchange data among each other, thus raising synchronization issues. In this paper we analyze time-related characteristics of the computational process in a space-aware application in the case when each node does not need global synchronization (i.e. synchronization with all other nodes) but requires only local synchronization (i.e. synchronization with a subset of neighbor nodes). Performance is evaluated both analytically and numerically. We provide the analytical support to an important conclusion: the mean computation time per step remains finite irrespective of the number of nodes under local synchronization, while under global synchronization it grows unboundedly as the number of nodes increases. In practical scenarios this corresponds to significantly better scalability properties of local synchronization.