Effective Search for a Naval Mine with Application to Distributed Failure Detection

We consider a kind of reconnaissance problem which has an application to distributed failure detection. The problem can be considered as a multistage two-person zero-sum game. The two-person, player A and player B, consists of a transport ship and a terrorist, respectively, where the ship is equipped with an unmanned reconnaissance boat. The ship circulates ports again and again and the terrorist may lay a naval mine on the shipping route. For safety, the ship dispatches the unmanned reconnaissance boat and removes the risk of a mine. However, it is very rare that the terrorist lays the mine, while the circulation of the reconnaissance boat is very costly. So, we introduce a mine-preparing probability, represented by geometric distribution, preceding the terrorist’s strategy. The ship has to determine when it should dispatch the boat so that it can maximize its expected payoff. First, we assume that the mine is laid at each beginning of a stage and investigate two cases, a game continuation case and a game termination case, after the ship has been broken by a mine. Next, we assume that the mine may be laid at any timing of a stage and investigate two methods, dispatching two boats and dispatching one boat, for the game continuation case. Finally, we state that the problem can also be applied to a failure detection problem in a distributed system if we regard the ship as a token and the terrorist as an adversary who causes a failure.