Question

Let's assume we have given a two dimensional cellular automaton with an initial configuration where alls cells are in an quiescent state, expect for one square of cells. Let $n$ be the number of cells in that square. We want to synchronize all cells in the square, so we basically want to solve the firing squad synchronization problem.

Synchronizing all cells in $\Theta(\sqrt{n})$ is rather easy: All cells at the left and right border of the square serve as generals and we synchronize each row separately with any standard 1-dimensional FSSP algorithm. A row of $k$ cells with generals at both ends can be synchronized in $\Theta(k)$ steps (in our case: $k=\sqrt{n}$).

What I want to do, is to synchronize the whole square in $\Theta(\sqrt{n} \log n)$, so I need to slow down the synchronization process by a factor of $\log n$. But I have no idea how to do so.

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top