We show that if a minimal-time solution exists for a fundamental distributed computation primitive, synchronizing arbitrary undirected networks of finite-state processors, then there must exist an “extraordinarily fast” $\tilde{O}(D^5E)$ algorithm in the RAM model of computation for exactly determining the diameter D of an arbitrary unweighted undirected graph with E edges. The proof is constructive.
At present we know eight variations of the firing squad synchronization problems whose solutions are known but whose minimal-time solutions are not known. Our result essentially completes the program outlined in [3] to show that it is highly unlikely for there to exist minimal-time solutions for these variations.