Squad Synchronization Problem

Title: Squad Synchronization Problem

Research Question: How can we synchronize a group of processors in a network so that they all start and stop at the same time?

Methodology: The researchers considered several problems related to strongly-connected directed networks of identical finite-state processors that work synchronously in discrete time steps. They focused on two main problems: the Wake Up and Report Problem (WURP) and the Firing Squad Synchronization Problem (FSSP).

Findings: They found that these two problems are asymptotically time-equivalent, meaning that the time it takes for all processors to synchronize is the same up to a constant factor. This result leads to the inclusion of several other related problems into this new time-class.

Implications: This new time-class of problems allows researchers to focus their efforts on solving the "easy" problems and note that the solutions also solve the "difficult" ones. Conversely, a lower asymptotic time bound for one of the "difficult" problems also applies to the "easy" ones. This can help researchers to better understand the complexity of these problems and potentially find more efficient solutions.

Link to Article: https://arxiv.org/abs/0310003v1 Authors: arXiv ID: 0310003v1