Jiang [The synchronization of nonuniform networks of finite automata, in: FOCS, Vol. 89,1989, pp. 376-381, The synchronization of non uniform networks of finite automata, Inform. and Comput. 97(2) (1992) 234-261] proved a remarkable result: for every k, there exists a cellular automaton synchronizing every degree <= 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 <= 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 >= 2 one can synchronize in time D [log, (D)] 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 (P. Rosenstiehl, Existence d'automates capables de s'accorder bien qu'arbitrairement connectes et nombreux, Internat. Comput. Center Bull. 5 (1966) 245-261, P. Rosenstiehl, J.R. Fiksel, A. Holliger, Intelligent graphs: networks of finite automata capable of solving graph problems, in: R.C. Read (Ed.), Graph Theory and Computing, Academic Press, New York, 1972, pp. 219-265]. 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. (c) 2006 Elsevier B.V. All rights reserved.
