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

8.1 Introduction

We consider a reconnaissance problem which has an application to distributed
failure detection. The problem is described as follows. A transport ship circulates
a route containing distinct n ports again and again. A terrorist aims to attack the
ship by a naval mine. The ship can avoid the attack by dispatching an unmanned re-
connaissance boat before starting from one port to another. However, it is costly to
dispatch the boat at every starting time because the ship has to wait until the circu-
lation of the boat. So, the ship uses a mixed strategy which maximizes the expected
payoff in two-person zero-sum game, where the ship is considered as player A and
the terrorist as player B [ 13 ].
The topic of this chapter is motivated by a distributed failure detection/repair
problem. In distributed systems, e.g., the Internet, it is difficult to detect/repair a
failure. So, it is useful to consider a self-mending system in particular for a tran-
sient failure , a kind of memory corruption. Self-stabilizing mutual exclusion sys-
tems [ 2 , 3 ], in which at most one process is allowed to obtain a privilege to some
resource, e.g., a shared printer, tolerate the transient failure. One of the systems uses
a token circulation mechanism [ 14 ] and is carefully reinforced with a sub-token ,
called a superstabilization [ 8 , 10 ]. The token and the sub-token in a distributed
system correspond to the transport ship and the reconnaissance boat in our recon-
naissance problem, respectively. In addition, the failure caused by an adversary is
considered as the naval mine laid by a terrorist. The great advantage is that our
problem enables us to omit the detailed implementation of the distributed system
and to extract an essential point. Thus, we interpret the solution of the reconnais-
sance problem as that of the token circulation without proving the correctness of a
protocol.

a b

reconnaissance
boat

sub-token i i

token ship

After circulation of a sub-token,
process i sends both the tokens.

After circulation of a boat, a fleet
of ships proceed to the next port.

Fig. 8.1 Superstabilizing protocol vs. mine reconnaissance

Figure 8.1 a illustrates the superstabilizing protocol. The feature of the method
is that the process holding a token always dispatches a sub-token before acquir-
ing a privilege. When the sub-token meets a failure, it is corrected to a legitimate
state. After the circulation of the sub-token, the process holding a token acquires
a privilege. Figure 8.1 b illustrates our reconnaissance problem, where the same