(Fénix Editora, 2011) Dinneen, Michael J.; Kim, Yun-Bum; Nicolescu, Radu
We present an improved solution for the Firing Squad Synchronization Problem
(FSSP) for digraph-based P systems. We improve our previous FSSP algorithm by
allowing the general to delegate a more central cell in the P system to send the nal
command to synchronize. With e being the eccentricity of the general and r denoting the
radius of the underlying digraph, our new algorithm guarantees to synchronize all cells
of the system, between e + 2r + 3 steps (for all trees structures and many digraphs) and
up to 3e + 7 steps, in the worst case for any digraph. Empirical results show our new
algorithm for tree-based P systems yields at least 20% reduction in the number of steps
needed to synchronize over the previous best-known algorithm.
