We are given a line of n identical processors (finite automata) that work synchronously. Each processor can transmit just one bit of information to the neighbour processors (if any) on the left and on the right. The computation starts at time 1 with the leftmost processor in a starting state and all other processors in a quiescent state. Given the time f(n), the problem is to set (synchronize) all the processors in a particular state for the first time, at the very same instant f(n). This problem is also known as the Firing Squad Synchronization Problem and was introduced by Moore in 1964. Mazoyer has given a minimal time solution with the least number of different states (six) and very recently he has given a minimal time solution for the constrained problem in which adjacent processors can exchange only one bit. In this paper we present solutions that synchronize the line at a given time expressed as a function of n. In particular we give solutions that synchronize at the times n log n, nradicn, n 2 and 2n. Moreover we also show how to compose solutions in such a way to obtain synchronizing solutions for all times expressed by polynomials with nonnegative coefficients. Clearly all such solutions work also in the general case when the 1-bit constraint is relaxed.
Synchronization of a line of identical processors at a given time
LA TORRE, Salvatore;NAPOLI, Margherita;PARENTE, Domenico
1997-01-01
Abstract
We are given a line of n identical processors (finite automata) that work synchronously. Each processor can transmit just one bit of information to the neighbour processors (if any) on the left and on the right. The computation starts at time 1 with the leftmost processor in a starting state and all other processors in a quiescent state. Given the time f(n), the problem is to set (synchronize) all the processors in a particular state for the first time, at the very same instant f(n). This problem is also known as the Firing Squad Synchronization Problem and was introduced by Moore in 1964. Mazoyer has given a minimal time solution with the least number of different states (six) and very recently he has given a minimal time solution for the constrained problem in which adjacent processors can exchange only one bit. In this paper we present solutions that synchronize the line at a given time expressed as a function of n. In particular we give solutions that synchronize at the times n log n, nradicn, n 2 and 2n. Moreover we also show how to compose solutions in such a way to obtain synchronizing solutions for all times expressed by polynomials with nonnegative coefficients. Clearly all such solutions work also in the general case when the 1-bit constraint is relaxed.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
