% $B@_7W(B

\chapter{ dklicio $B$N@_7W(B \Comment{(Design)} }
\label{design}

$BA0>O$G$O!"(Bdklicio $B$NDL?.%W%m%H%3%k(B DKLICP $B$r2r@b$7$?!#(B
%
$BK\>O$G$O!"(BDKLIC $B=hM}7O$N:G2<0L%5!<%P$G$"$k(B
dklicio $B$N@_7W$K$D$$$F=R$Y$k!#(B

% \vspace{1em}

% \section{ Layers }

\newcommand{\E}{distributed}
\newcommand{\T}{variable\_table}

dklicio $B$O<!$N;0$D$N3,AX$+$i@.$k!#(B
\begin{enumerate}
\item $BJ,;6O@M}JQ?t(B \E
\item $BJQ?tI=(B \T ( \( \Leftrightarrow \) ID manager )
\item $B@k8@7?JQ?tF~=PNO%=%1%C%H(B io
\end{enumerate}


\section{ $BJ,;6O@M}JQ?t(B \E }

\newcommand{\Fuse}{\makebox{fuse}}
\newcommand{\Bound}{\makebox{bound}}
\newcommand{\In}{\( \; + \)}
\newcommand{\Out}{\( \; - \)}
\newcommand{\Nio}{\( \; ? \)}
\newcommand{\id}{\var{id}}

% $BFs<TDL?.(B
% $B;0<TDL?.(B

% $BJ,;6C10l2=(B

$BJ,;6O@M}JQ?t$O6qBN2=!"D>7k!"GQ4~$5$l$?$3$H$r8!=P$9$kI,MW$,$"$k!#(B

$BJQ?tI=$N%(%s%H%j$H$J$kJ,;6O@M}JQ?t$O!"<!$N$h$&$J$b$N$G$"$k!#(B

\( Dist =\Def ID \times Var \ni (id, var) \)

$B35G0E*$K$O<!$N$h$&$J%/%i%9(B \E $B$r:n$k$3$H$K$J$k!#(B
\begin{verbatim}
d(ID, X, Report) :- wait(X) |
  Report = [bound(ID, X)].
alternatively.
d(ID, X, Report) :- fused(X) |
  Report = [fused(ID, X) | Report1],
  d(ID, X, Report1).
d(ID, X, Report) :- garbage(X) |
  Report = [removed(ID)].
\end{verbatim}
$B$9$J$o$A!"6qBN2=!"D>7k!"GQ4~$5$l$?$3$H$r8!=P$7!"(B
$B$=$N;]$rJQ?tI=$KJs9p$9$kI,MW$,$"$k!#(B

KLIC $B=hM}7O$O<!$N%a%=%C%I$K$h$C$F%/%i%9(B \E $B$rA`:n$9$k!#(B
\begin{enumerate}
\item $B%3%s%9%H%i%/%?(B \In\ID, {\Nio}Report

\item $B%$%Y%s%H(B \Fuse {\Nio}Any
\\
$B%m!<%+%k%[%9%HFb$G(B \E $B$,C10l2=$5$l$?$3$H$r<($9%$%Y%s%H$G$"$k!#(B

$B%m!<%+%k%[%9%HFb$N@)Ls5-21!JC10l2=$NMzNr!K$r(B \( constraints \) $B$H$9$k$H!"(B
\\
\( \Fuse: Dist \times Constraints \times Term \rightarrow
\\ \Tab Constraints \times \{ bound/2, fused/2 \} \)
\\
\( \Fuse((id, var), constraints, term) =
\\ \Tab (constraints \cup \{ var=term \},
\\ \Tab message(id, term))
\\ \Where
\\ \Tab message = bound \If term \in Bound
\\ \Tab message = fused \If term \not\in Bound \)

KLIC $B=hM}7O$GL$Dj5AJQ?tF1;N$ND>7k$r8!=P$9$k$K$O!"(B
$B$=$NL$Dj5AJQ?t$,%8%'%M%l!<%?%*%V%8%'%/%H$H$7$F<BAu$5$l$F$$$kI,MW$,$"$k!#(B
%
$B=>$C$F!"(B\E $BF1;N$ND>7k$r8!=P$9$k$?$a$K!"(B
\E $B$r%8%'%M%l!<%?%*%V%8%'%/%H$H$7$F<BAu$9$k!#(B

\item $B%$%Y%s%H(B gc ({\Out}Address)
\\
$B%m!<%+%k%[%9%HFb$G(B KLIC $B=hM}7O$N%3%T!<(B GC $B$,9T$o$l!"(B
$B%f!<%6%W%m%;%9$+$i$3$N%*%V%8%'%/%H$X$N;2>H$,@8B8$7$F$$$k$N$G!"(B
$B$3$N%*%V%8%'%/%H$r?7NN0h$X%3%T!<$9$kI,MW$,$"$k$3$H$r<($9%$%Y%s%H$G$"$k!#(B

$BJQ?tI=$+$i$3$N%*%V%8%'%/%H$X$N;2>H$O!V@8B8$7$F$$$J$$!W$N$G!"(B
$B$=$l0J30$N;2>H$,@8B8$7$F$$$J$$>l9g!"(B
$B$3$N%*%V%8%'%/%H$O5lNN0h$X<h$j;D$5$l!"GQ4~$5$l$k!#(B
\end{enumerate}


\section{ ID manager (Name Server) }

Name Server $B$O35G0E*$KMM!9$J%l%Y%k$G8=$l$k!#(B
%
$BNc$($P!"(B
\begin{enumerate}
\item DNS $B$O%[%9%HL>$r(B IP $B%"%I%l%9$KBP1~IU$1$k!#(B
\item $B%=%1%C%H$O%]!<%HHV9f$r%5!<%P$KBP1~IU$1$k!#(B
\item ID manager $B$O(B ID $B$rJ,;6O@M}JQ?t$KBP1~IU$1$k!#(B
\item java.rmi.Naming (rmiregistry)
$B$O%$%s%?%U%'%$%9$r%5!<%P%*%V%8%'%/%H$KBP1~IU$1$k!#(B
\item ORB $B$O%5!<%S%9$rJ,;6%*%V%8%'%/%H$KBP1~IU$1$k!#(B
\end{enumerate}

DNS, ORB $B$O<BBN$K!"0[$J$kL>A06u4V$K$*$1$kJLL>$rIU$1$k!#(B
$B%f!<%6$O<BBN$NK\L>$rCN$kI,MW$,$J$/!"(B
$BJLL>$K$h$C$F<BBN$rFCDj$9$k$3$H$,$G$-$k!#(B

$B%=%1%C%H(B, ID manager, Java RMI $B$O(B
$B<BBN$K9-0hL>$rIU$1$k$3$H$K$h$C$F!"(B
$B1s3V%f!<%6$,<BBN$K%"%/%;%9$9$k$3$H$r2DG=$K$9$k!#(B

\Comment
{Name Server $B$KI,?\$N5!G=$G$O$J$$$,!"(B
 (DNS,) Java RMI, ORB $B$K$O8!:w5!G=$,$"$k!#(B}

$B$3$3$G:n$k(B Name Server $B$O<!$N$h$&$J$b$N$G$"$k!#(B
\\\( NS : ID \rightarrow \{ free, used \} \)

$B$3$N(B NS $B$KBP$7$F$O<!$NFs$D$NA`:n$r9T$&!#(B
\begin{eqnarray*}
get &:& NS \rightarrow ID \times NS
\\
release &:& NS \times ID \rightarrow NS
\end{eqnarray*}
\\
\( get(ns) = (id, ns \setminus \{ (id, free) \} \cup \{ (id, used) \}) \)
\\
\( release(ns, id) =
 ns \setminus \{ (id, used) \} \cup \{ (id, free) \} \)

NS $B$N5!G=$OJQ?tI=!JG[Ns!K$K4^$a$k$3$H$,2DG=$G$"$k$,!"(B
$B?7$7$$(B ID $B$r(B \( O(1) \) $B$G<hF@$9$k$?$a$K(B
$BL$;HMQ(B ID $B$r%j%9%H$G4IM}$9$k!#(B
%
$B%j%9%H$N07$$$O(B C $B8@8l$h$j(B KL1 $B8@8l$NJ}$,F@0U$H$7$F$$$k$N$G!"(B
NS $B$O(B KL1 $B8@8l$K$h$C$F5-=R$7!"(B
C $B8@8l$K$h$C$F5-=R$9$kJQ?tI=%*%V%8%'%/%H$H$OJL%W%m%;%9$H$9$k!#(B
%
$B$^$?!"%8%'%M%j%C%/%*%V%8%'%/%H$h$j$b(B KL1 $B%W%m%;%9$NJ}$,!"(B
$BB>$N(B KL1 $B%W%m%;%9$+$i$N%"%/%;%9$,MF0W$G$"$k$H$$$&M}M3$b$"$k!#(B

\begin{verbatim}
ns(NS, Free) :- NS = [get(ID) | NS1] |
  Free = [ID | Free1],
  ns(NS1, Free1).
ns(NS, Free) :- NS = [release(ID) | NS1] |
  Free1 = [ID | Free],
  ns(NS1, Free1).
\end{verbatim}
$B35G0E*$K$O>e$N$h$&$J(B NS $B$r:n$k$,!"(B
ID $B6u4V$,<B:]$K$OM-8B$G$"$k$3$H$r9MN8$9$kI,MW$,$"$k!#(B

$BNc$($P!"(B
$BL$;HMQ(B ID $B$,$J$$;~$K(B get $B$5$l$?$iJQ?tI=$r9-$2$k!#(B
%
$BJQ?tI=$,=L$s$@$iL$;HMQ(B ID $B$r:F7W;;$9$k!#(B

$BJQ?tI=!JG[Ns!K$N%$%s%G%/%9$rI=$9@0?t$r(B ID $B$H$7$F;HMQ$9$k!#(B


\section{ $BJQ?tI=%*%V%8%'%/%H(B \T }

\newcommand{\Add}{ add }
\newcommand{\Remove}{ remove }
\newcommand{\GetID}{ getID }
\newcommand{\Get}{ get }
\newcommand{\Set}{ set }

$BJQ?tI=%*%V%8%'%/%H$O<!$N$h$&$J$b$N$G$"$k!#(B

\( Table =\Def 2^{Dist} \ni \{ (id, var) \} \)

\begin{eqnarray}
\forall i, j;
(id_i, var_i), (id_j, var_j) \in table \Rightarrow
\nonumber\\
\Tab (id_i = id_j \Leftrightarrow var_i = var_j)
\label{eq:distinct}
\end{eqnarray}
%
$BO@M}JQ?tF1;N$NF10l@-$rH=Dj$9$k$3$H$,2DG=$G$"$k$3$H$rA0Ds$H$9$k!#(B
%
$BF10l$NO@M}JQ?t$,F10l$NJQ?tI=$K$*$$$F(B
$BJ#?t$N0[$J$k%(%s%H%j$r;}$D$3$H$O$J$$(B (\ref{eq:distinct})$B!#(B

\begin{eqnarray}
&& State = Table \times NS
\nonumber\\
&& \forall id, ns, table;
\nonumber\\
&& \Tab (ns(id) = used \Leftrightarrow (id, var) \in table) \wedge
\nonumber\\
&& \Tab (ns(id) = free \Leftrightarrow (id, var) \not\in table)
\label{eq:encapsulated}
\end{eqnarray}
%
$BJQ?tI=%*%V%8%'%/%H$O(B NS $B$HO"F0$9$k!#(B
$BJQ?tI=%*%V%8%'%/%H$O(B NS $B$NFbIt$K1#JC$7!"(B
$BB>$N%W%m%;%9$+$iD>@\A`:n$5$l$J$$$h$&$K$9$k(B
(\ref{eq:encapsulated})$B!#(B

NS $B$O<!$N%a%=%C%I$K$h$C$FJQ?tI=%*%V%8%'%/%H$rA`:n$9$k!#(B
\begin{enumerate}
\item $B%3%s%9%H%i%/%?(B {\In}Length, {\Nio}Report

\item $B%$%Y%s%H(B gc ({\Out}Length)
\\
$B%m!<%+%k%[%9%HFb$G(B GC $B$,9T$o$l$F$$$k$3$H$r<($9%$%Y%s%H!#(B
%
$BJQ?tI=%*%V%8%'%/%H$O<+J,<+?H$r?7NN0h$X%3%T!<$9$k$,!"(B
$B%(%s%H%j(B \E $B$r%3%T!<$7$J$$!#(B
%
GC $B=*N;D>8e$KGQIJ$H$7$F2s<}$5$l$?(B \E $B$N8e;OKv$r$9$k!#(B

\item io $B$+$i$N%a%C%;!<%8(B \Add \Out\id, {\Nio}Var, ({\Out}Length)
\\
io $B$,JQ?tI=%*%V%8%'%/%H$KEPO?$5$l$F$$$J$$O@M}JQ?t$rM"=P$7$?$$;~!"(B
$B$^$?$O(B io $B$,1s3V%[%9%H$+$i(B \OpenMessage $B$r<u$1<h$C$?;~$K(B
$BH/$9$k%a%C%;!<%8$G$"$k!#(B
\\
\( \Add: State \times Var \rightarrow ID \times State \)
\\
\( \Add(table, ns, var) =
\\ \Tab (id, table \cup \{ id \}, ns_1)
\\ \Where get(ns) = (id, ns_1) \)

\item io $B$+$i$N%a%C%;!<%8(B \Remove \In\ID
\\
io $B$,1s3V%[%9%H$+$i(B \M{\_\(ID\)=Removed}
$B$r<u$1<h$C$?;~$KH/$9$k%a%C%;!<%8$G$"$k!#(B
\\
\( \Remove: State \times ID \rightarrow State \)
\\
\( \Remove(table, ns, id) =
\\ \Tab (table \setminus \{ (id, var) \}, release(ns, id)) \)

\item io $B$+$i$N%a%C%;!<%8(B \GetID \Out\ID, {\Nio}Var
\\
io $B$,JQ?tI=%*%V%8%'%/%H$KEPO?:Q$_$NJ,;6O@M}JQ?t$r1s3V%[%9%H$KAw?.$7$?$$;~!"(B
$B%m!<%+%k%[%9%HFb$NO@M}JQ?t$KBP1~$9$k(B ID $B$rMW5a$9$k%a%C%;!<%8$G$"$k!#(B
\\
\( \GetID: State \times Var \rightarrow ID \)
\\
\( \GetID(table, ns, var) = id
\\ \Where (id, var) \in table \)

\item io $B$+$i$N%a%C%;!<%8(B \Get \In\ID, {\Nio}Var
\\
io $B$,1s3V%[%9%H$+$i(B \M{\_\(ID\)} $B$r<u$1<h$C$?;~$K!"(B
ID $B$KBP1~$9$k%m!<%+%k%[%9%HFb$NO@M}JQ?t$rMW5a$9$k%a%C%;!<%8$G$"$k!#(B
\\
\( \Get: State \times ID \rightarrow Var \times State \)
\\
\( \Get(table, ns, id) = (var, table, ns)
\\ \Where (id, var) \in table \)

\item io $B$+$i$N%a%C%;!<%8(B \Set \In\ID, {\In}Bound
\\
io $B$,1s3V%[%9%H$+$i(B \M{\_\(ID\)=\(Bound\)}
$B$r<u$1<h$C$?;~$KH/$9$k%a%C%;!<%8$G$"$k!#(B
\\
\( \Set: State \times Constraints \times ID \times Bound \rightarrow
\\ \Tab State \times Constraints \)
\\
\( \Set(table, ns, constraints, id, bound) =
\\ \Tab (table \setminus \{ (id, var) \}, release(ns, id),
\\ \Tab constraints \cup \{ var = bound \}) \)

\item io $B$+$i$N%a%C%;!<%8(B \Fuse \In\ID, \In\ID1
\\
io $B$,1s3V%[%9%H$+$i(B \M{\_\(ID\)=\_\(ID1\)}
$B$r<u$1<h$C$?;~$KH/$9$k%a%C%;!<%8$G$"$k!#(B
\\
\( \Fuse: State \times ID \times ID \rightarrow State \)
\\
\( \Fuse(table, ns, id, id_1) =
\\ \Tab (table \setminus \{ (id, var), (id_1, var_1) \} \cup
\\ \Tab \{ (id_1, var) \}, release(ns, id) ) \)

\item \E $B$+$i$N%a%C%;!<%8(B \Bound \In\ID, {\In}Bound
\\
\E $B$,6qBN2=$5$l$?;~$KH/$9$k%a%C%;!<%8$G$"$k!#(B
\\
\( \Bound: State \times ID \times Bound \rightarrow State \)
\\
\( \Bound(table, ns, id, bound) =
\\ \Tab remove(table, ns, id) \)

\item \E $B$+$i$N%a%C%;!<%8(B fused \In\ID, {\In}Var
\\
\E $B$,B>$N(B \E $B$HC10l2=$5$l$?;~$KH/$9$k%a%C%;!<%8$G$"$k!#(B
\\
\( fused: State \times ID \times Var \rightarrow State \)
\\
\( fused(table, ns, id, var)
\\ = (table, ns) \If id < \GetID(var)
\\ = \Remove(table, ns, id) \If id > \GetID(var) \)

\item \E $B$+$i$N%a%C%;!<%8(B removed \ID
\\
\E $B$,(B KLIC $B$N(B GC $B%U%'%$%:Cf$K?7NN0h$X%3%T!<$5$l$J$+$C$?;~!"(B
$BGQ4~$5$l$kD>A0$KH/$9$k%a%C%;!<%8$G$"$k!#(B
\end{enumerate}

\begin{verbatim}
vt(VT, T, NS) :- VT = [add(ID,X) | VT1] |
  NS = [get(ID) | NS1],
  T1 = [(ID,X) | T],
  vt(VT1, T1, NS1).
vt(VT, T, NS) :- VT = [remove(ID) | VT1] |
  remove(T, ID, T1),
  NS = [release(ID) | NS1],
  vt(VT1, T1, NS1).
vt(VT, T, NS) :- VT = [get(ID,X) | VT1] |
  get(T, ID, X, T1),
  vt(VT1, T1, NS).
vt(VT, T, NS) :- VT = [set(ID,Bound) | VT1] |
  set(T, ID, Bound, T1),
  vt(VT1, T1, NS).
vt(VT, T, NS) :- VT = [fuse(ID,ID1) | VT1] |
  fuse(T, ID, ID1, T1),
  vt([remove(ID) | VT1], T1, NS).
vt(VT, T, NS) :- VT = [bound(ID,X) | VT1] |
  remote(set(ID,X)),
  vt([remove(ID)|VT1], T, NS).
vt(VT, T, NS) :- VT = [fused(ID,ID1) | VT1] |
  remote(fuse(ID,ID1)),
  vt([remove((ID)) | VT1], T, NS).
\end{verbatim}
$B35G0E*$K$O>e$N$h$&$JJQ?tI=%*%V%8%'%/%H$r:n$j$?$$!#(B

NS $B$K(B ID $B6u4V$,8O3i$7$?$H8@$o$l$?>l9g!"<+J,<+?H$r9-$2$k!#(B
$B<+J,<+?H$r=L$a$?>l9g!"(BNS $B$K(B ID $B6u4V$r=L$a$m$H8@$&!#(B

\vspace{1em}

$B0J>e$G!"(Bdklicio $B$N@_7W$r=*$($k!#(B
$B<!>O$G$O!"(Bdklicio $B$N<BAu$r9T$&!#(B

% end
