On minimal-time solutions of firing squad synchronization problems for networks

摘要

The goal of this work is to show that if a minimal-time solution exists for a fundamental computation primitive, synchronizing networks of finite-state processors (formally known as the firing squad synchronization problems for directed and undirected networks), then there must exist "extraordinarily fast" algorithms for exactly solving the diameter problem in the standard RAM model of computation. These results can therefore be interpreted either as evidence that such minimal-time solutions for synchronization do not exist or as a potentially major algorithmic leap forward in the study of the diameter problem. We conjecture that the former is true. These results essentially complete the program outlined in [K. Kobayashi, Theoret. Comput. Sci., 259 (2001), pp. 129-143] to show that there exist a wide range of natural topologies for which it seems highly unlikely that there exist minimal-time solutions.