A compositional approach to synchronize two dimensional networks of processors

The problem of synchronizing a network of identical processors that work sy nchronously at discrete steps is studied. Processors are arranged as an arr ay of m rows and n columns and can exchange each other only one bit of info rmation. We give algorithms which synchronize square arrays of (n x n) proc essors and give some general constructions to synchronize arrays of (m x n) processors. Algorithms are given to synchronize in time n(2), n inverted r ight perpendicluar log n inverted left perpendicular, n inverted right perp endicular rootn inverted left perpendicular and 2(n) a square array of (n x n) processors. Our approach is a modular description of synchronizing algo rithms in terms of "fragments" of cellular automata that are called signals . Compositional rules to obtain new signals (and new synchronization times) starting from known ones are given for an (m x n) array. Using these compo sitional rules we construct synchronizations in any "feasible" linear time and in any time expressed by a polynomial with nonnegative coefficients.