Information Technology Reference
In-Depth Information
Similar to the argument for
m
=
1, the optimal strategies of player A and player
m
), denoted by
a
k
and
b
k
,are
Bforthe
k
-th stage (1
≤
k
≤
n
2
(
r
k
β
+
1
)(
n
+
1
)
r
k
(
α
−
β
n
)+
−
1
a
k
=
)
,
r
k
(
α
+
β
)+
n
(
n
+
1
r
k
(
α
+
β
)+
n
(
n
+
1
)
and
n
(
n
+
1
)
r
k
(
α
+
β
)
r
k
(
α
+
β
)+
b
k
=
)
,
,
r
k
(
α
+
β
)+
(
+
(
+
)
n
n
1
n
n
1
respectively.
If
k
is very large or
α
<
β
n
holds, we have
1
n
,
n
−
1
a
k
b
k
(
,
1
,
0
)
.
n
On the other hand, if
n
α
<
β
holds, we have
β
α
+
β
,
α
α
+
β
a
k
b
k
(
,
0
,
1
)
.
If
n
r
k
α
and
β
α
hold, we have
(
n
2
+
)
−
+
n
1
n
1
1
2
a
k
b
k
)
,
,
3
,
.
n
(
n
+
3
n
(
n
+
3
)
n
+
n
+
3
8.5 Application
We briefly state how our reconnaissance problem can be applied to a self-stabilizing
mutual exclusion, when there is at most one (major) token in a system. The process
holding the (major) token is given a privilege to do some task, called a
critical sec-
tion
. As shown in Fig.
8.1
, our protocol works for ring networks, in which a token,
called a
major token
, and a sub-token, called a
minor token
, are used. Our protocol
is the combination of a
base state protocol
and a superstabilizing protocol [
11
].
In the base state protocol, we predefine
H
>
n
integer states
I
H
=
{
0
,
1
,...,
H
−
1
, called
bases
, such that every correct state of a major token takes in a domain
R
H
=[
}
. If some major token has a non-base state, called a
non-base falut
, it is reset to a neighboring base state. To avoid a deadlock in which
every major token has a non-base state, process 0 sends a deadlock-breaking token,
called
dtoken
. When the process 0 receives the
dtoken
, it resets to some base
state independently because such a situation means the deadlock occurs.
In the superstabilizing protocol, we can also define the correct states of a major
token as
I
H
. In addition, we can recognize a process has a major token if it has a
different state from its neighboring state(s). Notice that there may be other spurious
major tokens even if every process has a base state. In such a case, we cannot restore
0
,
H
)=
{
x
|
0
≤
x
<
H
}
Search WWH ::
Custom Search