License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2018.20
URN: urn:nbn:de:0030-drops-85195
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8519/
Charron-Bost, Bernadette ;
Moran, Shlomo
The Firing Squad Problem Revisited
Abstract
In the classical firing squad problem, an unknown number of nodes represented by identical finite state machines is arranged on a line and in each time unit each node may change its state according to its neighbors' states. Initially all nodes are passive, except one specific node located at an end of the line, which issues a fire command. This command needs to be propagated to all other nodes, so that eventually all nodes simultaneously enter some designated ``firing" state.
A natural extension of the firing squad problem, introduced in this paper, allows each node to postpone its participation in the squad for an arbitrary time, possibly forever, and firing is allowed only after all nodes decided to participate. This variant is highly relevant in the context of decentralized distributed computing, where processes have to coordinate for initiating various tasks simultaneously.
The main goal of this paper is to study the above variant of the firing squad problem under the assumptions that the nodes are infinite state machines, and that the inter-node communication links can be changed arbitrarily in each time unit, i.e., are defined by a dynamic graph. In this setting, we study the following fundamental question: what connectivity requirements enable a solution to the firing squad problem?
Our main result is an exact characterization of the dynamic graphs for which the firing squad problem can be solved. When restricted to static directed graphs, this characterization implies that the problem can be solved if and only if the graph is strongly connected. We also discuss how information on the number of nodes or on the diameter of the network, and the use of randomization, can improve the solutions to the problem.
BibTeX - Entry
@InProceedings{charronbost_et_al:LIPIcs:2018:8519,
author = {Bernadette Charron-Bost and Shlomo Moran},
title = {{The Firing Squad Problem Revisited}},
booktitle = {35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
pages = {20:1--20:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-062-0},
ISSN = {1868-8969},
year = {2018},
volume = {96},
editor = {Rolf Niedermeier and Brigitte Vall{\'e}e},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8519},
URN = {urn:nbn:de:0030-drops-85195},
doi = {10.4230/LIPIcs.STACS.2018.20},
annote = {Keywords: Synchronization, Detection, Simultaneity, Dynamic Networks}
}
|
Keywords: |
|
Synchronization, Detection, Simultaneity, Dynamic Networks |
|
Collection: |
|
35th Symposium on Theoretical Aspects of Computer Science (STACS 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
27.02.2018 |
