{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:25:08Z","timestamp":1787340308459,"version":"build-2736575974"},"reference-count":22,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2012,1]]},"abstract":"<jats:p>Consider a fully connected network where up to t processes may crash and all processes start in an arbitrary memory state. The self-stabilizing firing squad problem consists of eventually guaranteeing simultaneous response to an external input. This is modeled by requiring that the noncrashed processes \u201cfire\u201d simultaneously if some correct process received an external \u201cgo\u201d input, and that they only fire as a response to some process receiving such an input. This paper presents FireSquad, the first self-stabilizing firing squad algorithm. A firing squad algorithm facilitates the use of algorithms that need to start in the same round. It allows a smooth transition between algorithms whose executions need to be disjoint. The FireSquad algorithm combines two forms of fault-tolerance properties: self-stabilization to allow recovery from arbitrary transient errors and resilience to crash failures to handle permanent ones. The FireSquad algorithm is optimal in two respects: (a) once the algorithm is in a safe state, it fires in response to a go input as fast as any other algorithm does, and (b) starting from an arbitrary state, it converges to a safe state as fast as any other algorithm does.<\/jats:p>","DOI":"10.1137\/090776512","type":"journal-article","created":{"date-parts":[[2012,4,24]],"date-time":"2012-04-24T20:38:12Z","timestamp":1335299892000},"page":"415-435","source":"Crossref","is-referenced-by-count":5,"title":["An Optimal Self-Stabilizing Firing Squad"],"prefix":"10.1137","volume":"41","author":[{"given":"Danny","family":"Dolev","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ezra N.","family":"Hoch","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yoram","family":"Moses","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2012,4,24]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"R. Bazzi and G. Neiger,\n                      The possibility and the complexity of achieving fault-tolerant coordination\n                      , in Proceedings of the 11th Annual ACM Symposium on Principles of Distributed Computing, New York, 1992, pp. 203\u2013214.","DOI":"10.1145\/135419.135460"},{"key":"R2","unstructured":"J. E. Burns and N. A. Lynch,\n                      The Byzantine Firing Squad Problem\n                      , in Advances in Computing Research, Parallel and Distributed Computing 4, Jai Press, Greenwich, CT, 1987, pp. 147\u2013161."},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1137\/0218068"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1145\/96559.96565"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.05.005"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"S. Dolev and J. L. Welch,\n                      Wait-free clock synchronization (extended abstract)\n                      , in PODC, (1993), pp. 97\u2013108.","DOI":"10.1145\/164051.164066"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1145\/1017460.1017463"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1023\/A:1007914216733"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"S. Dolev,\n                      Self-Stabilization\n                      , MIT Press, Cambridge, MA, 2000.","DOI":"10.7551\/mitpress\/6156.001.0001"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(90)90014-9"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"R. Fagin, J. Y. Halpern, Y. Moses, and M. Y. Vardi,\n                      Reasoning about Knowledge\n                      , MIT Press, Cambridge, MA, 1995.","DOI":"10.7551\/mitpress\/5803.001.0001"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1145\/79147.79161"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"E. N. Hoch, D. Dolev, and A. Daliot,\n                      Self-stabilizing byzantine digital clock synchronization\n                      , in Proceedings of the 8th International Symposium on Stabilization, Safety, and Security of Distributed Systems, New York, 2006, pp. 350\u2013362.","DOI":"10.1007\/978-3-540-49823-0_25"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1145\/2455.2457"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-007-0049-6"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"T. Mizrahi and Y. Moses,\n                      Continuous consensus with failures and recoveries\n                      , in Proceedings of the 22nd International Symposium on Discrete Computing, 2008, pp. 408\u2013422.","DOI":"10.1007\/978-3-540-87779-0_28"},{"key":"R17","unstructured":"E. F. Moore,\n                      The firing squad synchronization problem\n                      , in Sequential Machines: Selected Papers, Addison-Wesley, Reading, MA, 1964, pp. 213\u2013214."},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2009.01.001"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1007\/BF01762112"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1007\/BF02242706"},{"key":"R21","doi-asserted-by":"crossref","unstructured":"M. Papatriantafilou and P. Tsigas,\n                      On self-stabilizing wait-free clock synchronization\n                      , in Algorithm Theory SWAT '94, E. Schmidt and S. Skyum, eds., Lecture Notes in Comput. Sci. 824, Springer, Berlin, 1994, pp. 267\u2013277.","DOI":"10.1007\/3-540-58218-5_25"},{"key":"R22","doi-asserted-by":"crossref","unstructured":"B. Patt-Shamir,\n                      A Theory of Clock Synchronization\n                      , Ph.D. thesis, MIT, Cambridge, MA, 1994.","DOI":"10.1145\/195058.195466"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/090776512","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:29:18Z","timestamp":1787336958000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/090776512"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,1]]},"references-count":22,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2012,1]]}},"alternative-id":["10.1137\/090776512"],"URL":"https:\/\/doi.org\/10.1137\/090776512","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,1]]}}}