Existing cosmological simulation methods lack a high degree of parallelism due to the long-range nature of the gravitational force, which limits the size of simulations that can be run at high resolution. To solve this problem, we propose a new, perfectly parallel approach to simulate cosmic structure formation, based on the spatial COmoving Lagrangian Acceleration (sCOLA) framework. Building upon a hybrid analytical and numerical description of particles' trajectories, our algorithm allows an efficient tiling of a cosmological volume, where the dynamics within each tile is computed independently. As a consequence, the degree of parallelism is equal to the number of tiles. We optimise the accuracy of sCOLA by the use of a buffer region around tiles, and of appropriate Dirichlet boundary conditions around sCOLA boxes. As a result, we show that cosmological simulations at the degree of accuracy required for the analysis of the next generation of surveys can be run in drastically reduced wall-clock times and with very low memory requirements. The perfect scalability of our algorithm unlocks profoundly new possibilities of computing larger and higher-resolution cosmological simulations, taking advantage of a variety of hardware architectures.