Synchronization of One-way Connected Processors
Salvatore La Torre
Margherita Napoli
Mimmo Parente
Dipartimento di Informatica ed Applicazioni,
Università degli Studi di Salerno,
84081 Baronissi, Italy
Abstract
A network of identical processors that work synchronously at discrete steps is given. At each step every processor sends messages only to a given subset of its neighboring processors and receives only from the remaining neighbors. The computation starts with one distinguished processor in a particular starting state and all other processors in a quiescent state. The problem is the following: to set all the processors in a given state for the first time and at the very same instant.
This problem is known as the firing squad synchronization problem and was introduced in [9]. In this paper solutions are presented that synchronize processors communicating on one-way links arranged in a ring or in a square with rows and columns that are rings. In particular, we provide optimal algorithms to synchronize both of the networks.
In addition, compositions of solutions are shown and solutions which synchronize at a time 
are given for equal to 
, 
, and 
.
