Abstract: Some models of parallel computers consist of copies of a single finite state automaton connected together in a regular fashion. In such computers a self-organizing structure called clerks can be useful, enabling one to simulate a more powerful computer for which optimal algorithms are easier to design. The computation proceeds by having the cellular automata organize themselves into clerks, and then a stepwise simulation of the more powerful computer is performed. For a system of n automata, each clerk contains Θ(log n) automata, so first they need to determine log(n), despite the fact that no single automata can count higher than a fixed number.

Clerks are used here to give optimal parallel algorithms for a connected 1s problem on a cellular array, and a circle construction problem on a pyramid cellular automaton.

In the connected 1s problem, the input is a white/black grid stored one point per processor, with two specially marked points, and the goal is to decide if the two marked points are in the same connected component (equivalently, viewing the input as a maze with black indicating walls, the problem is to decide if one can go from one marked point to the other within the maze). The 2-dimensional problem had been solved many years earlier by Beyer, who showed that an n x n cellular automata could solve it in Θ(n) time. However, his elegant solution, which was independently discovered by Levialdi, does not extend to higher dimensions.

This paper answers an open question that was raised in his 1969 thesis, showing that for any dimension d, a d-dimensional n x n ... x n cellular automata can solve the d-dimensional connected ones problem in Θ(n) time. S.R. Kosarju had called this a ``classic'' open problem.

Some closely related problems are still open. For dimension 2, it is known that a mesh computer can mark a minimal length path connecting the marked points (if they can be connected) in Θ(n) time. In a mesh computer each processor can perform constant-time calculations on words of logarithmic length, as opposed to the constant-length words in a celluar automata, but can store only a constant number of words. Can cellular automata mark a minimal path in this time? It is easy for the cellular automata to do this in Θ(n²) time by a breadth-first ``spreading wave'' approach. For dimensions ≥ 3 it isn't known if a mesh computer can solve this in Θ(n) time even if each processor is allowed polynomially much storage (i.e., all that it could address, given its word size).

Complete paper. This paper appears in Proceedings 23rd IEEE Symposium on Foundations of Computer Science (1982), pp. 272-279.

Related work:

• A paper utilizing clerks for a cellular automaton arranged as a mesh-connected computer, and one for a pyramid computer.
• My papers in parallel computing, and an overview of my research
• An explanation of parallel computing, Parallel Computing 101, a tutorial and a list of parallel computing resources.

Copyright © 2005-2008 Quentin F. Stout