%\input head
%\input amssym.def
%\input amssym

%\begin{document}
%\section{Appendix}

이장에서는 앞장의 MCNV알고리즘에 대한 증명및 분석을 기술한다.
여기에 사용된 형식은 [Lamp85]와 유사하다.

먼저 증명에 필요한 가정들을 기술하면 다음과 같다.

A1) 모든  클럭 $c_p,c_q$에 대해 다음이 성립한다. 여기서 $\delta_0$는 
상수이다.
\begin{eqnarray*}
	\left| c_p(T^{(0)}) - c_q(T^{(0)}) \right| < \delta_0 .
\end{eqnarray*}

조건 A1)은 최초에 모든 클럭들이 $\delta_0$-동기되어야함을 의미한다. 

$C_p^{(i)}$를 구하는 시간은 $R^{(i)}$ 구간의 마지막 $S$초라고 
생각한다. 즉, $S^{(i)} \equiv [ T^{(i+1)}$$ - S, T^{(i+1)}]$구간에 이루어진다.

A2) 만일 $i$에 대하여 클럭동기조건S1,S2가 만족되고 클럭 $c_p$가 시간
$T^{(i+1)}$까지 정상이면, 
각각의 클럭 $c_q$에 대해 $c_p$는 클럭 편차 $\Delta_{qp}$를 얻을 수 있다.
만일 $c_q$가 시간$T^{(i+1)}$까지 정상이면 $S^{(i)}$의 
어떤시간 $T_0$에 대해 다음이 성립한다.
\begin{eqnarray*}
	\left| c_p^{(i)}(T_0+\Delta_{qp}) - c_q^{(i)}(T_0) \right| 
	< \varepsilon .
\end{eqnarray*}

여기서 $p=q$이면 $\Delta=0$이다.  $\varepsilon$은 편차 측정 오차를 의미한다.

위의 가정들이 전체 클럭 시스템에서 성립한다면 다음 Lemma들을 유도할 수 있다.

\newcommand{\LEM}{\sc Lemma}
\newtheorem{lemm}{\LEM}

\begin{lemm}.\rm   % 1
 만약 i에 대해 클럭동기조건 S1이 성립하고 클럭 $c_p$ 와 $c_q$가 
$T^{(i+1)}$까지 정상이라면 다음이 성립한다.
\begin{eqnarray*}
	\left| \Delta_{qp} \right| \lesssim \delta + \varepsilon 
\end{eqnarray*}
{\gr증명}: $\Delta_{qp}$~와 $T_0$는 A2에서와 같다고 할때,
\begin{eqnarray*}
  \lefteqn{c_p^{(i)}(T_0)-c_p^{(i)}(T_0+\Delta_{qp}) }\\
  & = &
  c_p^{(i)}(T_0)-c_q^{(i)}(T_0)+c_q^{(i)}(T_0)-c_p^{(i)}(T_0+\Delta_{qp})
\end{eqnarray*}
이므로 S1과 A1으로 부터 다음이 성립하므로
\begin{eqnarray*}
  \left|{c_p^{(i)}(T_0)-c_p^{(i)}(T_0+\Delta_{qp}) }\right|
  < \delta + \varepsilon 
\end{eqnarray*}
A2과 $\rho \ll 1$의 가정으로 부터 성립함을 알 수 있다.\hfill $\blacksquare$
\end{lemm}

\begin{lemm}.\rm %2
 만약 i에 대해 클럭동기조건 S1이 성립하고 클럭 $c_p$ 와 $c_q$가 
$T^{(i+2)}$까지 정상이라면 다음이 성립한다. 여기서, $\Pi$는 임의의 수이다.
\begin{eqnarray*}
	 \left| c_p^{(i)}(T+\Pi)-\left[c_p^{(i)}(T)+\Pi \right]\right| \leq 
	\left( {\rho \over 2} \right) |\Pi| 
\end{eqnarray*}

따라서, 만일 $\rho\Pi$가 무시할 만큼 작으면 다음이 성립한다.
\begin{eqnarray*}
	c_p^{(i)}(T+\Pi) \approx c_p^{(i)}(T)+|\Pi| 
\end{eqnarray*}
{\gr증명}: A1으로부터 쉽게 성립한다.\hfill $\blacksquare$
\end{lemm}

\begin{lemm}.\rm %3
 만약 i에 대해 클럭동기조건 S1이 성립하고 클럭 $c_p$ 와 $c_q$가 
$T^{(i+1)}$까지 정상이라면 다음이 성립한다.
\begin{eqnarray*}
	\left| c_p^{(i)}(T_0+\alpha\Delta_{qp})-c_q^{(i)}(T_0) \right| 
	\lesssim 
	\varepsilon +|\alpha-1|\Delta
