%\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}