THE FIRING SQUAD SYNCHRONIZATION PROBLEM ON SQUARES, TORUSES AND RINGS.

It is well known that a solution for the Firing Squad Synchronization Problem (FSSP) takes time 2n - 1, n being the number of soldiers. It is also known that a solution on a square of n × n soldiers takes the same time. The main result of this paper is a new solution for the FSSP on networks shaped as squares. Our solution is optimal in two aspects: it is communication optimal (the so-called 1-bit solution) and is also time optimal, as it takes 2n - 1 time. It is also used as a building block to construct a very efficient solution on the square torus. Our approach applies also to linearly shaped networks and yields on the ring almost optimal time & communication solutions. In particular, for the square torus with n rows and rings of n processors, if n is even our solution is time & communication optimal. Otherwise, it is communication-optimal but does not match the lower bound on the time of a synchronization just by 1 time unit. [ABSTRACT FROM AUTHOR]