Synchronization of a bounded degree graph of cellular automata with nonuniform delays in time \(D\lfloor \log_mD\rfloor\) (Q2490817)

\textit{T. Jiang} [The synchronization of non uniform networks of finite automata, in: FOCS, Vol. 89, 1989, 376--381; Inf. Comput. 97, No.~2, 234--261 (1992; Zbl 0768.68003)] proved a remarkable result: for every \(k\), there exists a cellular automaton synchronizing every degree \(\leq k\) connected graph with arbitrary symmetric communication delays. The synchronization time obtained by Jiang is \(O(\Delta^3)\) where \(\Delta\) is the maximum communication delay between two cells. Mazoyer [Synchronization of a line of finite automata with non uniform delays, 1990, unpublished] proved an \(O(D^2)\) synchronization time where \(D\) is the sum of the communication delays of the degree \(\leq k\) connected graph (together with an \(O(D \log D)\) synchronization time in case the graph has only two cells). In this paper, we prove (cf. Theorem 23) that for any \(m \leq 2\) one can synchronize in time \(D \lfloor\log_m (D)\rfloor\) all lines of total communication delay \(> m^9\) (shorter lines being synchronized in time \(4D\)). A result which extends to bounded degree connected graphs using Rosensthiel's technique [\textit{P. Rosenstiehl}, Int. Comput. Center Bull. 5, 245--261 (1966); \textit{P. Rosenstiehl, J. R. Fiksel} and \textit{A. Holliger}, Graph Theory Comput., 219--265 (1972; Zbl 0265.94030)]. As shown by Vivien [Cellular Automata: A Geometrical Approach, to appear], this result is already optimal for lines of two cells with arbitrary communication delay. The method relies heavily on Jiang technique of circuit with revolving information.