On the Complexity of Network Synchronization
Darin Goldstein, Kojiro Kobayashi · SIAM Journal on Computing · 2005
We show that if a minimal-time solution to a fundamental distributed computation primitive, synchronizing a network path of finite-state processors, exists on the three-dimensional, undirected grid, then we can conclude the purely complexity-theoretic result $P = NP$. Every previous result on network synchronization for various network topologies either demonstrates the existence of fast synchronization solutions or proves that a synchronization solution cannot exist at all. To date, it is unknown whether there is a network topology for which there exists a synchronization solution but for which no minimal-time synchronization solution exists. Under the assumption that $P eq NP$, this paper solves this longstanding open problem in the affirmative.