JCA HomeIssue Contents

Fault Tolerant Solutions to the Firing Squad Synchronization Problem in Linear Cellular Automata
Jean-Baptiste Yunès

We consider some specific instances of the firing squad synchronization problem in which some cells are possibly defectives. As Umeo [16] showed, minimal-time solutions exist in the case there are locally more working cells than defective ones. This paper explains how to set up different schemes to obtain a linear-time synchronization on defective lines in the case there are locally more defective cells than working ones (but globally not too much many ones).

Full Text (IP)