The wake up and report problem is time-equivalent to the firing squad synchronization problem

DOI10.1007/S00446-003-0095-7MaRDI QIDQ5138501zbMATH OpenOpenAlexFDO

Authors Darin Goldstein, Nick Meyer

Publication date 4 December 2020

Published in Distributed Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cs/0310003

Mathematics Subject Classification ID

Data structures (68P05) Network design and communication in computer systems (68M10) Distributed systems (68M14) Network protocols (68M12)

Abstract: 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.

Recommendations

• scientific article; zbMATH DE number 2119713
• Synchronization of 1-way connected processors
• scientific article; zbMATH DE number 1869612
• The wakeup problem in synchronous broadcast systems
• The firing squad problem revisited

Cites work

• scientific article; zbMATH DE number 3990874 (Why is no real title available?)
• scientific article; zbMATH DE number 3237733 (Why is no real title available?)
• scientific article; zbMATH DE number 3310089 (Why is no real title available?)
• Computing with Snakes in Directed Networks of Automata
• Distributed Algorithms For Unidirectional Networks
• Distributed network protocols
• Faster computation on directed networks of automata
• Memory-efficient and self-stabilizing network RESET (extended abstract)
• Self-Stabilizing Symmetry Breaking in Constant Space
• The firing squad synchronization problem for a class of polyautomata networks
• The firing squad synchronization problem for graphs

Cited in

(2)

• Computing with Snakes in Directed Networks of Automata
• scientific article; zbMATH DE number 2119713 (Why is no real title available?)

This page was built for publication: The wake up and report problem is time-equivalent to the firing squad synchronization problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5138501)