\end{eqnarray*}
{\gr증명}: $\rho$는 무시할 만한 크기( $10^{-6}$ ) 이므로
\begin{eqnarray*}
\lefteqn{\left| c_p^{(i)}(T_0+\alpha\Delta_{qp})-c_q^{(i)}(T_0) \right|} \\
	& = & \left| c_p^{(i)}(T_0+\Delta_{qp}+|\alpha-1|\Delta_{qp})
		- c_q^{(i)}(T_0) \right| \\
	&\approx & \left| c_p^{(i)}(T_0+\Delta_{qp}) - c_q^{(i)}(T_0)\right| 
		+ |\alpha-1|\left|\Delta_{qp}\right| 
		\mbox{\hspace{2em}[by {\sc Lemma 2}]}
		%\mbox{\hspace{5em}[by {\sc Lemma} 2]}
\end{eqnarray*}
$\left|\Delta_{qp}\right|<\Delta$이고 A2과 $\rho \ll 1$의 가정으로 부터 
성립함을 알 수 있다.
\hfill $\blacksquare$
\end{lemm}

\begin{lemm}. \rm %4
 만약 i에 대해 클럭동기조건 S1이 성립하고 클럭 $c_p$ 와 $c_q$가 
$T^{(i+2)}$까지 정상이라면 $S^{(i)}$에 속한 시간 $T$에 대해 다음이 
성립한다.
\begin{eqnarray*}
	\left| c_p^{(i)}(T+\Pi+\alpha\Delta_{qp})-c_q^{(i)}(T+\Pi) \right| 
	\lesssim \varepsilon+\rho S+ |\alpha-1|\Delta 
\end{eqnarray*}
{\gr증명}: $T_0$는 A2에서와 같다.
\begin{eqnarray*}
 \lefteqn{\left| c_p^{(i)}(T+\Pi+\alpha\Delta_{qp})-c_q^{(i)}(T+\Pi) 
		\right|} \\
  & = & \left| c_p^{(i)}(T_0+\alpha\Delta_{qp}+T-T_0+\Pi)
	-c_q^{(i)}(T_0+T-T_0+\Pi) \right| \\
  & \leq & \left| c_p^{(i)}(T_0+\alpha\Delta_{qp})-c_q^{(i)}(T_0) \right|
  + \rho \left| T-T_0 + \Pi \right|  \mbox{\hspace{1em}[by Lemma 2]} \\
  %+ \rho \left| T-T_0 + \Pi \right|  \mbox{\hspace{5em}[by Lemma 2]} \\
  & \lesssim & \varepsilon+|\alpha-1|\Delta + \rho \left| T-T_0 \right|\\
  &&		\mbox{\hspace{2em}[by {\sc Lemma 3} and the hypothesis that
		 $\rho\Pi$ is negligible]}
 % &&		\mbox{\hspace{5em}[by Lemma 3 and the hypothesis that
 %		 $\rho\Pi$ is negligible]}
\end{eqnarray*}
$T$는 $S^{(i)}$에 속해 있으므로 위의 식이 성립한다.
\hfill $\blacksquare$
\end{lemm}

\begin{lemm}. \rm
 만약 i에 대해 클럭동기조건 S1이 성립하고 클럭 $c_p$ 와 $c_q$, $c_r$모두가
$T^{(i+2)}$까지 정상이라면 $S^{(i)}$에 속한 시간 $T$에 대해 다음이 
성립한다.
\begin{eqnarray*}
	\left| c_p^{(i)}(T)+\alpha\bar{\Delta}_{rp}-
	\left[c_p^{(i)}(T)+\alpha\bar{\Delta}_{rq} \right] \right| \leq 
	2(\varepsilon+\rho S+|\alpha-1|\Delta)
\end{eqnarray*}
{\gr증명}: {\sc Lemma 1}로 부터 $\left|\Delta_{rp}\right|$와 $\left|\Delta_{rq}\right|$ 
     가 $\Delta$보다 작음을 알 수 있으므로, 
	$\bar{\Delta}_{rp}=\Delta_{rp}$이고
	$\bar{\Delta}_{rq}=\Delta_{rq}$이다. 또한 
	$\rho\Delta_{rp}$와 $\rho\Delta_{rp}$ 는 무시할 만큼 작으므로
\begin{eqnarray*}
\lefteqn{ \left| c_p^{(i)}(T)+\alpha\bar{\Delta}_{rp}-
	\left[c_p^{(i)}(T)+\alpha\bar{\Delta}_{rq} \right] \right| } \\
  & = & \left| c_p^{(i)}(T)+\alpha\Delta_{rp}-
	\left[c_q^{(i)}(T)+\alpha\Delta_{rq}\right] \right| \\
  & \approx & \left| c_p^{(i)}(T+\alpha\Delta_{rp})
        -c_q^{(i)}(T+\alpha\Delta_{qp}) \right|
		\mbox{\hspace{4em}[by {\sc Lemma 2}]}\\
		%\mbox{\hspace{5em}[by Lemma 2]}\\
  & \leq & \left| c_p^{(i)}(T+\alpha\Delta_{rp})-c_r^{(i)}(T)\right| 
    + \left| c_r^{(i)}(T)-c_q^{(i)}(T+\alpha\Delta_{qp}) \right|\\
  & \lesssim & 2(\varepsilon+\rho S+|\alpha-1|\Delta) 
		\mbox{\hspace{10em}[by Lemma 4]}
