The Distributed Firing Squad Problem (Preliminary Version)
Brian Coan, Danny Dolev, Cynthia Dwork, Larry J. Stockmeyer · Symposium on the Theory of Computing · 1985
Many fault-tolerant distributed algorithms assume a synchronous system, in which processing is divided into synchronous unison “steps” separated by rounds of message exchange (see, e.g., [DS, LSP]). A message sent at step s from a correct processor p to a correct processor q is received by q at step s+l. This assumption is justified by the impossibility results of [FLP] and [DDS], which show that if the system is asynchronous then there is no protocol for distributed agreement tolerant to even one benign processor failure. Another common assumption is that all processors begin the algorithm simultaneously, i.e., at the same step. In an actual distributed system in which different transactions and algorithms may be executed periodically, this may be unrealistic. Typically an algorithm is executed in response to a request from some specific processor, which may in turn be responding to some external request. If the given processor is correct then all correct processors learn of the request simultaneously, so they can indeed begin the algorithm in unison. However, if the processor is faulty then the correct processors may learn of the request at different steps. In this paper we justify the design assumption of simultaneous starts. Specifically, we provide algorithms to solve the associated synchronization