Computer Science – Distributed – Parallel – and Cluster Computing
Scientific paper
2003-10-05
Computer Science
Distributed, Parallel, and Cluster Computing
13 pages, 4 figures, in Symposium on Discrete Algorithms, (SODA) pp. 578-587, January 6-8, 2002 (journal version to appear in
Scientific paper
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.
Goldstein Darin
Meyer Nick
No associations
LandOfFree
The Wake Up and Report Problem is Time-Equivalent to the Firing Squad Synchronization Problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The Wake Up and Report Problem is Time-Equivalent to the Firing Squad Synchronization Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Wake Up and Report Problem is Time-Equivalent to the Firing Squad Synchronization Problem will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-652147