אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

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 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. Typically, this variant is relevant in the context of decentralized distributed computing, where processes have to coordinate for initiating various tasks simultaneously.

The talk will present the above variant of the firing squad problem under the assumptions that the nodes are {\em infinite} state machines, and that the inter-node communication links can be changed arbitrarily in each time unit, i.e., are defined by a {\em dynamic graph}. In this setting, the following question is studied: what connectivity requirements enable a solution to the firing squad problem?

The main result is a 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.

Time permitting, improvements of the solutions when additional information on the number of nodes or on the diameter of the network is given, and by the use of randomization, will also be discussed.

Joint work with Bernadette Charron-Bost