Effective Search for a Naval Mine with Application to Distributed Failure Detection - Search Theory: A Game Theoretic Perspective - page 121

8.4 Another Assumption

If assumption 2 described in Sect. 8.2 is changed as follows, a new argument is
possible. We call the time interval that a boat/ship moves from one port to another a
slot .

New Assumption 1 The mine may be laid on the route at each beginning of a slot ,
where every slot is selected equally likely.

It means that the mine can be laid between the two ports immediately after the boat
has passed across the ports. In what follows, we compare two boats case with one
boat case for a fleet of ships (i.e., the game continues after the attack in both cases)
and for n

2 ports.
Notice that it takes n

>

1 slots, consisting of reconnaissance ( n slots) and the move
of ships (1 slot), to proceed to the next stage if the reconnaisance boat is dispatched.
Therefore, the terrorist has n

+

+ 1 chances to lay a mine in such a case.

8.4.1 Two Boats Case

To deal with the new assumption, we consider a new method, that is, the transport
ships dispatch two reconnaissance boats in both clockwise direction and counter-
clockwise direction. Then, the mine laid immediately after a boat has passed can
be found by another boat (see Fig. 8.2 ). It seems that the method can be replaced
by dispatching one boat in the counterclockwise direction. However, the two boats
method is meaningful in the distributed failure detection because no spurious tokens
are allowed in the global network as well as in front of the true token. Since the two
boats method does not work for n = 2 ports, we assume n > 2 in this section.

c

a

b

boat 1 boat 2

boat 1

i

i i

boat 2 boat 1

boat 2

ship

ship ship

When boat 1 is passing, no mine
is laid in front of the ship.

After boat 1 has passed, a mine
is laid in front of the ship.

Even the case (b), boat 2 can
find and remove the mine.

Fig. 8.2 Usefulness of two boats for the new assumption

By using this method, we have the following payoff matrix for the game contin-
uation case. Notice that even the two boats method cannot prevent the ships from
suffering damage if the mine is laid after a circulation of them.