History


Please fill in your query. A complete syntax description you will find on the General Help page.
Synchronization of one-way connected processors. (English)
Complex Syst. 10, No.4, 239-255 (1996).
Summary: 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. 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 $f(n)$ are given for $f(n)$ equal to $n^2$, $n\log n$, and $2^n$.
Classification: C.m
WorldCat.org
Valid XHTML 1.0 Transitional Valid CSS!