Delys (anciennement Regal)
The Firing Squad Problem Revisited
Intervenant(s) : Bernadette Charron-Bost (LIX)
In the classical firing squad problem, an unknown number of nodes represented by identical finite
states 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, have full computational capabilities, 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.
Joint work with Shlomo Moran (Technion)
Plus d'informations ici
marc.shapiro (at) null