Document Open Access Logo

The Firing Squad Problem Revisited

Authors Bernadette Charron-Bost, Shlomo Moran

PDF
Thumbnail PDF

File

LIPIcs.STACS.2018.20.pdf
  • Filesize: 0.53 MB
  • 14 pages

Document Identifiers

Author Details

Bernadette Charron-Bost
Shlomo Moran

Cite As Get BibTex

Bernadette Charron-Bost and Shlomo Moran. The Firing Squad Problem Revisited. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 20:1-20:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.STACS.2018.20

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.

Subject Classification

Keywords
  • Synchronization
  • Detection
  • Simultaneity
  • Dynamic Networks

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Sebastian Abshoff, Markus Benter, Andreas Cord-Landwehr, Manuel Malatyali, and Friedhelm Meyer auf der Heide. Token dissemination in geometric dynamic networks. In Proceedings of the 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics, ALGOSENSORS, pages 22-34, 2013. Google Scholar
  2. Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration inequalities. A nonasymptotic theory of independence. Oxford University Press, Oxford, 2013. Google Scholar
  3. James E. Burns and Nancy Lynch. The byzantine firing squad problem. Advances in Computing Research, 4:147-161, 1987. Google Scholar
  4. Arnaud Casteigts, Paola Flocchini, Walter Quattrociocchi, and Nicola Santoro. Time-varying graphs and dynamic networks. In Hannes Frey, Xu Li, and Stefan Rührup, editors, ADHOC-NOW, volume 6811 of Lecture Notes in Computer Science, pages 346-359. Springer, 2011. Google Scholar
  5. Bernadette Charron-Bost and André Schiper. The Heard-Of model: computing in distributed systems with benign faults. Distributed Computing, 22(1):49-71, 2009. Google Scholar
  6. Bernard Chazelle. Natural algorithms and influence systems. Communications of the ACM, 55(12):101-110, 2012. Google Scholar
  7. Brian A. Coan, Danny Dolev, Cynthia Dwork, and Larry Stockmeyer. The distributed firing squad problem. In ACM Symposium on Theory of Computing Conference, STOC'85, pages 335-345, 1985. Google Scholar
  8. Thiago Correa, Breno Gustavo, Lucas Lemos, and Amber Settle. An overview of recent solutions to and lower bounds for the firing synchronization problem. arXiv preprint arXiv:1701.01045, 2017. Google Scholar
  9. Reinhard Diestel. Graph Theory. Springer-Verlag Berlin Heidelberg, 2017. Google Scholar
  10. Danny Dolev, Ezra N. Hoch, and Yoram Moses. An optimal self-stabilizing firing squad. SIAM Journal on Computing, 41(2):415-435, 2012. Google Scholar
  11. Danny Dolev, Rüdiger Reischuk, and H. Raymond Strong. Early stopping in Byzantine agreement. jacm, 37(4):720-741, 1990. Google Scholar
  12. Danny Dolev and H. Raymond Strong. Authenticated algorithms for Byzantine agreement. 12(4):656-666, 1983. Google Scholar
  13. Cynthia Dwork and Yoram Moses. Knowledge and common knowledge in a Byzantine environment: Crash failures. Information and Computation, 88(2):156-186, oct 1990. Google Scholar
  14. Steven Finn. Resynch procedures and a fail-safe network protocol. IEEE Transactions on Communications, 27(6):840-845, 1979. Google Scholar
  15. Julien M. Hendrickx, Alexander Olshevsky, and John N. Tsitsiklis. Distributed anonymous discrete function computation. IEEE Trans. Automat. Contr., 56(10):2276-2289, 2011. URL: http://dx.doi.org/10.1109/TAC.2011.2163874.
  16. Fabian Kuhn, Nancy A. Lynch, and Rotem Oshman. Distributed computation in dynamic networks. In Leonard J. Schulman, editor, Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pages 513-522. ACM, 2010. URL: http://dx.doi.org/10.1145/1806689.1806760.
  17. Fabian Kuhn, Yoram Moses, and Rotem Oshman. Coordinated consensus in dynamic networks. In Proceedings of the 30th ACM Symposium on Principles of Distributed Computing (PODC), pages 1-10. ACM, 2011. Google Scholar
  18. Edward F. Moore. The firing squad synchronization problem. Sequential Machines, Selected papers, pages 213-214, 1964. Google Scholar
  19. F. R. Moore and G. G. Langdon. A generalized firing squad problem. Information and Control, 12(3):212-220, 1968. Google Scholar
  20. Rotem Oshman. Distributed Computation in Wireless and Dynamic Networks. PhD thesis, Massachusetts Institute of Technology, 2012. Google Scholar
  21. Marshall Pease, Robert Shostak, and Leslie Lamport. Reaching agreement in the presence of faults. 27(2):228-234, 1980. Google Scholar
  22. Nicola Santoro. Time to change: On distributed computing in dynamic networks (keynote). In 19th International Conference on Principles of Distributed Systems, OPODIS 2015, December 14-17, 2015, Rennes, France, pages 3:1-3:14, 2015. Google Scholar
  23. T. K. Srikanth and Sam Toueg. Simulating authenticated broadcasts to derive simple fault-tolerant algorithms. Distributed Computing, 2(2):80-94, 1987. Google Scholar
  24. Roger Wattenhofer. Principles of distributed computing. Unpublished, 2014. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact