Abstract:
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
final 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.