Information Technology Reference
In-Depth Information
a non-error state by the base state protocol but by the superstabilizing protocol. That
is, when the minor token encounters the spurious major token, the erroneous state
can be corrected. Since it is very costly to send the minor token at every moving
the major token, we considered a mixed strategy of sending a minor token (ST, for
short) with probability p and not sending it (NS, for short) with probability 1
p .
Here is our protocol. There are two descriptions for i
=
0and i
=
0, but we omit
=
the one for i
0.
Our protocol for process i
=
0
if ( i has a non-base fault) then
reset to a neighboring base (if any);
send dtoken if i receives it
else if ( i has both major and minor tokens) then
if ( i has just received the major token) then
choose ST with probability p and NS with probability 1 p
if ( i has been waiting for the minor token) or ( i chooses NS) then
perform critical section ;
send major and minor tokens to i
1
else if ( i has a spurious major token) and ( i has a minor token) then
eliminate spurious major token
fi
send a minor token to i
+
+
1(ifany)
8.6 Conclusion
In this chapter we considered an effective search strategy for a naval mine by using
a two-person zero-sum game. The problem is motivated by distributed failure detec-
tion/repair as shown in the appendix. The advantage of our topic is to simplify the
original problem and to show its wide application.
We can find the feature of a method in some typical cases. For example, suppose
that n
r k α
and
β α
hold. First, the reconnaissance probabilities in the optimal
strategies are
n for the game
termination case. This means the probability for the termination case is smaller than
that for the continuation case for n
(
n
+
1
) / (
3 n
)
for the game continuation case and 1
/
>
2. Next, the reconnaissance probabilities in the
2
3 n 2
2
n 2
optimal strategies are
(
n
+
1
)
/ (
+
n
)
for the two boats case and
(
n
+
1
)
/ (
+
3 n
for the one boat case, where a detailed timing assumption is used. This means
the probability for the two boats case is smaller than that for the one boat case.
Our future work includes another application of reconnaissance problem to dis-
tributed protocols.
)
Acknowledgements
The authors would like to thank the anonymous referees for their helpful
comments.
This
work
was
partially
supported
by
Grant-in-Aid
for
Scientific
Research
((C)23510177) of the Ministry of Education, Science, Sports, and Culture of Japan.
Search WWH ::




Custom Search