The Wake Up and Report Problem is Time-Equivalent to the Firing Squad Synchronization Problem

Simple item page
dc.creatorGoldstein, Darin
dc.creatorMeyer, Nick
dc.date2003-10-05
dc.date.accessioned2026-07-07T03:20:23Z
dc.date.available2026-07-07T03:20:23Z
dc.descriptionWe 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.
dc.description13 pages, 4 figures, in Symposium on Discrete Algorithms, (SODA) pp. 578-587, January 6-8, 2002 (journal version to appear in the Journal of Distributed Computing)
dc.identifierhttps://arxiv.org/abs/cs/0310003
dc.identifierhttp://arxiv.org/abs/cs/0310003
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/31810
dc.subjectDistributed, Parallel, and Cluster Computing
dc.subjectData Structures and Algorithms
dc.subjectE.1; C.2.1; C.2.2
dc.titleThe Wake Up and Report Problem is Time-Equivalent to the Firing Squad Synchronization Problem
dc.typetext

Files

Collections

arXiv