\end{eqnarray*}
이 성립한다.
\hfill $\blacksquare$
\end{lemm}

\begin{lemm}.\rm
 만약 i에 대해 클럭동기조건 S1이 성립하고 클럭 $c_p$ 와 $c_q$가
$T^{(i+2)}$까지 정상이라면 임의의 $c_r$과 $S^{(i)}$에 속한 시간 $T$에 
대해 다음이 성립한다.
\begin{eqnarray*}
	\left| c_p^{(i)}(T)+\alpha\bar{\Delta}_{rp}-
	\left[c_q^{(i)}(T)+\alpha\bar{\Delta}_{rq} \right] \right|  <
	(\delta+ 2\alpha\Delta)
\end{eqnarray*}
{\gr증명}:  $|\bar{\Delta}_{rp}|$와 $|\bar{\Delta}_{rq}|$가 $\Delta$보다 
작다는 점과 S1으로 부터 쉽게 얻을 수 있다.
\hfill $\blacksquare$
\end{lemm}

\noindent{\bf\gr정리 1.}
 A1-A2가 성립하고 만약 
\begin{eqnarray*}
 n & > & { 4\alpha-1 \over 2\alpha-1}m \\
\delta & > &\mbox{max}
	\left\{{ (2-2\alpha)n+(4\alpha-1)m \over n}\delta 
	+ { (4-2\alpha)n + (4\alpha-4)m \over n}\varepsilon \right.\\
     & & \left. \mbox{~~~~~~~~~~~~~~}
	+ \rho \left( {2(n-m)S \over n}+ R \right) 
	, \delta_0+\rho R \right\}
\end{eqnarray*}
이 성립하면, $\Sigma=\Delta$로서 MCNV알고리즘이 S1,S2를 만족한다\vspace{2ex}.

\noindent {\gr증명}: 증명은 induction방법을 사용 한다.
$i=0$일때는 A1으로 부터 성립한다. S1이 $i$에 대하여 성립한다고 
가정하고 $i+1$일때 성립함을 위의 Lemma들을 사용하여 증명하겠다.

$T^{(i+1)}$를 $T$로 간략히 표기하자.
구간 $R^{(i+1)}$에 속한 시간$T'$에 대해 다음이 성립한다. 
\begin{eqnarray*}
\lefteqn{ \left| c_p^{(i+1)}(T')- c_q^{(i+1)}(T') \right|  
      <  \left| c_p^{(i+1)}(T)- c_q^{(i+1)}(T) \right| + \rho R } \\
      %\mbox{\hspace{10em}[by A2]}\\ 
  & = & \left | c_p^{(i)}(T+\alpha\Delta_p) 
	       - c_q^{(i)}(T+\alpha\Delta_q) \right | + \rho R 
      \mbox{\hspace{1em}[from the algorithm]}\\ 
      %\mbox{\hspace{4em}[from the algorithm]}\\ 
  & \approx & \left | c_p^{(i)}(T)+\alpha\Delta_p 
	       - \left[c_q^{(i)}(T)+\alpha\Delta_q \right] \right | + \rho R 
      \mbox{\hspace{3em}[by {\sc Lemma 2}]}\\ 
      %\mbox{\hspace{6em}[by Lemma 2]}\\ 
  & = & \left | \left( {1 \over n}\right) \sum_{r=1}^{n}
 	  \left( c_p^{(i)}(T)+\alpha\bar{\Delta}_{rp} 
	- \left[c_q^{(i)}(T)+\alpha\bar{\Delta}_{rq}\right]\right)
	\right | + \rho R \\
  &&  \mbox{\hspace{13em}[by definition of $\Delta_p$ and $\Delta_q$]}\\ 
  %&&  \mbox{\hspace{14em}[by definition of $\Delta_p$ and $\Delta_q$]}\\ 
  & \lesssim & \left( {1 \over n}\right) [ 2(n-m)(\varepsilon + 
  		|\alpha-1|\Delta
	+\rho S) + m(\delta + 2 \alpha\Delta) ] + \rho R\\
  &&    \mbox{\hspace{15em}[by {\sc Lemma 5,Lemma 6}]} 
  %&&    \mbox{\hspace{14em}[by Lemma 5,Lemma 6]} 
\end{eqnarray*}
$\Delta \approx \delta + \varepsilon$이므로 위의 식을 정리하면 
$R^{(i+1)}$에 속한 시간$T'$에 대해 
\begin{eqnarray*}
\left| c_p^{(i+1)}(T')- c_q^{(i+1)}(T') \right|  < \delta 
\end{eqnarray*}
이 성립함을 알 수 있다. 따라서 {\gr정리 1}은 성립한다.
\hfill $\blacksquare$
%\end{document}
