The Wake Up and Report Problem is Time-Equivalent to the Firing Squad Synchronization Problem
<|reference_start|>The Wake Up and Report Problem is Time-Equivalent to the Firing Squad Synchronization Problem: We consider several problems relating to strongly-connected directed networks of identical finite-state processors that work synchronously in discrete time steps. The conceptually simplest of these is the Wake Up and Report Problem; this is the problem of having a unique "root" processor send a signal to all other processors in the network and then enter a special "done" state only when all other processors have received the signal. The most difficult of the problems we consider is the classic Firing Squad Synchronization Problem; this is the much-studied problem of achieving macro-synchronization in a network given micro-synchronization. We show via a complex algorithmic application of the "snake" data structure first introduced in Even, Litman, and Winkler [ELW], that these two problems are asymptotically time-equivalent up to a constant factor. This result leads immediately to the inclusion of several other related problems into this new asymptotic time-class.<|reference_end|>
@article{goldstein2003the,
    title={The Wake Up and Report Problem is Time-Equivalent to the Firing Squad
  Synchronization Problem},
    author={Darin Goldstein and Nick Meyer},
    journal={arXiv preprint arXiv:cs/0310003},
    year={2003},
    archivePrefix={arXiv},
    eprint={cs/0310003},
    primaryClass={cs.DC cs.DS}
}