\documentclass[12pt]{article} \usepackage{latexsym} %Definitionen werden hier eingetragen \newcommand{\emi}[1]{{\em #1\/}} \newcommand{\ppI}[1]{{\hat{#1}}} \newcommand{\pppI}[1]{{\check{#1}}} \newcommand{\pB}[1]{{\tilde{\B{#1}}}} \newcommand{\emop}[1]{\mbox{\emi{#1}}} \newcommand{\indi}{I} \newcommand{\B}[1]{{\mbox{\boldmath$#1$}}} \newcommand{\VB}[1]{\vec{{\mbox{\boldmath$#1$}}}} \newcommand{\OA}{\B{\cal OA}} \newcommand{\CV}{\B{\cal CV}} \newcommand{\M}{\B{\cal M}} \newcommand{\ol}{\bar{l}} \newcommand{\od}{\bar{d}} \newcommand{\opi}{\bar{\pi}} \newcommand{\BZGA}{\mbox{\boldmath$2G$}_A} \newcommand{\Br}[1]{{\mbox{\boldmath${#1}_{\mbox{\boldmath$\rho$}}$}}} \newcommand{\hmax}{\mathop{\mbox{\rm $h$-max}}\limits} \newcommand{\mhmax}{\mathop{\overline{\mbox{\rm $h$-max}}}\limits} \newcommand{\pref}[2]{#1 \ref{#2} & \pageref{#2}} \newcommand{\myremarks}{\noindent {\bf Remarks}} \newcommand{\refp}[1]{\ref{#1} (p.~\pageref{#1})} \newcommand{\nccup}{\sqcup} \renewcommand{\o}{f_o} \renewcommand{\c}{f_c} \renewcommand{\d}{f_s} \newcommand{\e}{f_a} \renewcommand{\a}{f_u} \newcommand{\dn}{f_n} \newtheorem{lem}{Lemma} \newtheorem{thm}{Theorem} \newtheorem{defin}{Definition} \newtheorem{asum}{Assumption} %%%%%%% \hyphenation{pa-ra-me-ters} \newenvironment{rmm} {\begin{trivlist}\item[\hskip\labelsep{\textbf{Remarks\,}}]} {\end{trivlist}} \newcount\penum \def\pitem{\ifnum\penum>1\par\fi\the\penum. \advance\penum by1} \penum=1 %%%%%%%%% \title{Orthogonal Accuracy Clock Synchronization} \author{Ulrich Schmid\\ %\vspace{-1mm}\normalsize Technische Universit\"at Wien\\ %\vspace{-1mm}\normalsize Department of Automation\\ %\vspace{-1mm}\normalsize Treitlstra\ss e~1, A-1040 Vienna\\ s@auto.tuwien.ac.at} \date{July 31, 2000} \begin{document} %% %% CJTCS frontmatter, Insert after \begin{document} %% \def\registered{\({}^{\ooalign% {\hfil\raise.07ex\hbox{{\tiny\textup{R}}}% \hfil\crcr\scriptsize\mathhexbox20D\cr}}\)} \begin{titlepage} \pagenumbering{roman} \null\vfil\vskip 60pt \begin{center} {\Huge\bf Chicago\nolinebreak[1] Journal of Theoretical Computer\nolinebreak[1] Science\par} \vskip 3em {\huge\it The MIT Press\par} \end{center} \par\vskip 1.5em {\Large \begin{center} Volume 2000, Article 3\\ \textit{Orthogonal Accuracy Clock Synchronization} \end{center} } \par\noindent ISSN 1073--0486. MIT Press Journals, Five Cambridge Center, Cambridge, MA 02142-1493 USA; (617)253-2889; \emph{journals-orders@mit.edu, journals-info{\allowbreak}@mit.edu}. Published one article at a time in \LaTeX\ source form on the Internet. Pagination varies from copy to copy. For more information and other articles see \begin{itemize} \item \emph{http://mitpress.mit.edu/CJTCS/} \item \emph{http://www.cs.uchicago.edu/publications/cjtcs/} \item \emph{ftp://mitpress.mit.edu/pub/CJTCS} \item \emph{ftp://cs.uchicago.edu/pub/publications/cjtcs} \end{itemize} \par\noindent The \emph{Chicago Journal of Theoretical Computer Science} is abstracted or indexed in \emph{ Research Alert\registered, SciSearch\registered, Current Contents\registered/Engineering Computing \& Technology}, and \emph{CompuMath Citation Index\registered.} \par\noindent\copyright 1999 The Massachusetts Institute of Technology. Subscribers are licensed to use journal articles in a variety of ways, limited only as required to ensure fair attribution to authors and the journal, and to prohibit use in a competing commercial product. See the journal's World Wide Web site for further details. Address inquiries to the Subsidiary Rights Manager, MIT Press Journals; (617)253-2864; \emph{journals-rights@mit.edu}.\pagebreak[2] \par\noindent The \emph{Chicago Journal of Theoretical Computer Science} is a peer-reviewed scholarly journal in theoretical computer science. The journal is committed to providing a forum for significant results on theoretical aspects of all topics in computer science. \par \begin{trivlist} \item[\emph{Editor-in-Chief:}] Janos Simon \item[\emph{Consulting Editors:}] Joseph Halpern, Eric Allender, Raimund Seidel \item[\emph{Editors:}] \begin{tabular}[t]{lll} Martin Abadi & Greg Frederickson & John Mitchell \\ Pankaj Agarwal & Andrew Goldberg & Ketan Mulmuley \\ Eric Allender & Georg Gottlob & Gil Neiger \\ Tetsuo Asano & Vassos Hadzilacos & David Peleg \\ Laszl\'o Babai & Juris Hartmanis & Andrew Pitts \\ Eric Bach & Maurice Herlihy & James Royer \\ Stephen Brookes & Ted Herman & Alan Selman \\ Jin-Yi Cai & Stephen Homer & Nir Shavit \\ Anne Condon & Neil Immerman & Eva Tardos \\ Cynthia Dwork & Howard Karloff & Sam Toueg \\ David Eppstein & Philip Klein & Moshe Vardi \\ Ronald Fagin & Phokion Kolaitis & Jennifer Welch \\ Lance Fortnow & Stephen Mahaney & Pierre Wolper \\ Steven Fortune & Michael Merritt \end{tabular} \vspace{1ex} \item[\emph{Managing Editor:}] Michael J.\ O'Donnell \vspace{1ex} \item[\emph{Electronic Mail:}] \emph{chicago-journal@cs.uchicago.edu} \end{trivlist} \vfil\null \end{titlepage} \maketitle \pagenumbering{arabic} %% %% End frontmatter code %% %\bibliographystyle{alpha} \maketitle \begin{abstract} We present description and analysis of a novel {\em orthogonal accuracy\/} clock synchronization algorithm (OA), which takes care of both precision and accuracy with respect to external time. It is based upon the generic algorithm introduced in \cite{SS97:1} and utilizes a convergence function based on Marzullo's fault-tolerant intersection function. As far as precision is concerned, we show that OA has the same worst-case performance as the well-known fault-tolerant midpoint algorithm of \cite{LL88}. However, relying upon a perception-based hybrid fault model and a fairly realistic system model, our results are valid for a wide variety of node and link faults and apply to very high-precision applications as well: Impairments due to clock granularity and discrete rate adjustment cannot be ignored here anymore. Our accuracy analysis focuses on the nodes' local accuracy interval, which provides the application with an on-line bound on the current deviation from external time. We show that this bound could get larger than twice the necessary lower bound (``traditional accuracy''), hence OA is definitely suboptimal in this respect. \end{abstract} % Keywords: interval-based clock synchronization, fault-tolerant % distributed real-time systems, convergence functions, precision % analysis, accuracy intervals, clock granularity, % hybrid fault models, Marzullo function. \section{Introduction} \label{Introduction} Modern distributed systems usually run applications that rely on a global notion of time. Indeed, most algorithms for (fault-tolerant) distributed systems are considerably simplified and improved with respect to performance when mutually synchronized clocks are available (\cite{Lis93}). In addition, since time rules daily life and hence most commercial computer applications, a well-defined relation between system time and external standard time \emi{Universal Time Coordinated} (UTC) becomes increasingly important as well. Ignoring non-fault-tolerant solutions based on centralized clocks, the usual approach is to equip each node $p$ of a distributed system with a local clock $C_p(t)$ that continuously displays $p$'s view of system time. Providing mutually synchronized (``precise'') local clocks is known as the internal synchronization problem, and numerous solutions have been worked out under the term fault-tolerant clock synchronization, see \cite{YM93} for a bibliography. Providing mutually synchronized clocks that also relate to UTC (being ``accurate'' as well) is usually termed the external synchronization problem, due to the fact that UTC is provided externally to the system. A comprehensive collection of papers describing recent efforts in this area may be found in \cite{Sch97}. Among those is our research on \emi{clock validation} introduced in \cite{Sch95}, which approaches the external synchronization problem by verifying whether the usually highly accurate (but possibly faulty) ``authoritative time'' provided by UTC time sources is consistent with the less accurate (but reliable) ``validation time'' formed by exchanging the information of all the local clocks in the system. If so, the authoritative time is accepted ---if not, it is discarded and the nodes rely upon the validation time instead. The latter situation is encountered in case of failures\footnote{Our experimental evaluation (\cite{HS97}) of the failures of six different GPS timing receivers revealed an average error probability of about $10^{-6}$, with several different failure modes.} or unavailability of time information from UTC time sources, where clock validation obviously ``degenerates'' to pure internal synchronization. Therefore, the clock synchronization algorithm employed for computing the validation time must not only ensure precision but has to maintain high accuracy as well. Traditional internal synchronization algorithms are ill-suited for coping with this requirement. In fact, although worst case accuracy bounds have been provided for most existing algorithms, it is nevertheless true that a static worst-case bound is not representative for the ``average'' execution. A promising alternative are interval-based algorithms introduced in Marzullo's thesis \cite{Mar84} and further exploited in \cite{Lam87}, \cite{Mar90}, \cite{OSF92}, \cite{Sch95}, \cite{Mil95}, \cite{BI96}, \cite{SS97:1}, \cite{Scho97}, where local time at external time~$t$ is expressed as an interval that contains $t$. Given a set of such intervals from different nodes, a usually smaller interval that contains $t$ can be determined by means of a suitable interval-valued convergence function. Since accuracy bounds are maintained dynamically (``on-line'') here, they are obviously representative for the ``average'' execution. In \cite{SS97:1}, we presented and analyzed a generic interval-based clock synchronization algorithm suitable for computing the validation time in our clock validation framework. According to the exposition above, it maintains bounded precision when started from an initially synchronized state and takes care of accuracy intervals as well. However, the algorithm is generic in the sense that the convergence function employed for computing the clock adjustments was left unspecified. As in \cite{Sch86}, all results (worst-case precision, accuracy, maximum adjustment, etc.)\ were hence expressed in terms of a few characteristic parameters of the convergence function. In order to determine the performance of a particular instance of the algorithm, all that needs to be done is to evaluate the characteristic parameters and to plug those into the generic results. This paper provides description and detailed analysis of the {\em orthogonal accuracy algorithm\/} OA obtained by employing the {\em orthogonal accuracy convergence function\/} $\B{\cal OA}$ in the generic algorithm of \cite{SS97:1}. It is organized as follows: Section~\ref{sec:2} introduces our interval-based clock synchronization framework, including the generic algorithm (Subsection~\ref{Generic Algorithm} and Appendix~B), the generic precision analysis (Subsection~\ref{Generic Precision Analysis} and Appendix~C), and the perception-based hybrid fault model (Subsection~\ref{Fault Model}). Section~3 is devoted to an in-depth investigation of Marzullo's function $\B{\cal M}$, which plays a central role in the analysis of $\B{\cal OA}$ in Section~4 and Appendix~A. Our major results, namely, worst-case bounds for accuracy and precision of OA, are provided in Section~5. Some conclusions in Section~6, an appended road-map showing the interdependency of the major parts of the analysis, and a glossary eventually round off the paper. \section{Interval-based Clock Synchronization} \label{sec:2} The core idea of the interval-based paradigm introduced in \cite{Mar84} is to {\em represent\/} real-time (= external time)~$t$ not just by a time-dependent local clock value $C(t)$, but rather by a {\em local interval clock\/} $\B{C}(t)=[C(t)-\alpha^-(t),C(t)+\alpha^+(t)]$\label{pag:clock}. Any $\B{C}(t)$ must be maintained appropriately to secure the {\em accurateness property\/} $t\in\B{C}(t)$, which is of course increasingly meaningful if $\B{\alpha}(t)$ becomes small. Note carefully that an interval, that is, a range of values where $t$ could lie, is the best deterministic information one can get in practice, since the exact value of $t$ is usually not known explicitly: Even the {\em 1~pulse-per-second\/} (1pps) output of a GPS timing receiver, which indicates something like ``now it is 10:00,'' actually means ``the real-time when the 1pps signal actually occurred lies somewhere within 10:00 $\pm$ 150~ns'', see \cite{Dan97}, \cite{HS97} for more information. Interval clock readings $\B{A}=[T-\alpha^-,T+\alpha^+] = [T\pm\B{\alpha}]$ taken at some fixed real-time~$t_0$, that is, $\B{A}=\B{C}(t_0)$, as well as intervals derived from those by means of the basic operations introduced in Subsection~\ref{Generic Algorithm}, are called {\em accuracy intervals\/}. They are the basic units of information processed by interval-based clock synchronization algorithms and disseminated via messages, and consist of $\B{A}$'s {\em reference point\/} (logical time\footnote{Note that we employ the usual notation of lower case letters like $t$ for real-time values and upper case letters like $T$ for logical time ones.}) $T$ and its {\em interval of accuracies\/} $\B{\alpha}$ taken relatively to the reference point. Note carefully that, given some $\B{A}=[T\pm\B{\alpha}]$ representing real-time~$t$, we can never assume $T=t$, and not even $t\in\B{A}$ if $\B{A}$ is not accurate, that is, faulty. \subsection{Generic Algorithm} \label{Generic Algorithm} The system model of \cite{SS97:1} assumes a distributed system consisting of $n$~{\em nodes\label{pag:noden}\/}, which communicate with each other by message passing over a fully connected point-to-point or broadcast network. Each node is equipped with a {\em processor\/} (with integer arithmetic only) for executing the clock synchronization algorithm, a {\em network interface\/}, and a local interval clock $\B{C}_p(t)$ that continuously displays $p$'s local accuracy interval. Consult \cite{SKMNCK99} for details of an advanced prototype implementation based upon our {\em Network Time Interface\/} M-Module. An interval-based clock synchronization algorithm is in charge of maintaining $\B{C}_p(t)$ in a way that secures the following properties: \begin{itemize} \itemsep-3pt \item[(P)] {\em Precision requirement\/}: There is some fixed {\em precision\/} $\pi_{\max}\geq0$ such that $|C_p(t)-C_q(t)|\leq \pi_{\max}$ for all nodes $p$, $q$ that are non-faulty up to real-time~$t$. \item[(A)] {\em Accuracy requirement\/}: The interval of accuracies $\B{\alpha}_p(t)$ is such that $-\alpha_p^+(t)\leq C_p(t)-t \leq\alpha_p^-(t)$ for all nodes~$p$ that are non-faulty up to real-time $t$. \end{itemize} Note that we restrict our attention to $\alpha_p^+(t), \alpha_p^-(t) = {\cal O}(t)$, with the implied constant\footnote{Throughout this paper, we use the ${\cal O}(\cdot)$-notation to characterize the order of magnitude of neglected terms. An expression like $\alpha_p^-(t)={\cal O}(t)$ means that there is some (reasonably small) fixed constant $M>0$ such that $|\alpha_p^-(t)|\leq M|t|$.} $M$ being (much) smaller than~1. This forces $C_p(t)$ to be within a linear envelope of real-time, thereby excluding ``degenerated'' cases like $C_p(t)\equiv0$ (see \cite{DHS86}). The generic interval-based clock synchronization algorithm of \cite{SS97:1} (restated as Definition~\ref{def:OAalgorithm} in Appendix~B) employs the usual round-based structure of traditional internal synchronization algorithms. Starting from an initially synchronized state, where (P) and (A) is somehow enforced, any node periodically executes the following steps whenever its local clock reads $kP$, $k\geq1$: \begin{enumerate} \itemsep-3pt \item Initiation of a {\em full message exchange\/} (FME) to provide each node with the accuracy intervals of all other nodes in the system. \item {\em Preprocessing\/} of the set of received accuracy intervals to make them all ``compatible'', that is, represent the same real-time. \item Application of a suitable interval-valued {\em convergence function\/} to the set of preprocessed intervals to compute and subsequently apply a clock correction upon $\B{C}_p(t)$ for resynchronization. \item Keeping track of real-time by means of $\B{C}_p(t)$ up to the next resynchronization. \end{enumerate} The algorithm relies upon two basic operations called drift compensation and delay compensation. \emi{Drift compensation} ---required in Step~2 and~4 of the algorithm--- allows to shift (``drag'') an accuracy interval in time by means of the local clock while maintaining accurateness of the resulting interval. Since the local clock can drift with respect to real-time, this requires sufficient enlargement (``deterioration'') of positive and negative accuracy according to \cite[Def.~5]{SS97:1}. The following Figure~\ref{fig:deter} shows an example of drift compensated intervals based upon some initial interval $\B{A}_0=[T_0\pm\B{\alpha}]$ representing $t_0$, which is of course assumed to be accurate (hence $t_0\in\B{A}_0$). This initial accuracy interval is then dragged to real-times~$t_i$ characterized by, say, $C(t_i)=T_i=T_0+i\Delta T$ for some fixed $\Delta T$, $i\geq1$, leading to accuracy intervals $\B{A}_i=\B{A}_0+[i\Delta T \pm i\Delta T\B{\rho}]$. We assume a fast but deaccelerating clock with a maximum drift $\in[-\rho,\rho]$ here and ignore advanced issues like clock granularity and discrete rate adjustment uncertainty for simplicity. For accurateness, deterioration must ensure that any $\B{A}_i$ intersects with the line $T=t$. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{figure}[htb] \begin{center} \unitlength=0.65mm \special{em:linewidth 0.4pt} \linethickness{0.4pt} \begin{picture}(140.00,90.00)(15,0) \put(15.00,10.00){\vector(1,0){125.00}} \put(20.00,5.00){\vector(0,1){85.00}} \put(140.00,7.00){\makebox(0,0)[ct]{{\footnotesize $T$}}} \put(17.00,90.00){\makebox(0,0)[rc]{{\footnotesize $t$}}} \put(25.00,15.00){\line(1,1){65.00}} \put(83.00,75.00){\makebox(0,0)[rc]{{\footnotesize real-time $T=t$}}} \bezier{452}(28.00,15.00)(81.00,42.00)(119.00,80.00) \put(40.00,9.00){\line(0,1){2.00}} \put(60.00,9.00){\line(0,1){2.00}} \put(80.00,9.00){\line(0,1){2.00}} \put(40.00,21.00){\circle*{2.00}} \put(28.33,20.67){\rule{17.33\unitlength}{0.67\unitlength}} \put(28.33,20.00){\line(0,1){2.00}} \put(46.00,20.00){\line(0,1){2.00}} \put(59.67,33.00){\circle*{2.00}} \put(80.00,46.33){\circle*{2.00}} \put(40.00,6.33){\makebox(0,0)[ct]{{\footnotesize $T_0=C(t_0)$}}} \put(60.00,6.33){\makebox(0,0)[ct]{{\footnotesize $T_1$}}} \put(80.00,6.33){\makebox(0,0)[ct]{{\footnotesize $T_2$}}} \put(17.00,21.00){\makebox(0,0)[rc]{{\footnotesize $t_0$}}} \put(17.00,33.00){\makebox(0,0)[rc]{{\footnotesize $t_1$}}} \put(17.00,46.00){\makebox(0,0)[rc]{{\footnotesize $t_2$}}} \put(100.00,9.00){\line(0,1){2.00}} \put(100.00,6.33){\makebox(0,0)[ct]{{\footnotesize $T_3=C(t_3)$}}} \put(100.00,62.33){\circle*{2.00}} \put(17.00,61.67){\makebox(0,0)[rc]{{\footnotesize $t_3$}}} \put(58.33,62.33){\line(0,0){0.00}} \put(49.00,21.00){\makebox(0,0)[lc]{{\footnotesize $[T_0\pm\B{\alpha}]$}}} \put(50.00,12.00){\makebox(0,0)[cb]{{\footnotesize $\Delta T$}}} \put(70.00,12.00){\makebox(0,0)[cb]{{\footnotesize $\Delta T$}}} \put(90.00,12.00){\makebox(0,0)[cb]{{\footnotesize $\Delta T$}}} \put(100.00,46.00){\makebox(0,0)[lc]{{\footnotesize $[T_0\pm\B{\alpha}]+[2\Delta T\pm2\Delta T\B{\rho}]$}}} \put(21.00,21.00){\line(1,0){1.00}} \put(23.00,21.00){\line(1,0){1.00}} \put(25.00,21.00){\line(1,0){1.00}} \put(27.00,21.00){\line(1,0){1.00}} \put(40.00,19.00){\line(0,-1){1.00}} \put(40.00,17.00){\line(0,-1){1.00}} \put(40.00,15.00){\line(0,-1){1.00}} \put(40.00,13.00){\line(0,-1){1.00}} \put(25.00,21.00){\vector(1,0){1.00}} \put(40.00,15.00){\vector(0,-1){1.00}} \put(39.00,32.00){\line(0,1){2.00}} \put(71.00,32.00){\line(0,1){2.00}} \put(49.00,45.00){\line(0,1){2.00}} \put(59.00,61.00){\line(0,1){2.00}} \put(96.00,45.00){\line(0,1){2.00}} \put(121.00,61.00){\line(0,1){2.00}} \put(117.00,75.00){\makebox(0,0)[lc]{{\footnotesize (inverse) local clock}}} \put(75.00,33.00){\makebox(0,0)[lc]{{\footnotesize $[T_0\pm\B{\alpha}]+[\Delta T\pm\Delta T\B{\rho}]$}}} \put(125.00,62.00){\makebox(0,0)[lc]{{\footnotesize $[T_0\pm\B{\alpha}]+[3\Delta T\pm3\Delta T\B{\rho}]$}}} \put(49.00,45.67){\rule{47.00\unitlength}{0.67\unitlength}} \put(59.00,61.67){\rule{62.00\unitlength}{0.67\unitlength}} \put(39.00,32.67){\rule{32.00\unitlength}{0.67\unitlength}} \end{picture} \caption{\em Example of drift compensation in case of a fast but deaccelerating clock with maximum drift $\in [-\rho,\rho]$. Proper deterioration ensures intersection with the line $t=T$.} \label{fig:deter} \end{center} \end{figure} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% The \emi{delay compensation} operation employed in Step~2 of the algorithm maintains accurateness of intervals that are transmitted over a network experiencing variable transmission delays $\delta'\in [\delta\pm\B{\varepsilon}]$, with $\delta$ denoting the deterministic part of the delay. As before, positive and negative accuracy must be enlarged according to \cite[Def.~6]{SS97:1} to account for the maximum uncertainty in transmission delay~$\B{\varepsilon}$. This is illustrated in Figure~\ref{fig:transmit}, where it is assumed that the actual transmission delay is $\delta'>\delta$ and the sender node~$p$'s clock is drift-free, that is, progresses as real-time does. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{figure}[htb] \begin{center} \unitlength=0.75mm \special{em:linewidth 0.4pt} \linethickness{0.4pt} \begin{picture}(144.00,87.00) \put(10.00,50.00){\vector(1,0){130.00}} \put(144.00,50.00){\makebox(0,0)[lc]{{\footnotesize $t$}}} \put(90.00,49.00){\dashbox{1.00}(30.00,2.00)[cc]{}} \put(99.00,51.00){\line(0,-1){2.00}} \put(24.33,49.00){\rule{1.00\unitlength}{2.00\unitlength}} \put(104.33,49.00){\rule{1.00\unitlength}{2.00\unitlength}} \put(25.00,58.00){\vector(1,0){80.00}} \put(105.00,58.00){\vector(-1,0){80.00}} \put(62.00,43.00){\makebox(0,0)[cb]{{\footnotesize $\delta$}}} \put(65.00,59.00){\makebox(0,0)[cb]{{\footnotesize $\delta'$}}} \put(95.00,52.00){\makebox(0,0)[cb]{{\footnotesize $\varepsilon^-$}}} \put(110.00,52.00){\makebox(0,0)[cb]{{\footnotesize $\varepsilon^+$}}} \put(10.00,75.00){\vector(1,0){130.00}} \put(144.00,75.00){\makebox(0,0)[lc]{{\footnotesize $T$}}} \put(20.00,75.00){\circle*{2.00}} \put(15.33,74.67){\rule{14.67\unitlength}{0.67\unitlength}} \put(15.33,74.00){\line(0,1){2.00}} \put(30.00,74.00){\line(0,1){2.00}} \put(100.00,75.00){\circle*{2.00}} \put(95.33,74.67){\rule{14.67\unitlength}{0.67\unitlength}} \put(95.33,74.00){\line(0,1){2.00}} \put(110.00,74.00){\line(0,1){2.00}} \put(10.00,23.00){\vector(1,0){130.00}} \put(144.00,23.00){\makebox(0,0)[lc]{{\footnotesize $T$}}} \put(94.00,23.00){\circle*{2.00}} \put(85.00,22.67){\dashbox{1.00}(30.00,0.67)[cc]{}} \put(85.00,22.00){\line(0,1){2.00}} \put(115.00,22.00){\line(0,1){2.00}} \put(80.00,22.67){\rule{5.00\unitlength}{0.67\unitlength}} \put(115.00,22.67){\rule{10.00\unitlength}{0.67\unitlength}} \put(125.00,22.00){\line(0,1){2.00}} \put(80.00,22.00){\line(0,1){2.00}} \put(83.00,17.00){\makebox(0,0)[ct]{{\footnotesize $\alpha^-$}}} \put(120.00,17.00){\makebox(0,0)[ct]{{\footnotesize $\alpha^+$}}} \put(25.00,42.00){\vector(1,0){74.00}} \put(99.00,42.00){\vector(-1,0){74.00}} \put(99.00,48.00){\line(0,-1){1.00}} \put(99.00,46.00){\line(0,-1){1.00}} \put(99.00,44.00){\line(0,-1){1.00}} \put(99.00,42.00){\line(0,-1){1.00}} \put(94.00,34.00){\line(0,-1){1.00}} \put(94.00,30.00){\line(0,-1){1.00}} \put(94.00,28.00){\line(0,-1){1.00}} \put(94.00,26.00){\line(0,-1){1.00}} \put(25.00,48.00){\line(0,-1){1.00}} \put(25.00,46.00){\line(0,-1){1.00}} \put(25.00,44.00){\line(0,-1){1.00}} \put(23.00,87.00){\makebox(0,0)[cb]{{\footnotesize $\B{A}_p=[T_p\pm\B{\alpha}]$}}} \put(103.00,87.00){\makebox(0,0)[cb]{{\footnotesize $\B{A}_p'=[T_p'\pm\B{\alpha}]$}}} \put(22.00,72.00){\makebox(0,0)[lt]{{\footnotesize $T_p$}}} \put(102.00,72.00){\makebox(0,0)[lt]{{\footnotesize $T_p'=T_p+\delta'$}}} \put(97.00,26.00){\makebox(0,0)[lb]{{\footnotesize $T_q^p=T_p+\delta$}}} \put(25.00,42.00){\line(0,-1){1.00}} \put(102.00,9.00){\makebox(0,0)[ct]{{\footnotesize $\B{A}_q^p=[T_q^p\pm\B{\alpha}+\B{\varepsilon}]$}}} \put(-9.00,78.00){\makebox(0,0)[lb]{{\footnotesize node $p$}}} \put(-9.00,26.00){\makebox(0,0)[lb]{{\footnotesize node $q$}}} \put(27.00,48.00){\makebox(0,0)[lt]{{\footnotesize $t_p$}}} \put(107.00,47.00){\makebox(0,0)[lt]{{\footnotesize $t_q^p$}}} \put(-9.00,72.00){\makebox(0,0)[lt]{{\footnotesize (Sender)}}} \put(-9.00,20.00){\makebox(0,0)[lt]{{\footnotesize (Receiver)}}} \put(105.00,59.00){\line(0,-1){1.00}} \put(105.00,57.00){\line(0,-1){1.00}} \put(105.00,55.00){\line(0,-1){1.00}} \put(105.00,53.00){\line(0,-1){1.00}} \put(25.00,59.00){\line(0,-1){1.00}} \put(25.00,57.00){\line(0,-1){1.00}} \put(25.00,55.00){\line(0,-1){1.00}} \put(25.00,53.00){\line(0,-1){1.00}} \put(25.00,50.00){\line(-1,5){5.00}} \put(105.00,50.00){\line(-1,5){5.00}} \put(20.00,83.00){\vector(1,0){80.00}} \put(100.00,83.00){\vector(-1,0){80.00}} \put(60.00,84.00){\makebox(0,0)[cb]{{\footnotesize $\delta'$}}} \put(100.00,84.00){\line(0,-1){1.00}} \put(100.00,82.00){\line(0,-1){1.00}} \put(100.00,80.00){\line(0,-1){1.00}} \put(100.00,78.00){\line(0,-1){1.00}} \put(20.00,84.00){\line(0,-1){1.00}} \put(20.00,82.00){\line(0,-1){1.00}} \put(20.00,80.00){\line(0,-1){1.00}} \put(20.00,78.00){\line(0,-1){1.00}} \put(20.00,74.00){\line(0,-1){1.00}} \put(20.00,72.00){\line(0,-1){1.00}} \put(20.00,70.00){\line(0,-1){1.00}} \put(20.00,68.00){\line(0,-1){1.00}} \put(20.00,66.00){\line(0,-1){1.00}} \put(20.00,64.00){\line(0,-1){1.00}} \put(20.00,62.00){\line(0,-1){1.00}} \put(20.00,60.00){\line(0,-1){1.00}} \put(20.00,58.00){\line(0,-1){1.00}} \put(20.00,56.00){\line(0,-1){1.00}} \put(20.00,54.00){\line(0,-1){1.00}} \put(20.00,52.00){\line(0,-1){1.00}} \put(20.00,50.00){\line(0,-1){1.00}} \put(20.00,48.00){\line(0,-1){1.00}} \put(20.00,46.00){\line(0,-1){1.00}} \put(20.00,44.00){\line(0,-1){1.00}} \put(20.00,42.00){\line(0,-1){1.00}} \put(20.00,40.00){\line(0,-1){1.00}} \put(20.00,38.00){\line(0,-1){1.00}} \put(20.00,36.00){\line(0,-1){1.00}} \put(20.00,34.00){\line(0,-1){1.00}} \put(57.00,35.00){\makebox(0,0)[cb]{{\footnotesize $\delta$}}} \put(20.00,34.00){\vector(1,0){74.00}} \put(94.00,34.00){\vector(-1,0){74.00}} \put(105.00,49.00){\line(-2,-5){10.33}} \put(94.00,32.00){\line(0,-1){1.00}} \put(89.00,21.00){\makebox(0,0)[ct]{{\footnotesize $\varepsilon^-$}}} \put(104.00,21.00){\makebox(0,0)[ct]{{\footnotesize $\varepsilon^+$}}} \end{picture} \caption{\em Example of delay compensation when sending $\protect\B{I}$ from node~$p$ to~$q$. The received interval must be enlarged by $\protect\B{\varepsilon}$ to secure accurateness.} \label{fig:transmit} \end{center} \end{figure} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% The middle time axis represents real-time, whereas the upper and lower one show local time at node~$p$ and $q$, respectively. A line connecting two points at different axes, like $T_p$ and $t_p$, indicates the ``represents'' relation; since $\B{A}_p$ is assumed to be accurate, we must have $t_p\in\B{A}_p$ here. When interpreting Figure~\ref{fig:transmit}, one should consider the intervals $\B{A}_p$ and $\B{A}_q^p$ as ``fixed'' (since they do not depend upon the actual transmission delay $\delta'$), whereas the reception time $t_q^p$ and hence the interval $\B{A}_p'$ vary with~$\delta'$. It is apparent that $t_q^p\in\B{A}_q^p$ is always maintained if $t_q^p$ remains within the dash-boxed region of the $t$-axis, that is, if $\delta'\in[\delta\pm\B{\varepsilon}]$. Together, drift compensation and delay compensation are employed to make all received intervals compatible, that is, represent a common real-time~$t_q^R$: For an accuracy interval $\B{A}_p$ sent by node~$p\neq q$ at real-time~$t_p$, delay compensation is applied to provide the receiver~$q$ with an interval $\B{A}_q^p$ that covers the sender's current accuracy interval at the real-time of reception~$t_q^p$. This interval $\B{A}_q^p$ is then dragged locally by means of the receiver's clock to some (common) point in real-time $t_q^R$ defined by $C_q(t^R_q)=T^R_q$, requiring an appropriate drift compensation to obtain the final accuracy interval $\B{I}_q^p$. Provided that $T^R_q$ is chosen large enough to ensure that the intervals of all non-faulty nodes can be received and processed, it follows by construction that $\B{I}_q^p$ is accurate if (1) $\B{A}_p$ was accurate, (2) transmission delay was not excessive, and (3) the receiver $q$ is not faulty. Finally, a suitable {\em convergence function\/} is applied to the set $\B{\cal I}_q$ of node~$q$'s intervals $\B{I}_q^p$ in Step~3, which provides a (small) interval that both contains real-time $t^R_q$ (that is, is accurate) and enhances precision ---despite some possibly faulty $\B{I}_q^p$'s. Fortunately, only a few properties of the convergence function are actually required for predicting the entire clock synchronization algorithm's worst-case performance. Hence, the appropriate analysis in \cite{SS97:1} was conducted for a generic convergence function $\B{\cal CV}$, which can be any interval-valued function that satisfies certain properties stated in Definition~\ref{def:charconv} in Appendix~C. \subsection{Generic Precision Analysis} \label{Generic Precision Analysis} Since all operations used in our interval-based clock synchronization algorithm, namely, drift compensation, delay compensation, and finally application of the convergence function, are explicitly designed to preserve accurateness of the intervals involved, it is clear that accurateness of the local interval clocks $\B{C}_p(t)$ of all non-faulty nodes is maintained during all rounds. Apart from the requirement of being accurate, which is a property of any single accuracy interval, however, we also have the precision requirement that applies to (the reference points of) a set of accuracy intervals. Precision and accuracy are in fact almost\footnote{They are not totally independent, as the computed reference point could lie outside the accuracy interval, see Figure~\ref{fig:accprec}.} independent of each other, since the reference point can in principle be placed arbitrarily within the accuracy interval. In the remainder of this section, we will briefly sketch the interval-based precision analysis framework established in \cite{SS97:1}. To that end, we first introduce the basic notation used throughout the paper: Our elementary objects are real intervals $\B{I}=[x,y]$, $x\leq y$, with {\em lower edge\/} $x=\mbox{left}(\B{I})$ and {\em upper edge\/} $y=\mbox{right}(\B{I})$; the {\em empty interval\/} $\emptyset$ satisfies $\not\!\!\exists t: t\in\emptyset$. For an interval $\B{I}=[x,y]$, $|\B{I}|=y-x$ denotes its {\em length\/} and $\mbox{center}(\B{I})=(x+y)/2$ its {\em centerpoint\/}. The {\em sum\/} of two intervals is defined by $[x,y]+[u,v]=[x+u,y+v]$, the {\em scalar product\/} by $s\cdot[x,y]=[sx,sy]$ for $s\geq 0$, and the {\em translation\/} by $\B{I}+a=\B{I}+[a,a]=[x+a,y+a]$ for some arbitrary scalar $a$. For two intervals $[x,y]$, $[u,v]$, the {\em intersection\/} is $[x,y]\cap[u,v]=[\max\{x,u\},\min\{y,v\}]$ if $u\leq y$, $v\geq x$, and $\emptyset$ otherwise; the {\em union\/} reads $[x,y]\cup[u,v]=[\min\{x,u\},\max\{y,v\}]$. Note that the definition of the union is also valid for $[x,y]\cap[u,v]=\emptyset$, hence incorporates the closure of two disjoint intervals as well. Both intersection and union extend to a scalar operand in the obvious way, i.e., $[x,y] \cup u = [x,y] \cup [u,u]$. Finally, we will need the {\em non-commutative union\/} (abbreviated {\em nc-union\/}) defined by $[x,y]\nccup[u,v] = [x,v]$ if $x\leq v$ and $\emptyset$ otherwise. Accuracy intervals, as introduced at the beginning of this section, are intervals extended by a distinguished {\em reference point\/} $r$, which partitions the interval into a {\em negative accuracy\/} $\alpha^-$ and a {\em positive accuracy\/} $\alpha^+$ according to \begin{equation} \B{A}=[r\pm\B{\alpha}]=[r-\alpha^-,r+\alpha^+]\label{eq:intv}. \end{equation} Herein, $\mbox{ref}(\B{A})=r$ denotes $\B{A}$'s reference point\label{pag:refpt}, $\B{\alpha}=[-\alpha^-,\alpha^+]$ its {\em interval of accuracies\/}\label{pag:accuriv}, and $\alpha=|\B{\alpha}|=\alpha^++\alpha^-$ its length. Note that we use bold letters like $\B{A}$\label{pag:intervals} for both ordinary intervals and accuracy intervals, since its actual type is usually clear from the context. Similarly, calligraphic bold letters like $\B{\cal A}$ are used to denote a {\em set\/} of intervals or accuracy intervals. For accuracy intervals $\B{I}=[r\pm\B{\alpha}]$ and $\B{J}=[s\pm\B{\beta}]$, we have $\mbox{left}(\B{I})=r-\alpha^-$, $\mbox{right}(\B{I})=r+\alpha^+$, $|\B{I}| = \alpha^+ + \alpha^- = \alpha$, $\mbox{center}(\B{I}) = r + (\alpha^+-\alpha^-)/2$, $\B{I}+\B{J} = [r+s\pm\B{\gamma}]$ where $\B{\gamma}=\B{\alpha}+\B{\beta}=[-(\alpha^-+\beta^-),\alpha^++\beta^+]$, $\B{I}+a=[r+a\pm\B{\alpha}]$ for an arbitrary scalar $a$, and $s\B{I}=[sr\pm \B{\mu}]$ with $\B{\mu}=s\B{\alpha}=[-s\alpha^-,s\alpha^+]$ for any scalar $s\geq0$. Finally, there is also a notation to express intervals obtained from~(\ref{eq:intv}) by {\em swapping\/} positive and negative accuracy, namely \begin{equation} \overline{\B{I}}=\overline{[r\pm\B{\alpha}]}=[r\mp\B{\alpha}]=[r-\alpha^+,r+\alpha^-] =[r\pm\overline{\B{\alpha}}]\label{eq:swapintv} \end{equation} where $\overline{\B{\alpha}}=[-\alpha^+,\alpha^-]=-\B{\alpha}$. \begin{defin}[Interval Relations~{\cite[Def.~1]{SS97:1}}]\label{def:ivrels} Accuracy intervals \\ are categorized as follows: \begin{itemize} \item[(1)] Two accuracy intervals $\B{I}=\B{I}(t_1)$ representing~$t_1$ and $\B{J}=\B{J}(t_2)$ representing~$t_2$ are compatible if and only if $t_1=t_2$. \item[(2)] Two compatible accuracy intervals $\B{I}$ and $\B{J}$ are consistent if and only if $\B{I}\cap \B{J} \ne \emptyset$. \item[(3)] An accuracy interval $\B{I}=\B{I}(t)$ representing real-time $t$ is accurate if and only if $t\in \B{I}$. \end{itemize} \end{defin} Note that compatibility of two accuracy intervals means that they are comparable, that is, represent the same real-time. Bear in mind, however, that the ``represents'' relation implies neither consistency nor accurateness in case of faulty accuracy intervals. The following definition of $\B{\pi}$-precision is a key for our interval-based precision analysis. The underlying idea is to capture precision $\pi$ of two clocks $C_p(t)$ and $C_q(t)$, that is, $|C_p(t)-C_q(t)|\leq \pi$, by means of consistency of suitably constructed precision intervals. \begin{defin}[Precision Intervals {\bf \cite[Def.~2]{SS97:1}}] \label{def:ivprec} Given some fixed $\B{\pi}$ $=[-\pi^-,\pi^+]$ with $\pi^-,\pi^+\geq0$ and $\pi=|\B{\pi}|=\pi^-+\pi^+$, and a set of $n\ge2$ compatible accuracy intervals $\B{\cal I}=\{\B{I}_1, \dots, \B{I}_n\}$ with $\B{I}_j=[r_j\pm\B{\alpha}_j]$, the {\em $\B{\pi}$-precision interval\/} $\ppI{\B{I}}_j$ associated with $\B{I}_j$ is defined as $\ppI{\B{I}}_j=[r_j\pm\B{\pi}]$. The set $\B{\cal I}$ is called $\B{\pi}$-precise if and only if $\bigcap_{j=1}^n\ppI{\B{I}}_j \neq \emptyset$. \end{defin} Figure~\ref{fig:intvs} shows two accuracy intervals along with their associated precision intervals. Note carefully that associated $\B{\pi}$-precision intervals are not maintained ``online,'' as are accuracy intervals, but rather computed from the reference points by adding the ``static'' values of $-\pi^-$, $\pi^+$ provided by the analysis. That is, it is sufficient for the clock synchronization algorithm to dynamically maintain the interval of accuracies and its reference point only. Item (2) of the following Lemma~\ref{lem:corpiprec} reveals that $\B{\pi}$-precision implies (traditional) precision $\pi=|\B{\pi}|$. Its assertions are quite trivial, as can be seen from the associated precision intervals shown in Figure~\ref{fig:intvs}. \begin{lem}[$\B{\pi}$-Precision vs. Precision]\label{lem:corpiprec} Given a $\B{\pi}$-precise set $\B{\cal I}$ $=\{\B{I}_1$, $\dots$, $\B{I}_n\}$ of $n\geq2$ compatible accuracy intervals $\B{I}_j=[r_j\pm\B{\alpha}_j]$, then \begin{itemize} \item[(1)] $|\ppI{\B{I}_i}\cup\ppI{\B{I}_j}|\leq 2\pi$ for any $1\leq i,j \leq n$, \item[(2)] $|r_i - r_j|\leq \pi$ for any $1\leq i,j \leq n$. \end{itemize} \end{lem} \noindent {\bf Proof\,} See \cite{SS97:1}, Lemma~3. $\Box$ \medskip Although the definition of $\B{\pi}$-precision is a key for our precision analysis, there are only a few occasions where $\B{\pi}$-precise intervals are encountered explicitly. In most cases, the slightly stronger predicate of \emi{$\B{\pi}$-accurateness} (implying $\B{\pi}$-precision) is used, which is based on a suitable notion of an {\em internal global time\/} $\tau=\tau(t)$. More specifically, it was shown in \cite{SS97:1} that it makes sense to stipulate an ``artificial'' internal global time $\tau^k=\tau^k(t)=\tau_0^k+(t-t_0^k)$ for each round~$k$ that progresses as real-time does. Herein, $t_0^k$ denotes the real-time when round~$k$ commences, and $\tau_0^k=\tau^k(t_0^k)$ represents $\tau^k$'s initial offset with respect to real-time. Like real-time, internal global time is not directly accessible, and usually $\tau^k(t)\neq t$. However, internal global time of any fixed round is equivalent to real-time for specifying durations, and we can unambiguously write $\ppI{\B{I}}=\ppI{\B{I}}(t)=\ppI{\B{I}}(\tau^k)$ for $\tau^k=\tau^k(t)$, meaning that $\ppI{\B{I}}$ represents $\tau^k(t)$ if and only if $\B{I}$ represents $t$. The concept of internal global time makes it possible to define an analogue to accurateness as follows. \begin{defin}[$\B{\pi}$-correctness {\bf \cite[Def.~3]{SS97:1}}]\label{def:picorrness} For $\B{\pi}=[-\pi^-,\pi^+]$ with $\pi^-,\pi^+\geq0$, \begin{itemize} \item[(1)] an accuracy interval $\B{I}=\B{I}(t)$ is $\B{\pi}$-accurate (with respect to internal global time $\tau^k=\tau^k(t)$ of round~$k$) if and only if the $\B{\pi}$-precision interval $\ppI{\B{I}}=\ppI{\B{I}}(\tau^k)$ associated with $\B{I}$ satisfies $\tau^k\in\ppI{\B{I}}$, \item[(2)] an accuracy interval $\B{I}$ is $\B{\pi}$-correct (with respect to real-time and internal global time of round $k$) if and only if $\B{I}$ is both $\B{\pi}$-accurate and accurate, \item[(3)] a set $\B{\cal I}$ of compatible accuracy intervals is $\B{\pi}$-correct if all members are $\B{\pi}$-correct. \end{itemize} \end{defin} The following Figure~\ref{fig:intvs} shows an example of two $\B{\pi}$-correct intervals. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{figure}[htb] \begin{center} \unitlength=0.90mm \special{em:linewidth 0.4pt} \linethickness{0.4pt} \begin{picture}(111.00,43.00) \put(49.00,27.00){\circle*{2.00}} \put(43.00,25.67){\line(0,1){3.00}} \put(43.00,26.62){\rule{18.00\unitlength}{1.00\unitlength}} \put(65.00,7.00){\circle*{2.00}} \put(59.00,5.67){\line(0,1){3.00}} \put(59.00,6.62){\rule{18.00\unitlength}{1.00\unitlength}} \put(61.00,27.00){\line(1,0){38.00}} \put(61.00,25.67){\line(0,1){3.00}} \put(77.00,5.67){\line(0,1){3.00}} \put(99.00,25.67){\line(0,1){3.00}} \put(111.00,5.67){\line(0,1){3.00}} \put(77.00,7.00){\line(1,0){34.00}} \put(93.02,20.54){\line(0,-1){1.00}} \put(93.02,17.54){\line(0,1){1.00}} \put(93.02,16.54){\line(0,-1){1.00}} \put(93.02,14.54){\line(0,-1){1.00}} \put(93.02,12.54){\line(0,-1){1.00}} \put(93.02,10.54){\line(0,-1){1.00}} \put(93.02,8.54){\line(0,-1){1.00}} \put(93.02,6.54){\line(0,-1){1.00}} \put(93.02,4.54){\line(0,-1){1.00}} \put(93.02,2.54){\line(0,-1){1.00}} \put(93.02,37.54){\line(0,1){1.00}} \put(93.02,36.54){\line(0,-1){1.00}} \put(93.02,34.54){\line(0,-1){1.00}} \put(93.02,32.54){\line(0,-1){1.00}} \put(93.02,30.54){\line(0,-1){1.00}} \put(93.02,28.54){\line(0,-1){1.00}} \put(93.02,26.54){\line(0,-1){1.00}} \put(93.02,24.54){\line(0,-1){1.00}} \put(93.02,22.54){\line(0,-1){1.00}} \put(92.67,43.00){\makebox(0,0)[cb]{{\footnotesize $t$}}} \put(59.33,21.00){\line(0,-1){1.00}} \put(59.33,18.00){\line(0,1){1.00}} \put(59.33,17.00){\line(0,-1){1.00}} \put(59.33,15.00){\line(0,-1){1.00}} \put(59.33,13.00){\line(0,-1){1.00}} \put(59.33,11.00){\line(0,-1){1.00}} \put(59.33,9.00){\line(0,-1){1.00}} \put(59.33,7.00){\line(0,-1){1.00}} \put(59.33,5.00){\line(0,-1){1.00}} \put(59.33,3.00){\line(0,-1){1.00}} \put(59.33,38.00){\line(0,1){1.00}} \put(59.33,37.00){\line(0,-1){1.00}} \put(59.33,35.00){\line(0,-1){1.00}} \put(59.33,33.00){\line(0,-1){1.00}} \put(59.33,31.00){\line(0,-1){1.00}} \put(59.33,29.00){\line(0,-1){1.00}} \put(59.33,27.00){\line(0,-1){1.00}} \put(59.33,25.00){\line(0,-1){1.00}} \put(59.33,23.00){\line(0,-1){1.00}} \put(59.33,43.00){\makebox(0,0)[cb]{{\footnotesize $\tau$}}} \put(49.00,28.00){\line(0,1){5.00}} \put(73.00,31.00){\vector(-1,0){24.00}} \put(73.00,31.00){\vector(1,0){26.00}} \put(65.00,8.00){\line(0,1){5.00}} \put(89.00,11.00){\vector(-1,0){24.00}} \put(89.00,11.00){\vector(1,0){22.00}} \put(75.00,33.00){\makebox(0,0)[cb]{{\tiny $\alpha_{1}^+$}}} \put(88.00,13.00){\makebox(0,0)[cb]{{\tiny $\alpha_{2}^+$}}} \put(71.00,1.00){\makebox(0,0)[ct]{{\tiny $\pi^+$}}} \put(4.00,27.00){\makebox(0,0)[rc]{{\footnotesize $\B{I}_{1}$}}} \put(16.00,7.00){\makebox(0,0)[rc]{{\footnotesize $\B{I}_2$}}} \put(43.00,27.00){\line(-1,0){31.00}} \put(59.00,7.00){\line(-1,0){39.00}} \put(12.00,25.67){\line(0,1){3.00}} \put(20.00,5.67){\line(0,1){3.00}} \put(65.00,1.00){\line(0,1){5.00}} \put(49.00,21.00){\line(0,1){5.00}} \put(30.00,31.00){\vector(1,0){19.00}} \put(30.00,31.00){\vector(-1,0){18.00}} \put(54.00,23.00){\vector(1,0){7.00}} \put(54.00,23.00){\vector(-1,0){5.00}} \put(46.00,23.00){\vector(1,0){3.00}} \put(46.00,23.00){\vector(-1,0){3.00}} \put(45.00,11.00){\vector(1,0){20.00}} \put(45.00,11.00){\vector(-1,0){25.00}} \put(70.00,3.00){\vector(1,0){7.00}} \put(70.00,3.00){\vector(-1,0){5.00}} \put(62.00,3.00){\vector(1,0){3.00}} \put(62.00,3.00){\vector(-1,0){3.00}} \put(30.00,33.00){\makebox(0,0)[cb]{{\tiny $\alpha_{1}^-$}}} \put(42.00,13.00){\makebox(0,0)[cb]{{\tiny $\alpha_{2}^-$}}} \put(62.00,1.00){\makebox(0,0)[ct]{{\tiny $\pi^-$}}} \put(55.00,21.00){\makebox(0,0)[ct]{{\tiny $\pi^+$}}} \put(46.00,21.00){\makebox(0,0)[ct]{{\tiny $\pi^-$}}} \put(49.67,34.00){\makebox(0,0)[cb]{{\footnotesize $r_1$}}} \put(65.67,14.00){\makebox(0,0)[cb]{{\footnotesize $r_2$}}} \put(40.00,22.00){\makebox(0,0)[rc]{{\footnotesize $\ppI{\B{I}}_{1}$}}} \put(56.00,2.00){\makebox(0,0)[rc]{{\footnotesize $\ppI{\B{I}}_2$}}} \end{picture} \end{center} \caption{\em Example of two $\protect\B{\pi}$-accurate intervals. Both accuracy intervals and (bold) $\protect\B{\pi}$-precision intervals are accurate with respect to $t$ and $\tau$, respectively.} \label{fig:intvs} \end{figure} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Now we are ready to explain how the interval-based clock synchronization algorithm outlined at the beginning of this section maintains precision. The most important observation is that all steps of the algorithm, except the application of the convergence function, maintain precision automatically by maintaining accuracy. To understand why, assume that all members of the set $\B{\cal C}(t)$ of non-faulty interval clocks are $\B{\pi}_0$-correct at some real-time $t^0$ in round~$k$, that is, their associated $\B{\pi}_0$-precision intervals contain $\tau^k(t^0)$. In order to capture real-time $t$ by $\B{C}_p(t)$, it must be deteriorated (enlarged) appropriately to compensate for the drift of the local clock. However, if this is done properly to ensure $t'\in\B{C}_p(t')$ for $t'>t^0$, then the associated $\B{\pi}^H$-precision interval $\ppI{\B{C}}_p(t')$ captures internal global time $\tau^k(t')>\tau^k(t^0)$ as well, provided that $\B{\pi}^H$ is the result of enlarging $\B{\pi}_0$ by the maximum amount any $\B{C}_q$ has been enlarged. This is a simple consequence of the fact that internal global time progresses as real-time does. Note anyway that enlargement of precision intervals is just a matter of analysis ---the algorithm need not deal explicitly with precision intervals at all. Whereas enlarging $\B{\pi}_0$ to $\B{\pi}^H$ guarantees $\B{\pi}^H$-correctness of all non-faulty $\B{C}_p(t')$, this cannot ensure \underbar{bounded} precision for $t\to\infty$. Periodic resynchronizations are required for this purpose, giving rise to our round-based algorithm. More specifically, at the end of the $k$th round, the nodes' current $\B{\pi}^H$-correct local interval clocks are set to newly computed accuracy intervals that are $\B{\pi}_0$-precise for some $\B{\pi}_0\subset \B{\pi}^H$ (= precision enhancement provided by the convergence function). Note that we cannot safely assume $\B{\pi}_0$-correctness here, since it will usually happen that round~$k$'s internal global time $\tau^k$ does not lie in the intersection of the new $\B{\pi}_0$-precision intervals. However, if a new initial offset $\tau_0^{k+1}$ for internal global time $\tau^{k+1}(t)$ is defined for round $k+1$, $\B{\pi}_0$-correctness with respect to $\tau^{k+1}$ can of course be guaranteed. Consequently, resynchronization starts the next round~$k+1$, during which initial precision $\B{\pi}_0$ again deteriorates to $\B{\pi}^H$. Note carefully that only the interval clocks' associated $\B{\pi}^H$-precision intervals experience (precision) enhancement during resynchronization. The local interval clocks $\B{C}_p$ itself must continuously track real-time $t$, so that the accuracies could be monotonically increasing; the accuracy in round $k$ can in fact be viewed as an accumulation of the $\B{\pi}^H$-precision intervals during round~$0,\dots,k$. This eventually explains why $t$ and $\tau$ will usually be apart, as mentioned earlier. %The detailed analysis in \cite{SS97:1} reflects the principal structure outlined %above. In fact, a sequence of lemmas is provided that characterize %how accuracy/precision intervals evolve in a single round: %\cite[Lem.~11]{SS97:1} describes the set of %intervals fed into the convergence function, and \cite[Lem.~12]{SS97:1} %shows that the precision provided at the beginning of round~$k$ is %reestablished at the beginning of round~$k+1$. On top of that, a %simple induction proof is conducted to derive the major %result \cite[Thm.~1]{SS97:1}. % %\medskip Generally speaking, the major advantage of the interval-based precision analysis developed in \cite{SS97:1}\footnote{Note that we provide a few extensions of the generic analysis of \cite{SS97:1} in Appendix~C, which are used instead of the original version where required.} is conceptual beauty and considerable flexibility with respect to incorporating non-standard features like clock granularity, broadcast latencies, etc. This is primarily a consequence of our notion of internal global time and $\B{\pi}$-accurateness, which allows us to reason about precision by considering each local interval clock separately, that is, without explicitly relating it to the other clocks in the system. Even more, there is no need to consider the ``absolute position'' of intervals, that is, clock values, at all. In fact, any information required on some $\B{I}(t)=[T\pm\B{\alpha}]$ is provided by its interval of accuracies $\B{\alpha}$ and the associated $\B{\pi}$-precision interval: Since all (non-faulty) accuracy intervals must contain real-time $t$ and internal global time $\tau$ by construction, the latter times serve as a ``common reference'' for relating different intervals. Of course, the particular reference point $\mbox{ref}(\B{I})$ may lie anywhere in $[t-\alpha^{+}, t+\alpha^{-}]$ and $[\tau-\pi^{+}, \tau+\pi^{-}]$, according to the actually experienced clock drift, transmission delay, and initial accuracy, but there is no need for dealing with it explicitly. \subsection{Fault Model} \label{Fault Model} In \cite{SS97:1}, we argued that it does not make sense to stipulate a particular fault model for the generic algorithm. After all, it is primarily the convergence function that is concerned about faults. Now that we have to plug in a particular convergence function, we have to address this issue in full detail. We will introduce a {\em perception-based hybrid fault model\/} for this purpose, which is a refinement of the ``abstract fault model'' suggested in \cite{SS97:1}. Conventional ``global'' fault models, like the one that at most $f$ nodes may behave byzantine, rest upon the total number of faults in the entire system. An abstract (perception-based) fault model solely relies upon the number of faults in (any) two non-faulty nodes' {\em perceptions\/} of the system, that is, the intervals gathered by a node in an FME. Hence, the omniscient system-wide perception of faults is replaced by the local perceptions of (any) two non-faulty participants in the system. This way, both node \underbar{and} link faults can be accurately modeled. As in most other work dealing with byzantine faults in distributed systems, we assume that faulty nodes and network devices can take arbitrary steps and transmit (and ``receive'') any number of arbitrary messages. We only exclude (serious) ``global'' disturbance of system operation, namely, impersonating other nodes and flooding/jamming ``foreign'' links respectively the broadcast network. A faulty sender node or link can hence affect a receiving node only by means of the intervals $\B{\cal I}_q=\{\B{I}_q^s : 1\leq s \leq n\}$ received and preprocessed at any non-faulty node~$q$ during an FME, recall Subsection~\ref{Generic Algorithm}. Since the precision requirement~(P) only demands that any two non-faulty clocks must satisfy $|C_p(t)-C_q(t)|\leq \pi$, {\em without regard to the other nodes in the system\/}, the pair of perceptions $\B{\cal I}_p$, $\B{\cal I}_q$ can be considered {\em in isolation\/}; faulty receiving nodes (which may behave arbitrarily anyway) can entirely be ignored. Therefore, global fault assumptions ---like the one that \underbar{all} receivers perceive a certain fault consistently--- are not required. Rather than on the system-wide number of faults during a round (say, $f\leq\lfloor (n-1)/3 \rfloor$), we can hence rely upon the number of faulty pairs of intervals $\{\B{I}_p^s\in\B{\cal I}_p, \B{I}_q^s\in\B{\cal I}_q\}$ at two non-faulty nodes~$p$, $q\neq p$. It is important to note, though, that the issue of faulty vs.\ correct intervals is more subtle than it meets the eye. First of all, we cannot usually assume $\B{I}_p^s=\B{I}_q^s$ even if there is no fault at all: Since we are dealing with time-dependent intervals, transmission delays, clock granularities and drift rates usually cause $\B{I}_p^s$ and $\B{I}_q^s$ to differ slightly. This fact requires special treatment in our analysis, see Lemma~\ref{lem:precM}. In addition, the above effects could lead to a perturbed and even inconsistent perception of (sender) faults, since a faulty interval from~$s$ might nevertheless produce a correct $\B{I}_p^s$ or $\B{I}_q^s$. >From the above description, it is immediately apparent that a global fault assumption like ``at most $f$ nodes may be byzantine'' also implies ``at most $f$ (pairs of) intervals in $\B{\cal I}_p$, $\B{\cal I}_q$ may be byzantine,'' for any non-faulty $p$, $q$. Our perception-based fault model thus covers the corresponding global one as well, which also reveals that the traditional impossibility results (\cite{DHS86}) remain valid. The opposite covering, however, cannot be assumed in general since the faulty (pairs of) intervals in two different pairs of perceptions $\B{\cal I}_p$, $\B{\cal I}_q$ and $\B{\cal I}_v$, $\B{\cal I}_w$ need \underbar{not} originate in the same set of sending nodes. For that reason, our perception-based fault model also allows to accurately model {\em link faults\/}, ranging from packet losses due to unrecognized packet headers and receiver overruns up to inconsistent timing and value faults. Although such faults are quite likely in practice, they are difficult to capture by means of a conventional global fault model: ``Artificially'' mapping link faults to node faults and stipulating at most $f$ faults {\em within the whole system\/} is both unnecessarily restrictive and unrealistic. A natural model of, for example, receive omissions is to grant each receiving node a certain maximum number of those, independently of the situation at other nodes. Still, allowing even a single receive omission at each node could easily eat up all sending nodes, such that all $n$ nodes must be considered faulty in a conventional fault model. By contrast, in our perception-based model, at most two faulty (pairs of) intervals can show up in this case. We start our formal definitions with possible faults of a single interval, which is primarily required for accuracy analysis. \begin{defin}[Single Faults]\label{def:classfaults} An interval $\B{I}$ representing $t$ can suffer from the following faults: \begin{itemize} \item {\em Omission\/}: Missing interval, expressed by $\B{I}=\emptyset$. \item {\em Non-accurate interval\/}: $t\not\in \B{I}$. \item {\em Unbounded accuracy\/}: $t\in\B{I}$ but $|\B{I}|$ too large according to some condition (that need not be known explicitly). \end{itemize} \end{defin} \begin{rmm} \pitem Non-accurate intervals can be caused by {\em timing faults\/} due to a faulty sending node/clock or excessive transmission delays, or by {\em accuracy faults\/} due to a faulty sending node/clock or a damaged message. \pitem Masking or detecting, and thus ruling them out completely, unbounded accuracy faults is impossible in most circumstances. Indeed, although it is sometimes possible to determine the border between faulty and non-faulty accuracy values (see Theorem~\ref{thm:accOA}), it is nevertheless true that even limiting $\alpha^-$, $\alpha^+$ accordingly cannot prevent faulty nodes from considerably spoiling the ``average'' behavior. \pitem Whereas it is usually impossible to decide locally whether an interval $\B{I}$ is accurate or not, it is of course possible to detect omission faults. Hence, given a set $\B{\cal I}$ of $n\geq1$ compatible intervals with $\o'\geq0$ of them exhibiting omission faults, it is trivial to discard the $\o'$ omissive ones from $\B{\cal I}$ and to proceed with the reduced set $\B{\cal J}$ containing the $n'=n-\o'$ non-empty intervals only. \end{rmm} For our precision analysis, the single-interval faults of Definition~\ref{def:classfaults} must be complemented by faults of {\em pairs of intervals\/} $\B{I}_p^s$ and $\B{I}_q^s$ obtained at nodes $p$ and $q$, respectively, in the broadcast from a single node $s$. Different classes of faults (crash/symmetric/asymmetric) will be introduced to facilitate a {\em hybrid fault model\/} (refer to \cite{AK96}, \cite{WS00}). It will allow us to exploit the fact that masking $f$ symmetric faults with $\OA$ requires only $n\geq 2f+1$, whereas $n\geq 3f+1$ is needed if all faults are asymmetric ones (\cite{DHS86}). Since a large number of asymmetric faults is very unlikely in practice, see \cite{Sch95}, this effectively leads to a smaller $n$ for tolerating a given number of faults, see (\ref{equ:n}). The following Definition~\ref{def:pairfaultiv} exhaustively specifies all possible faults of pairs of intervals. \begin{defin}[Pairwise Faults]\label{def:pairfaultiv} A pair of compatible accuracy intervals $\{\B{I}_p^s$, $\B{I}_q^s\}$ originating in a single sending node~$s$ and representing real-time~$t$ suffers from \begin{itemize} \item a {\em crash fault\/} if and only if $\B{I}_p^s=\B{I}_q^s=\emptyset$, \item a {\em symmetric fault\/} if and only if either \begin{itemize} \item[(1)] both $\B{I}_p^s$ and $\B{I}_q^s$ are not accurate in the sense of $t < \mbox{left}(\B{I}_p^s)$ and $t < \mbox{left}(\B{I}_q^s)$, or else $t > \mbox{right}(\B{I}_p^s)$ and $t > \mbox{right}(\B{I}_q^s)$, \item[(2)] without loss of generality, $\B{I}_p^s=\emptyset$ and $\B{I}_q^s\neq\emptyset$ does not suffer from an unbounded accuracy fault, \end{itemize} \item an {\em asymmetric fault\/} if and only if either \begin{itemize} \item[(1)] both $\B{I}_p^s$ and $\B{I}_q^s$ are not accurate in the sense of $t > \mbox{right}(\B{I}_p^s)$ and $t < \mbox{left}(\B{I}_q^s)$ or else $t > \mbox{right}(\B{I}_q^s)$ and $t < \mbox{left}(\B{I}_p^s)$ (true byzantine fault), \item[(2)] without loss of generality, $\B{I}_p^s\neq\emptyset$ is faulty and $\B{I}_q^s$ is arbitrary (and none of the other faults applies). \end{itemize} \end{itemize} \end{defin} \begin{rmm} \pitem The ``classical'' asymmetric fault (\cite{WS00}) is one that is perceived differently at $p$ and~$q$. Its distinguishing property is that node~$p$ arrives at the conclusion that the sender's clock is, say, too fast, whereas $q$ thinks that it is too slow (or correct). This could occur, for example, when the transmission delay to $p$ respectively $q$ is excessively low respectively high or if the sending node exhibits byzantine behavior. In our context, an unbounded accuracy fault must also be counted as asymmetric, see Remark~2 on Lemma~\ref{lem:accM}. \pitem The ``classical'' symmetric fault (\cite{WS00}) is caused by disseminating information that is perceived identically at $p$ and~$q$. This type of fault is usually produced by a sender clock that runs too slow or too fast. In our context, ``pure'' receive omissions must also be counted as a symmetric fault. \pitem A crash fault causes an omission both at node~$p$ and~$q$. Note carefully, though, that it is impossible for either node to decide locally (without further information) whether its omission is due to a crash fault or a more severe receive omission. \pitem We do not consider \underbar{systemwide} consistently perceived {\em benign faults} (\cite{WS00}) explicitly, since they are simple to accommodate in our context: To tolerate $f_b$ benign faults, $n\geq f_b+1$ is sufficient. \pitem Note that Definition~\ref{def:pairfaultiv} does not cover the case where a more severe fault comes out as a less severe one. For example, it is reasonable to assume that an asymmetric fault could just be a symmetric or even a crash fault only. In this paper, we will typically use phrases like ``asymmetric (or weaker) fault'' to indicate such extensions. \end{rmm} We should finally mention that our definition of symmetric and asymmetric faults extends and, in some cases, apparently contradicts the ``classical'' meaning of those terms. Still, we think that their usage is legitimate due to the fact that our extension preserves the essentials of their meaning: The meaning of symmetric / asymmetric fault is basically received identically / not identically at different nodes. In our context, however, we had to relax the meaning of ``received identically'' since we cannot assume identical information at different nodes even in the faultless case, as explained earlier. We also had to accept the fact that the interval-based paradigm introduces unbounded accuracy faults, which are not known in conventional settings but can create an asymmetric perception. Whereas the above definitions are sufficient for ``pure'' accuracy intervals and precision intervals, they cannot be applied literally to the ``combination'' of both required for $\OA$'s final analysis in Section~\ref{Orthogonal Accuracy Convergence Function}, recall Figure~\ref{fig:intvs}. For the final fault model, we have to take into account that faults may occur in precision and accuracy intervals quite independently of each other. More specifically, we must distinguish faults affecting an accuracy interval and its associated precision interval either consistently ($t/\tau$-symmetrically) or inconsistently ($t/\tau$-asymmetrically): Let a single accuracy interval $\B{I}$ that is faulty with respect to real-time $t$ and/or internal global time $\tau$ be called {\em $t/\tau$-symmetrically\/} faulty if either $$ t < \mbox{left}(\B{I})\mbox{ and }\tau < \mbox{left}(\ppI{\B{I}}), \qquad\mbox{or}\qquad t > \mbox{right}(\B{I})\mbox{ and }\tau > \mbox{right}(\ppI{\B{I}}); $$ otherwise, it is considered {\em $t/\tau$-asymmetrically\/} faulty. A set $\B{\cal F}$ of faulty accuracy intervals is {\em identically\/} $t/\tau$-symmetrically faulty if $t$ (and hence also $\tau$) is either to the left or to the right for all members of $\B{\cal F}$. \begin{asum}[Perception-based Hybrid Fault Model ${\cal F}$]\label{asum:faultmodel} Let a pair of accuracy intervals $\{\B{I}_p^s$, $\B{I}_q^s\}$ originating in a single sending node~$s$ and representing real-time~$t$, with the associated precision intervals $\{\ppI{\B{I}}_p^s$, $\ppI{\B{I}}_q^s\}$ representing $\tau$, be called \begin{itemize} \item[(1)] {\em simple faulty\/} if it suffers from a crash fault or a symmetric fault with respect to $t$ and/or $\tau$ and both faulty intervals (only present if no omission took place) are identically $t/\tau$-symmetrically faulty, \item[(2)] {\em arbitrary faulty\/} if it suffers either from an asymmetric fault with respect to $t$ and/or $\tau$, or a symmetric fault involving at least one $t/\tau$-asymmetrically faulty interval. Alternatively, an arbitrary fault could also be just a simple one. \end{itemize} For all pairs of non-faulty nodes~$p$ and~$q$, consider the ordered sets\footnote{We use the term {\em ordered sets\/} for $\B{\cal I}_p$ and $\B{\cal I}_q$ to stress the fact that the intervals in both input sets can be uniquely grouped as $n$ pairs $\{\B{I}_p^s\in\B{\cal I}_p, \B{I}_q^s\in\B{\cal I}_q\}$ originating in the same sending node~$s$, $1\leq s\leq n$.} of intervals $\B{\cal I}_p=\{\B{I}_p^1,\dots,\B{I}_p^n\}$ and $\B{\cal I}_q=\{\B{I}_q^1,\dots,\B{I}_q^n\}$ obtained after reception and preprocessing of the accuracy intervals disseminated in an FME, according to the generic interval-based clock synchronization algorithm of Definition~\ref{def:OAalgorithm}. We assume that at most $\e$ respectively $\d$ of the $n$ pairs of intervals $\{\B{I}_p^s$, $\B{I}_q^s\}$, $1\leq s \leq n$, suffer from arbitrary respectively simple faults, where $\e$ and $\d$ are such that \begin{equation} n\geq 3\e+2\d+1.\label{equ:n} \end{equation} \end{asum} \section{Marzullo's Function} \label{Marzullo Function} This section is devoted to an in-depth investigation of a fault-tolerant intersection function $\M$, which plays a central role in our orthogonal accuracy convergence function. $\M$ was introduced in Marzullo's thesis \cite{Mar84} and termed {\em Marzullo function\/} in \cite{Lam87}. Although its relevance was recognized in several papers (for example, see \cite{Lam87}, \cite{Mar90}, \cite{OSF92}, \cite{Sch95}, \cite{Mil95}), it has been studied thoroughly in the context of replicated sensors only, see \cite{Mar90} and \cite{BI96}. For clock synchronization purposes, a number of additional properties are required, which will be established subsequently. \begin{defin}[Marzullo Function]\label{def:M} Given a set $\B{\cal I}=\{\B{I}_1,\ldots,\B{I}_n\}$ of $n\geq1$ (non-empty) compatible intervals with at least $n-f\geq1$ of the intervals being accurate, ${\M}^{n-f}_n(\B{\cal I})$ is defined as the largest interval whose edges lie in the intersection of at least $n-f$ different $\B{I}_j$'s. \end{defin} Therefore, to compute the left and right edge of $\M_n^{n-f}(\B{\cal I})$, one has to ``sweep'' over the set of intervals from left to right and right to left, respectively, and stop when $n-f$ intervals intersect for the first time. $\M$ is translation invariant, that is, $\M_n^{n-f}(\{\B{I}_1+\Delta,\dots,\B{I}_n+\Delta\})= \M_n^{n-f}(\{\B{I}_1,\dots,\B{I}_n\})+\Delta$ for any real $\Delta$, and can be computed in ${\cal O}(n\log n)$ time by sorting the intervals' edges, see~\cite{Mar90} for details. Figure~\ref{fig:marzullo} shows an example for $n=4$ and $f=1$. Note that the unknown $t$ cannot lie in the region between $\mbox{right}(\B{I}_3)$ and $\mbox{left}(\B{I}_4)$ in this example. However, since there is no way to decide whether $t$ lies in the area left or right of this region, both areas must be covered by ${\M}^{3}_4$. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{figure}[htb] \begin{center} \unitlength=0.60mm \special{em:linewidth 0.4pt} \linethickness{0.4pt} \begin{picture}(136.00,73.00) \put(25.00,39.00){\rule{70.00\unitlength}{1.00\unitlength}} \put(25.00,38.00){\line(0,1){3.00}} \put(95.00,38.00){\line(0,1){3.00}} \put(34.00,49.00){\rule{70.00\unitlength}{1.00\unitlength}} \put(34.00,48.00){\line(0,1){3.00}} \put(104.00,48.00){\line(0,1){3.00}} \put(15.00,59.00){\rule{58.00\unitlength}{1.00\unitlength}} \put(92.00,69.00){\rule{41.00\unitlength}{1.00\unitlength}} \put(15.00,58.00){\line(0,1){3.00}} \put(73.00,58.00){\line(0,1){3.00}} \put(92.00,68.00){\line(0,1){3.00}} \put(133.00,68.00){\line(0,1){3.00}} \put(60.00,5.00){\makebox(0,0)[ct]{{\footnotesize $t$ (unknown)}}} \put(34.00,61.00){\line(0,1){1.00}} \put(34.00,58.00){\line(0,-1){1.00}} \put(34.00,56.00){\line(0,-1){1.00}} \put(34.00,54.00){\line(0,-1){1.00}} \put(34.00,52.00){\line(0,-1){1.00}} \put(34.00,48.00){\line(0,-1){1.00}} \put(34.00,46.00){\line(0,-1){1.00}} \put(34.00,44.00){\line(0,-1){1.00}} \put(34.00,42.00){\line(0,-1){1.00}} \put(34.00,40.00){\line(0,-1){1.00}} \put(34.00,38.00){\line(0,-1){1.00}} \put(34.00,35.00){\line(0,1){1.00}} \put(34.00,34.00){\line(0,-1){1.00}} \put(34.00,32.00){\line(0,-1){1.00}} \put(34.00,30.00){\line(0,-1){1.00}} \put(34.00,28.00){\line(0,-1){1.00}} \put(34.00,26.00){\line(0,-1){1.00}} \put(34.00,24.00){\line(0,-1){1.00}} \put(34.00,22.00){\line(0,-1){1.00}} \put(34.00,20.00){\line(0,-1){1.00}} \put(34.00,18.00){\line(0,-1){1.00}} \put(34.00,16.00){\line(0,-1){1.00}} \put(95.00,58.00){\line(0,-1){1.00}} \put(95.00,56.00){\line(0,-1){1.00}} \put(95.00,54.00){\line(0,-1){1.00}} \put(95.00,52.00){\line(0,-1){1.00}} \put(95.00,48.00){\line(0,-1){1.00}} \put(95.00,46.00){\line(0,-1){1.00}} \put(95.00,44.00){\line(0,-1){1.00}} \put(95.00,42.00){\line(0,-1){1.00}} \put(95.00,40.00){\line(0,-1){1.00}} \put(95.00,38.00){\line(0,-1){1.00}} \put(95.00,35.00){\line(0,1){1.00}} \put(95.00,34.00){\line(0,-1){1.00}} \put(95.00,32.00){\line(0,-1){1.00}} \put(95.00,30.00){\line(0,-1){1.00}} \put(95.00,28.00){\line(0,-1){1.00}} \put(95.00,26.00){\line(0,-1){1.00}} \put(95.00,24.00){\line(0,-1){1.00}} \put(95.00,22.00){\line(0,-1){1.00}} \put(95.00,20.00){\line(0,-1){1.00}} \put(95.00,18.00){\line(0,-1){1.00}} \put(95.00,16.00){\line(0,-1){1.00}} \put(95.00,70.00){\line(0,-1){1.00}} \put(95.00,68.00){\line(0,-1){1.00}} \put(95.00,66.00){\line(0,-1){1.00}} \put(95.00,64.00){\line(0,-1){1.00}} \put(95.00,62.00){\line(0,-1){1.00}} \put(95.00,60.00){\line(0,-1){1.00}} \put(95.00,72.00){\line(0,-1){1.00}} \put(95.00,70.00){\line(0,-1){1.00}} \put(34.00,12.00){\line(0,1){3.00}} \put(95.00,12.00){\line(0,1){3.00}} \put(34.00,13.00){\rule{61.00\unitlength}{1.00\unitlength}} \put(60.00,9.00){\line(0,1){58.00}} \put(76.00,59.00){\makebox(0,0)[lc]{{\footnotesize $\B{I}_3$}}} \put(136.00,69.00){\makebox(0,0)[lc]{{\footnotesize $\B{I}_4$}}} \put(107.00,49.00){\makebox(0,0)[lc]{{\footnotesize $\B{I}_2$}}} \put(98.00,39.00){\makebox(0,0)[lc]{{\footnotesize $\B{I}_1$}}} \put(132.00,73.00){\makebox(0,0)[rb]{{\footnotesize incorrect}}} \put(98.00,13.00){\makebox(0,0)[lc]{{\footnotesize $\B{\cal M}^3_4(\B{\cal I})$}}} \end{picture} \end{center} \caption{\em Example of the Marzullo function $\protect\M$ for $n=4$ and $f=1$. The edges of the result lie in $n-f=3$ input intervals.} \label{fig:marzullo} \end{figure} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% The most important feature of $\M$ is fault-tolerance with respect to faulty input intervals. For example, Figure~\ref{fig:marzullo} shows that $\M_4^3$ provides an accurate result despite the fact that $\B{I}_4$ was non-accurate. We will now embark formally on $\M$'s capabilities in this respect, according to the following road-map: \begin{enumerate} \item We start with the ``single node case,'' where $\M$'s result $\B{M}_p$ computed at a particular non-faulty node~$p$ is considered in isolation. It suffices to account for single faults according to Definition~\ref{def:classfaults} here, which affect $\M$'s input intervals at node~$p$. \begin{itemize} \item Lemma~\ref{lem:accM} gives the number of non-faulty input intervals required for tolerating a certain number of faults, and provides both a lower and an upper bound on $\B{M}_p$. \item Lemma~\ref{lem:monotonicityM} provides a few monotonicity properties of $\M$, that is, upper bound results like $\M^{n-f}_n(\B{\cal I}) \subseteq \M^{n-(f+k)}_n(\B{\cal I})$. \end{itemize} Note that those results are primarily required for accuracy analysis. \item For precision analysis, we also require pairwise properties, that is, statements relating the results $\B{M}_p$ and $\B{M}_q$ of ${\M}$ computed at two different nodes~$p$ and~$q$. Therefore, we have to consider pairwise faults according to Definition~\ref{def:pairfaultiv} here, which affect the pair $\{\B{I}_p^s$, $\B{I}_q^s\}$ received in the broadcast from node~$s$. \begin{itemize} \item Lemma~\ref{lem:precM} gives the number of non-faulty pairs of intervals required for tolerating a certain number of faults, and provides both a lower bound on $\B{M}_p \cap \B{M}_q$ and an upper bound on $\B{M}_p \nccup \B{M}_q$; recall our definition of the nc-union in Section~\ref{Generic Precision Analysis}. \item Lemma~\ref{lem:degradeM} adopts Lemma~\ref{lem:precM} to a slightly extended fault model and, most importantly, shows what happens to $\B{M}_p \nccup \B{M}_q$ when the fault assumptions are violated. \end{itemize} \end{enumerate} We should add here that all lemmas of this section deal with elementary intervals only, even without reference points. Dealing with fully-fledged $\B{\pi}$-accurate intervals (incorporating both precision and accuracy intervals) according to Figure~\ref{fig:intvs} will be postponed to the final analysis of $\OA$ in Section~\ref{Orthogonal Accuracy Convergence Function}. The following Lemma~\ref{lem:accM} reveals how $\M$ behaves in the presence of faults according to Definition~\ref{def:classfaults}. Extending the accomplishments of \cite{Mar84} and \cite{Mar90}, it answers the question of how many non-faulty intervals are required for tolerating a certain number of non-accurate intervals ($\dn$) and unbounded accuracy faults ($\a$). The most important property shown is that $\M$'s result lies within the intersection of $n-2\dn-3\a \geq 1$ non-faulty input intervals. \begin{lem}[Accuracy $\M$]\label{lem:accM} Let $\B{\cal J}=\{\B{J}_1,\ldots,\B{J}_{n}\}$ be a set of $n\geq1$ non-empty compatible accuracy intervals representing $t$, and define $w^h$ to be the length of the largest intersection of $h\geq1$ non-faulty intervals among them, that is, $w^h=\max\{|\B{W}| : \B{W}\in \B{\cal W}^h\}$ for \begin{eqnarray*} \B{\cal W}^h &=&\{\B{W}: \B{W}=\bigcap_{i=1}^h \B{J}_{w_i} \mbox{\ \ with indices $w_i\neq w_j$ for $i\neq j$} \\ & & \mbox{ and $\B{J}_{w_i}\in \B{\cal J}$ being non-faulty}\}. \end{eqnarray*} If $\a'\geq0$ of the $\B{J}_j$ suffer from unbounded accuracy faults and $\dn'\geq0$ are non-accurate, where $\a'\leq \a$ and $\dn'\leq \dn$ with $\a'+\dn'=f'\leq \a+\dn=f0$ of the $n$ intervals are non-faulty), then: \begin{itemize} \item[(1)] $\B{M}={\M}^{n-f}_{n}(\B{\cal J})$ is accurate and contains any intersection $\B{W}\in\B{\cal W}^{n-f}$ of $n-f\geq 1$ different non-faulty input intervals $\B{J}_{w_1}, \dots, \B{J}_{w_{n-f}}$, that is, \begin{equation} \B{W}=\bigcap_{j=1}^{n-f}\B{J}_{w_j} \subseteq \B{M}, \end{equation} so that $|\B{M}|\geq w^{n-f}$ (minimal intersection property). \item[(2)] There are at least $n-2f-\a'\geq n-2f-\a$ different non-faulty input intervals $\B{J}_{b_1},\dots,\B{J}_{b_{n-2f-\a'}}\in \B{\cal J}$ such that \begin{equation} \B{M}\subseteq \bigcap_{j=1}^{n-2f-\a'}\B{J}_{b_j} \subseteq \bigcap_{j=1}^{n-2f-\a}\B{J}_{b'_j},\label{equ:major1} \end{equation} where the set of indices $\{b'_j\}_{1\leq j \leq n-2f-\a}$ is obtained from $\{b_j\}_{1\leq j \leq n-2f-\a'}$ by discarding $\a-\a'$ elements. Hence, $|\B{M}|\leq w^{n-2f-\a'}\leq w^{n-2f-\a}$. \item[(3)] There are at least $f-f'+1\geq1$ non-faulty intervals $\B{J}_{\ell_k}$ respectively $\B{J}_{r_k}$, $1\leq k \leq f-f'+1$, in $\B{\cal J}$ satisfying $\mbox{left}(\B{M})\leq \mbox{left}(\B{J}_{\ell_k})$ respectively $\mbox{right}(\B{M})\geq \mbox{right}(\B{J}_{r_k})$. \end{itemize} \end{lem} \noindent {\bf Proof\,} Since $\B{M}={\M}_{n}^{n-f}(\B{\cal J})$ contains any intersection of at least $n-f$ input intervals by definition, it obviously contains any intersection of $n-f$ non-faulty intervals $\B{W}=\bigcap_{j=1}^{n-f}\B{J}_{w_j}\in\B{\cal W}^{n-f}$. Note that $w_j$, $1\leq j \leq n-f$, just denote the indices of the contributing intervals with respect to $\B{\cal J}$ here. Therefore, it follows that $t\in\B{M}$ and $|\B{M}|\geq w^{n-f}$ as asserted in item~(1) of the lemma. Turning our attention to item~(2), it is apparent that the total number of intersections of left and right edge of $\B{M}$ with non-faulty input intervals is $g_l' + g_r' \geq 2(n-f)-2\a'-\dn'$, because an interval $\B{J}_j$ suffering from an unbounded accuracy fault ($\a'$) could intersect with both edges of $\B{M}$, whereas a non-accurate interval ($\dn'$) can only intersect with one edge of $\B{M}$ due to $t\notin \B{J}_j$ but $t\in\B{M}$. However, since there are only $g'=n-f'$ different non-faulty intervals in $\B{\cal J}=\{\B{J}_1,\ldots,\B{J}_{n}\}$, the pigeonhole principle reveals that \[ g_l' + g_r' -g' \geq 2n-2f-2\a'-\dn'-n+f'=n-2f-\a' \] of the intersected accurate intervals, say $\B{J}_{b_1},\dots,\B{J}_{b_{n-2f-\a'}}$, must be the same. Therefore, $\B{M}$ must lie in the intersection of those intervals and $|\B{M}|\leq w^{n-2f-\a'}$ as asserted. The upper bound in (\ref{equ:major1}) follows immediately from $\a'\leq\a$. Finally, to prove item~(3), consider without loss of generality the left edge of $\B{M}$. We show by contradiction that the left edge of at least $f-f'+1$ non-faulty intervals lies at or right of $\mbox{left}(\B{M})$: If there were at most $f-f'$ such intervals, all $n-f'-(f-f')=n-f$ remaining non-faulty intervals would have their left edge strictly left of $\mbox{left}(\B{M})$. However, this would contradict the minimal intersection property established in item~(1), completing the proof of our lemma. $\Box$ \begin{rmm} \pitem We excluded omission faults in our lemma, since $\M$ as defined in Definition~\ref{def:M} cannot deal with empty intervals. However, as mentioned in Remark~3 following Definition~\ref{def:classfaults}, intervals with omission faults can easily be discarded before $\M$ is applied. Therefore, if $\o'$ of presumed $n$ intervals suffer from an omission fault, we just have to set $n:=n-\o'$ and $f:=f-\o'$ in Lemma~\ref{lem:accM} to obtain the results for this case as well. Note that it is feasible to let $f$ depend on $\o'$, see Lemma~\ref{lem:precM} below. \pitem Interpreting item~(2) of Lemma~\ref{lem:accM} and the previous remark in terms of the usual fault-tolerance degree notion, it follows that $n\geq \o'+2f+\a'+1$ nodes are required to guarantee that $\B{M}$ remains bounded by the length of at least one non-faulty input interval. Hence, as many as \[ n \geq \left\{ \begin{array}{ll} \o'+1 & \mbox{for $\o'$ omission faults,}\\ 2\dn+1 & \mbox{for $\dn'\leq \dn$ non-accurate intervals,}\\ 2\a+\a'\leq 3\a & \mbox{for $\a'\leq \a$ unbounded accuracy faults} \end{array} \right. \] nodes are required for tolerating faults of the given type. It is thus apparent that $\M$ can tolerate $\lfloor (n-1)/2 \rfloor$ non-accurate intervals but only $\lfloor (n-1)/3 \rfloor$ intervals that suffer from unbounded accuracy faults, see \cite{Mar90}. Note carefully that the numbers above do not solely depend on the {\em actual\/} number of faults ($\a'$), but also on their maximum number ($\a$); this is due to the fact that the latter is compiled into the superscript argument of $\M$. \pitem The lower bound on $|\B{M}|$ in item~(1) expresses the rather obvious fact that ${\M}$ cannot improve the accuracy beyond the one ``hidden'' in the input intervals; the term {\em minimal intersection property\/} was coined in \cite{Mar84}. Note that $\B{M}$ contains {\em any\/} intersection of $n-f$ intervals, hence includes intersections involving unbounded accuracy faults as well. \pitem Item~(3) just says that $\B{M}$ contains the left and right edge of at least one (not necessarily the same) non-faulty interval. %may be interpreted as follows: If e.g.\ %$\ell=\mbox{left}(\B{M})$, there must be a reason %for attaining this left edge $\ell$, namely, that at least one non-faulty %interval ``pulls'' $\B{M}$ to this position. That is, %whereas the {\em length\/} of the resulting interval $\B{M}$ is %determined by the %intersection of at least $n-2f$ intervals, which is at least $f+1$ %for the (most important) case $n\geq 3f+1$, it is nevertheless true %that the absolute {\em position\/} of $\B{M}$ within the ``admissible %range'' may be determined by $f-f'+1$, that is, by as few as a single %non-faulty interval. \end{rmm} The following Lemma~\ref{lem:monotonicityM} establishes a few useful monotonicity relations with respect to both parameters and input arguments of $\M$. \begin{lem}[Monotonicity $\M$]\label{lem:monotonicityM} Let $\B{\cal I}=\{\B{I}_1,\dots,\B{I}_n\}$ be a set of $n>f\geq0$ compatible non-empty accuracy intervals representing $t$, with $f'$, $0\leq f'\leq f$, faulty ones among them. Then, $\M^{n-f}_n(\B{\cal I})$ is accurate and satisfies the following monotonicity relations: \begin{itemize} \item[(1)] $\M^{n-f}_n(\B{\cal I}) \subseteq \M^{n-(f+k)}_n(\B{\cal I})$ for any integer $k$ with $0\leq k < n-f$, \item[(2)] ${\M}^{n-f}_n(\B{\cal I})\subseteq {\M}^{n-f}_n(\B{\cal J})$ for any $\B{\cal J}=\{\B{J}_1,\ldots,\B{J}_n\}$ with $\B{I}_l\subseteq\B{J}_l$ for $1\leq l \leq n$, \item[(3)] For $f\geq f'\geq 1$, if $\B{\cal L}=\B{\cal I}\backslash\{\B{I}_j\}$ is obtained by discarding some faulty interval $\B{I}_j$ from $\B{\cal I}$, $\B{\cal M}^{(n-1)-(f-1)}_{n-1}(\B{\cal L})=\B{\cal M}^{n-f}_{n-1}(\B{\cal L})$ is accurate and satisfies \begin{equation} {\M}^{n-f}_{n-1}(\B{\cal L}) \subseteq {\cal M}^{n-f}_n(\B{\cal I}). \end{equation} \end{itemize} \end{lem} \noindent {\bf Proof\,} In the proof of item~(1) of Lemma~\ref{lem:accM}, we argued that $\B{M}={\M}_{n}^{n-f}(\B{\cal I})$ contains any intersection of at least $n-f$ input intervals by definition, hence must be accurate. Since the interval containing any intersection of $n-f-k$ input intervals obviously contains any intersection of $n-f$ input intervals, item~(1) of the lemma follows. Turning our attention to item~(2), it is clear that any particular intersection of $n-f$ intervals in $\B{\cal J}$ contains the intersection of the corresponding intervals in $\B{\cal I}$ if it is non-empty at all. By the same token as before, it hence follows that $\M_n^{n-f}(\B{\cal J})$ must contain $\B{\cal M}^{n-f}_n(\B{\cal I})$ as well. For proving item~(3), the same argument is used again. First of all, $n>f\geq 1$ implies that $n-1 > f-1\geq0$, hence $\B{M}^{(n-1)-(f-1)}_{n-1}(\B{\cal L})$ is accurate. Moreover, discarding a faulty $\B{I}_j$ in $\B{\cal I}$ and simultaneously reducing $f$ by 1 leaves the superscript argument $(n-1)-(f-1)=n-f$ in $\M_{n-1}^{n-f}(\B{\cal L})$ unchanged. Since the interval containing any intersection of $n-f$ input intervals in $\B{\cal I}$ must contain the interval containing any intersection of $n-f$ intervals in $\B{\cal L}\subseteq \B{\cal I}$, the statement given in item~(3) of our lemma follows. $\Box$ \begin{rmm} \pitem It is immediately apparent from the definition of $\M$ that ${\M}^1_n(\B{\cal I})=\bigcup_{i} \B{I}_i$ and ${\M}^n_n(\B{\cal I})=\bigcap_{i} \B{I}_i$, hence $\M_n^{n-f}$ ``changes'' from union to intersection as $n-f$ goes from 1 to $n$. \pitem It is not difficult to show that ${\M}$ is optimal with respect to worst-case accuracy in presence of non-accurate intervals among all interval-valued functions of $n$ interval arguments, as pointed out already in~\cite{Lam87}: Suppose there were a function $\B{\cal F}$ that provides an accurate interval satisfying $\M(\B{\cal I})\not\subseteq \B{\cal F}(\B{\cal I})$, then $\B{M}'=\M(\B{\cal I})\setminus \bigl(\M(\B{\cal I}) \cap \B{\cal F}(\B{\cal I})\bigr)\neq \emptyset$ and there must be an intersection of $n-f$ accurate intervals $\B{A}= \bigcap_{i=1}^{n-f} \B{I}_{b_i}$ so that $\B{A}\cap \B{M}' \neq \emptyset$. However, the (valid) assumption that $t \in \B{A}\cap \B{M}'$ reveals that $\B{\cal F}(\B{\cal I})$ cannot be accurate, providing the required contradiction. \pitem Regarding item~(2) of Lemma~\ref{lem:monotonicityM}, it is important to note that enlarging an input interval (even by a minor amount) can cause a discontinuous jump of an edge of $\M^{n-f}_n(\B{\cal J})$ if a ``new'' intersection of $n-f$ intervals comes up. Just consider shrinking or moving right the faulty interval $\B{I}_4$ in Figure~\ref{fig:marzullo}, which causes the right edge of $\M_4^3(\B{\cal I})$ to shrink to $\mbox{right}(\B{I}_3)$ as soon as $\mbox{left}(\B{I}_4)>\mbox{right}(\B{I}_1)$. This implies that $\M$ does not satisfy a Lipschitz condition with respect to moving (edges of) input intervals, as already noted in \cite{Lam87}. %By the same token, it is easy to see that if an accurate input %interval is moved in a certain direction (without sacrificing %accurateness), both edges of ${\cal %M}^{n-f}_n(\B{\cal I})$ can either move in the same direction or %remain where they are. ACHTUNG: Nur wenn n>2f!!!!! On the other %hand, moving an non-accurate interval could make one edge of ${\cal %M}^{n-f}_n(\B{\cal J})$ jumping in the opposite direction! \pitem Item~(3) of Lemma~\ref{lem:monotonicityM} implies that one should always try to detect and discard faulty intervals before $\M$ is applied, since this can only improve the result. \end{rmm} For establishing precision results, we also require certain ``pairwise'' properties of $\M$, that is, statements relating the results $\B{M}_p$ and $\B{M}_q$ of ${\M}$ computed at different nodes~$p$ and~$q$. This is provided by the following Lemma~\ref{lem:precM}, which is an advanced version of a lemma introduced in \cite{Sch95}. It gives the number of non-faulty pairs of intervals required for tolerating a certain number of \begin{itemize} \itemsep-2pt \item crash faults ($\c'\leq\c$), \item symmetric faults ($\d'\leq\d$), \item asymmetric faults ($\e'\leq\e$). \end{itemize} The most important result of Lemma~\ref{lem:precM} is an upper bound on the nc-union $\B{M}_p \nccup \B{M}_q$, which must lie within at least $n-\min\{\c'+\d',2\c-\c'\}-2\d-3\e \geq 1$ nc-unions $\B{I}_p^s\nccup\B{I}_q^s$ of non-faulty input intervals. Note that the nc-union takes into account that two different nodes $p$ and $q$ usually receive slightly different intervals in the broadcast of a single node~$s$, even if there is no fault. \begin{lem}[Precision $\M$]\label{lem:precM} Let $\B{\cal I}_p=\{\B{I}_p^1,\dots,\B{I}_p^n\}$ and $\B{\cal I}_q=\{\B{I}_q^1,\dots,\B{I}_q^n\}$ be two ordered sets of $n>\c+\d+\e$, $\c,\d,\e\geq0$, compatible (or empty) accuracy intervals representing $t$, where $\e'\leq \e$, $\d'\leq \d$, and $\c'\leq \c$ of the $n$ pairs of intervals $\{\B{I}_p^i, \B{I}_q^i\}$ exhibit asymmetric, symmetric, and crash faults, respectively, and the remaining ones are non-faulty. Define $u^h$ respectively $v^h$ to be the length of the largest intersection of $h\geq1$ nc-unions respectively intersections of pairs of non-faulty intervals, formally $u^h=\max\{|\B{U}| : \B{U}\in \B{\cal U}_{pq}^h\}$ respectively $v^h=\max\{|\B{V}|:\B{V}\in \B{\cal V}_{pq}^h\}$ for \begin{eqnarray*} \B{\cal U}_{pq}^h &=&\{\B{U}: \B{U}=\bigcap_{i=1}^h \B{I}_p^{u_i}\nccup\B{I}_q^{u_i} \mbox{\ \ with $u_i\neq u_j$, $i\neq j$}, \\ & & \mbox{ and non-faulty $\B{I}_p^{u_i}\in \B{\cal I}_p$, $\B{I}_q^{u_i}\in \B{\cal I}_q$}\} \\ \B{\cal V}_{pq}^h &=&\{\B{V}: \B{V}=\bigcap_{i=1}^h \B{I}_p^{v_i}\cap\B{I}_q^{v_i} \mbox{\ \ with $v_i\neq v_j$, $i\neq j$}, \\ & & \mbox{ and non-faulty $\B{I}_p^{v_i}\in \B{\cal I}_p$, $\B{I}_q^{v_i}\in \B{\cal I}_q$}\}. \end{eqnarray*} Let $d_p'$, $0\leq d_p' \leq \d'$, respectively $e_p'$, $0\leq e_p' \leq \e'$, denote the (unknown) number of empty intervals caused by symmetric respectively asymmetric faults at node~$p$, and $\B{\cal J}_p=\{\B{J}_1,\dots,\B{J}_{n_p}\}$ be the set of $n_p=n-o_p$ non-empty intervals obtained from $\B{\cal I}_p$ by discarding any of the (known) $o_p=\c'+d_p'+e_p'\leq \c+\d+\e$ empty intervals caused by crash and symmetric/asymmetric faults. Using the upper bound $f_p=\d+\e-\max\{0,o_p-\c\}$ on the number of intervals in $\B{J}_p$ that (still) may be faulty in presence of $o_p$ omissions, define $\B{M}_p={\M}_{n_p}^{n_p-f_p}(\B{\cal J}_p)$, and analogously $\B{M}_q={\M}_{n_q}^{n_q-f_q}(\B{\cal J}_q)$. Then, \begin{itemize} \item[(1)] both $\B{M}_p$ and $\B{M}_q$ are accurate and \begin{equation} \B{M}_p\cap\B{M}_q \supseteq \bigcap_{j=1}^{n-\c'-\d-\e}\B{I}_p^{v_j}\cap\B{I}_q^{v_j} = \B{V} \label{equ:dmip} \end{equation} for any subset $\B{V} \in \B{\cal V}_{pq}^{n-\c'-\d-\e}$, so that $|\B{M}_p\cap\B{M}_q|\geq v^{n-\c'-\d-\e}$ (distributed minimal intersection property), \item[(2)] there are at least $n-\min\{\c'+\d',2\c-\c'\}-2\d-2\e-\e'$ pairs of non-faulty intervals $\{\B{I}^{u_k}_p$, $\B{I}^{u_k}_q\}$ with $\B{I}^{u_k}_p\in\B{\cal J}_p$ and $\B{I}^{u_k}_q\in\B{\cal J}_q$ such that \begin{equation} \B{M}_p\nccup\B{M}_q \subseteq \bigcap_{k=1}^{n-\min\{\c'+\d',2\c-\c'\}-2\d-2\e-\e'} \B{I}^{u_k}_p \nccup \B{I}^{u_k}_q\label{equ:statem2acc} \end{equation} and hence $|\B{M}_p\nccup\B{M}_q|\leq u^{n-\min\{\c'+\d',2\c-\c'\}-2\d-2\e-\e'}$. \end{itemize} \end{lem} \noindent {\bf Proof\,} First of all, we note that $f_p$ gives indeed an upper bound on the number of intervals in $\B{\cal J}_p$ that still may be faulty in presence of $o_p=\c'+d_p'+e_p' \leq \c'+\d'+\e'\leq \c+\d+\e$ omissions, since $f_p=\d+\e$ if $o_p\leq \c$, and $f_p=\d+\e-(o_p-\c)$ otherwise (accounting for $o_p-\c>0$ symmetric/asymmetric faults that must have caused omissions at node~$p$), hence \begin{equation} f_p\leq \d+\e\label{equ:deffp}. \end{equation} Evidently, at least $n_p-f_p$ of the intervals in $\B{\cal J}_p$ must be non-faulty. Rewriting the definition \begin{equation} n_p-f_p = n-o_p - \d - \e +\max\{0,o_p-\c\} = n-\d-\e+\max\{-o_p,-\c\}\label{equ:upb} \end{equation} and applying $\max\{0,x\}\geq x$ for any $x$, and the simple fact that $$ \max\{-o_p,-\c\}\leq -\c' $$ since obviously $o_p\geq \c'$ and $\c'\leq \c$, it follows easily that \begin{equation} n-\c-\d-\e \leq n_p-f_p \leq n - \c' - \d - \e \leq n-\d-\e. \end{equation} Of course, analogous bounds hold for $n_q-f_q$. Lemma~\ref{lem:accM} is applicable, and it follows that $\B{M}_p$ and $\B{M}_q$ are both accurate and satisfy the (local) minimal intersection property. That is, $\B{M}_p$ contains any intersection of $n_p-f_p\leq n-\c'-\d-\e$ non-faulty intervals present in $\B{\cal J}_p$. If $\{v_j\}_{1\leq j \leq n-\c'-\d-\e}$ denotes any set of different indices of non-faulty pairs of intervals $\B{I}_p^{v_j}\in\B{\cal I}_p$, $\B{I}_q^{v_j}\in\B{\cal I}_q$ (of course also present in $\B{\cal J}_p$, $\B{\cal J}_q$), we thus have \[ \B{W}_p=\bigcap_{j=1}^{n-\c'-\d-\e}\B{I}_p^{v_j} \subseteq \bigcap_{j=1}^{n_p-f_p}\B{I}_p^{v_j} \subseteq \B{M}_p \] and, for the same set $\{v_j\}$, $\B{W}_q=\bigcap_{j=1}^{n-\c'-\d-\e}\B{I}_q^{v_j} \subseteq \B{M}_q$. By elementary set algebra, it thus follows that $\B{V}=\B{W}_p\cap\B{W}_q\in\B{\cal V}^{n-\c'-\d-\e}$ satisfies (\ref{equ:dmip}). Finally, $|\B{M}_p\cap\B{M}_q|\geq v^{n-\c'-\d-\e}$ is a simple consequence of the definition of $v^h$ as the maximum length of $\B{V}\in\B{\cal V}_{pq}^h$. This completes the proof of item~(1). For item~(2), suppose that the left respectively right edge of $\B{M}_p$ respectively $\B{M}_q$ intersects with $g_{p,l}$ respectively $g_{q,r}$ intervals belonging to a non-faulty pair of intervals in $\B{\cal I}_p$, $\B{\cal I}_q$. We must have \begin{eqnarray} g_{p,l} &\geq& n_p-f_p - (\e'-e_p') - (s_{\mbox{\scriptsize left}}'-d_{p,\mbox{\scriptsize left}}')\nonumber\\ &\geq& n-\d-\e+\max\{-o_p,-\c\}-\e'-s_{\mbox{\scriptsize left}}' + d_{p,\mbox{\scriptsize left}}' + e_p'\nonumber\\ g_{q,r} &\geq& n_q-f_q - (\e'-e_q') - (s_{\mbox{\scriptsize right}}'-d_{q,\mbox{\scriptsize right}}')\nonumber\\ &\geq& n-\d-\e+\max\{-o_q,-\c\}-\e'-s_{\mbox{\scriptsize right}}'+d_{q,\mbox{\scriptsize right}}' + e_q'.\nonumber \end{eqnarray} where $s_{\mbox{\scriptsize left}}'+s_{\mbox{\scriptsize right}}'=\d'\leq \d$ are the number of symmetrically faulty pairs of intervals lying left respectively right of $t$, and $d_{p,\mbox{\scriptsize left}}'+d_{p,\mbox{\scriptsize right}}' = d_p'$, $d_{q,\mbox{\scriptsize left}}'+d_{q,\mbox{\scriptsize right}}' = d_q'$ denote the number of omissions among them at node $p$ respectively $q$; the lower bounds follow immediately from (\ref{equ:upb}). However, we only have $g= n -\c' - \d' -\e'$ different non-faulty pairs of intervals. Thus, the pigeonhole principle reveals that $$ g_{p,l}+g_{q,r}-g\ge $$ \begin{eqnarray} &\geq& 2n + \max\{-o_p,-\c\} + \max\{-o_q,-\c\} - 2\d -2\e - 2\e' -\d' \nonumber\\ &&+ d_{p,\mbox{\scriptsize left}}' + d_{q,\mbox{\scriptsize right}}' + e_p' + e_q' - n + \c' +\d' +\e'\nonumber\\ &\geq& n + \max\{-\c'-d_{p,\mbox{\scriptsize right}}',-\c+d_{p,\mbox{\scriptsize left}}'+e_p'\} \nonumber\\ &&+\max\{-\c'-d_{q,\mbox{\scriptsize left}}',-\c+d_{q,\mbox{\scriptsize right}}'+e_q'\} + \c' -2\d -2\e -\e'\nonumber\\ &\geq& n+\max\{-2\c'-\d',-2\c\} + \c' -2\d -2\e -\e'\nonumber\\ &\geq& n-\min\{\c'+\d',2\c-\c'\}-2\d-2\e-\e' \nonumber \end{eqnarray} of them must be the same. Abbreviating $\mu=\min\{\c'+\d',2\c-\c'\}$, we can conclude that there are at least $n-\mu-2\d-2\e-\e'$ pairs of accurate intervals, say, $\B{I}_p^{b_1}\nccup\B{I}_q^{b_1},\dots,\B{I}_p^{b_{n-\mu-2\d-2\e-\e'}}\nccup \B{I}_q^{b_{n-\mu-2\d-2\e-\e'}}$ with $\B{I}_p^{b_i}\in \B{\cal J}_p$ and $\B{I}_q^{b_i}\in \B{\cal J}_q$ satisfying \begin{equation} \B{M}_p\nccup\B{M}_q\subseteq \bigcap_{j=1}^{n-\mu-2\d-2\e-\e'}\B{I}_p^{b_j} \nccup\B{I}_q^{b_j} \in \B{\cal U}_{pq}^{n-\mu-2\d-2\e-\e'},\label{equ:case2} \end{equation} which proves (\ref{equ:statem2acc}). To complete the proof of Lemma~\ref{lem:precM}, it only remains to justify $|\B{M}_p\nccup\B{M}_q|\leq u^{n-\mu-2\d-2\e-\e'}$, which is a trivial consequence of (\ref{equ:case2}). $\Box$ \begin{rmm} \pitem Note carefully that Lemma~\ref{lem:accM} could also be used to deduce a precision-related result: Since $\B{M}_p$ and $\B{M}_q$ are both accurate and hence contain $t$, it follows from item~(2) that $|\B{M}_p\cup\B{M}_q|\leq 2w^{n-2f-\a}$, so that the same holds true for $|\B{M}_p\nccup\B{M}_q|$. However, comparison with item~(2) of Lemma~\ref{lem:precM} reveals that this result is roughly twice as large and hence insufficient for precision enhancement. \pitem Our crash faults are more severe than the (systemwide consistently perceived) {\em benign faults\/} of \cite{AK96}, since it cannot be decided locally whether an omissive interval belongs to a crash fault or to an (inconsistent) receive omission. However, it is of course possible to ``merge'' crash and symmetric faults, in the sense that the former are counted in $\d'$ respectively $\d$ and $\c'=\c=0$ (note that $n_p-f_p=n-\d-\e$ in this case). After all, we already accounted for symmetric/asymmetric faults involving empty intervals in the proof of Lemma~\ref{lem:precM}. \pitem Interpreting the accomplishments of Lemma~\ref{lem:precM} and the previous remark in terms of the usual fault-tolerance degree notion, it turns out that $n\geq \min\{\c'+\d',2\c-\c'\} + 2\d +2\e+\e'+1$ nodes are required to guarantee that $\B{M}_p\nccup\B{M}_q$ remains bounded by the length of the nc-union of at least one pair of non-faulty input intervals. Hence, as many as \[ n \geq \left\{ \begin{array}{ll} % b'+1 & \mbox{for $b'$ benign faults,}\\ \min\{\c'+\d',2\c-\c'\}+1 & \mbox{for $\c'$ crash faults,}\\ 2\d+1 & \mbox{for $\d'\leq \d$ symmetric faults,}\\ 2\e+\e'+1 \leq 3\e+1 & \mbox{for $\e'\leq \e$ asymmetric faults} \end{array} \right. \] nodes are required for tolerating faults of the given type. \pitem It should be clear from the proof of Lemma~\ref{lem:precM} that the property that really pins down symmetric faults is the following one: If a symmetrically faulty interval $\B{I}_q^s$ intersects, say, with the right edge of $\B{M}_q$ (correctly accounted for in $s_{\mbox{\scriptsize right}}$), then its corresponding $\B{I}_p^s$ must not intersect with the left edge of $\B{M}_p$ (since it is not accounted for in $s_{\mbox{\scriptsize left}}$). This is the reason why $\B{I}_p^s\neq0$ being faulty and $\B{I}_q^s\neq0$ being non-faulty must be counted as an asymmetric fault in item~(2) of Definition~\ref{def:pairfaultiv}. \pitem The proof of Lemma~\ref{lem:precM} reveals the ultimate reason for using nc-unions $\nccup$ instead of $\cup$ in the statement of item~(2): It may be the case that, say, $\B{M}_q \subseteq \B{M}_p$, such that $\B{M}_p$ would determine both left and right edge of $\B{M}_p\cup\B{M}_q$. By applying Lemma~\ref{lem:accM} with $n:=n_p$, $f:=f_p$, and $\a'\leq \e'$ (as well as $\a\leq \e$), we could show that there are at least $n_p-2f_p-\a' \geq n-\mu-2\d-2\e-\e'$ non-faulty intervals $\B{I}_p^{b_j}$ in $\B{\cal J}_p$ the intersection of which majorizes $\B{M}_p$. This does not imply, however, that all of those intervals appear in $\B{\cal J}_q$ as well -- just think of symmetric faults appearing non-faulty at $p$ but omissive at $q$. Hence, we cannot claim that all the unions $\B{I}_p^{b_j} \cup \B{I}_q^{b_j}$ ---the intersection of which would of course majorize $\B{M}_q \cup \B{M}_p$--- involve non-fauly intervals only. Clearly, focussing upon $\B{M}_p\nccup\B{M}_q\subseteq\B{M}_p\cup\B{M}_q$ entirely avoids this difficulty. \end{rmm} The following lemma shows that the results of Lemma~\ref{lem:precM} remain valid if a more severe fault comes out as a less severe one, and shows what happens if certain fault assumptions are violated. Note that crash faults are counted as symmetric ones here for simplicity. \begin{lem}[Precision/Graceful Degradation $\M$]\label{lem:degradeM} Let $\B{\cal I}_p=\{\B{I}_p^1,\dots,\B{I}_p^n\}$ and $\B{\cal I}_q=\{\B{I}_q^1,\dots,\B{I}_q^n\}$ be two ordered sets of $n>\d+\e$, $\d,\e\geq0$, compatible (or empty) accuracy intervals representing $t$, where $\d'\leq\d$ respectively $\e'\leq\e$ of the $n$ pairs of intervals $\{\B{I}_p^i, \B{I}_q^i\}$ exhibit symmetric (or weaker) respectively asymmetric (or weaker) faults, and the remaining ones are non-faulty. As in Lemma~\ref{lem:precM}, define $u^h$ respectively $v^h$ to be the length of the largest intersection of $h\geq1$ nc-unions ($\in \B{\cal U}_{pq}^h$) respectively intersections ($\in \B{\cal V}_{pq}^{h}$) of pairs of non-faulty intervals. Let $\B{\cal J}_p=\{\B{J}_1,\dots,\B{J}_{n_p}\}$ be the set of $n_p=n-o_p$ non-empty intervals obtained from $\B{\cal I}_p$ by discarding any of the $o_p$ empty intervals caused by omissions. Using the upper bound $f_p=\d+\e-o_p$ on the number of intervals in $\B{J}_p$ that (still) may be faulty in presence of $o_p$ omissions, define \[ \B{M}_p={\M}_{n_p}^{n_p-f_p}(\B{\cal J}_p)=\B{\cal M}_{n_p}^{n-\d-\e}(\B{\cal J}_p), \] and analogously $\B{M}_q={\M}_{n_q}^{n-\d-\e}(\B{\cal J}_q)$. Then: \begin{enumerate} \item[(1)] Both $\B{M}_p$ and $\B{M}_q$ are accurate and \begin{equation} \B{M}_p\cap\B{M}_q \supseteq \bigcap_{j=1}^{n-\d-\e}\B{I}_p^{v_j}\cap\B{I}_q^{v_j} = \B{V}\label{equ:dmipnew} \end{equation} for any possible subset $\B{V}\in \B{\cal V}_{pq}^{n-\d-\e}$, so that $|\B{M}_p\cap\B{M}_q|\geq v^{n-\d-\e}$ (distributed minimal intersection property). \item[(2)] There are at least $n-2\d-2\e-\e'\geq n-2\d-3\e$ pairs of non-faulty intervals $\{\B{I}^{u_k}_p$, $\B{I}^{u_k}_q\}$ with $\B{I}^{u_k}_p\in\B{\cal J}_p$ and $\B{I}^{u_k}_q\in\B{\cal J}_q$ such that \begin{equation} \B{M}_p\nccup\B{M}_q \subseteq \bigcap_{k=1}^{n-2\d-2\e-\e'} \B{I}^{u_k}_p \nccup \B{I}^{u_k}_q \subseteq \bigcap_{k=1}^{n-2\d-3\e} \B{I}^{u_k'}_p \nccup \B{I}^{u_k'}_q,\label{equ:upbdprecM} \end{equation} where $\{u'_k\}_{1\leq k \leq n-2\d-3\e}$ is obtained from $\{u_k\}_{1\leq k \leq n-2\d-2\e-\e'}$ by discarding $\e-\e'$ arbitrary elements. Hence, $|\B{M}_p\nccup\B{M}_q|\leq u^{n-2\d-2\e-\e'} \leq u^{n-2\d-3\e}$. \item[(3)] Assume that the fault model is violated in the sense that $f'=\d'+\e'> \d+\e$ but still $n\geq 2f'+\a'+1$, where $\a'\leq \e'$ denotes the number of pairs of intervals that involve unbounded accuracy faults. If $\B{M}_p$ and $\B{M}_q$ exist, that is, sufficiently many intersecting input intervals exist to compute $\M$, then there are $n-2f'-\a'$ non-faulty intervals $\B{I}_p^{p_1},\dots,\B{I}_p^{p_{n-2f'-\a'}}$ in $\B{\cal J}_p$ and $n-2f'-\a'$ non-faulty intervals $\B{I}_q^{q_1},\dots,\B{I}_q^{q_{n-2f'-\a'}}$ in $\B{\cal J}_q$ such that \begin{equation} \B{M}_p\cup\B{M}_q\subseteq \left(\bigcap_{j=1}^{n-2f'-\a'}\B{I}_p^{p_j}\right)\cup \left(\bigcap_{j=1}^{n-2f'-\a'}\B{I}_q^{q_j}\right).\label{equ:gracebd} \end{equation} Hence, $|\B{M}_p\cup\B{M}_q| \leq w^{n-2f'-\a'}_p+w^{n-2f'-\a'}_q$, where $w^h_p$ respectively $w^h_q$ denote the length of the largest intersection of $h$ accurate intervals in $\B{\cal I}_p$ respectively $\B{\cal I}_q$. Nevertheless, $\B{M}_p$ and $\B{M}_q$ are not necessarily accurate and possibly not even consistent; accurateness is guaranteed, however, if $f'\leq \d+\e$ but all $f'$ faults are asymmetric ones. \end{enumerate} \end{lem} \noindent {\bf Proof\,} Since crash faults are now considered as symmetric ones and hence accounted for in $\d'$ and $\d$, see Remark~2 on Lemma~\ref{lem:precM}, items~(1) and~(2) follow directly from adopting the results of Lemma~\ref{lem:precM} to $\c'=\c=0$. Note that $n_p-f_p = n-\d-\e$ here. %To justify that simple %faults may even appear as benign ones, recall that benign faults manifest %as consistent omissions. Temporarily setting $\d:=\d-1$ and %$n:=n-1$ in the adopted Lemma~\ref{lem:precM} confirms that the %bounds given before remain amply valid. To confirm the assertions for asymmetric faults appearing as weaker ones, just consider the expressions supplied by Lemma~\ref{lem:precM} when temporarily setting $\e:=\e-1$ and $\d:=\d+1$. To show item~(3), we first note that we only have to consider the case where $n_p=n-o_p\geq n-\d-\e$, since otherwise there would have been too many omissions to compute $\B{M}_p$. Thus, \begin{equation} \B{M}_p={\M}_{n_p}^{n-\d-\e}(\B{\cal J}_p) \subseteq {\M}_{n_p}^{n-f'}(\B{\cal J}_p)\label{equ:equabc} \end{equation} according to item~(1) of Lemma~\ref{lem:monotonicityM}. Lemma~\ref{lem:accM} is now applicable to the right-hand side of (\ref{equ:equabc}) and it follows by its item~(2) that \[ \B{M}_p\subseteq \bigcap_{j=1}^{n-2f'-\a'}\B{J}_p^{p_j}. \] An analogous result holds for $\B{M}_q$. Of course, the majorizing intersections for $\B{M}_p$ and~$\B{M}_q$ involve non-faulty intervals only, hence are accurate and thus consistent. This justifies (\ref{equ:gracebd}) and thus the condition on $|\B{M}_p\cup\B{M}_q|$ given in the lemma. Note carefully, however, that this does not imply that $\B{M}_p$ and $\B{M}_q$ are accurate or even just consistent! On the other hand, if $f'\leq \d+\e$, it follows from item~(1) of Lemma~\ref{lem:accM} applied to the left-hand side of (\ref{equ:equabc}) that $\B{M}_p$ (and analogously $\B{M}_q$) is accurate. $\Box$ \begin{rmm} \pitem It follows from item~(3) of the above lemma that there are two possibilities in case of a violation of the fault assumptions: Either a node recognizes this fact because there are not enough accurate intervals to compute $\B{\cal M}$, or the computed interval is not ``too wrong'' (covered by an interval that is at most about twice as large as the usual one, see item~(2) of Lemma~\ref{lem:degradeM}). Obviously, this is some form of {\em graceful degradation\/} of the algorithm's performance. \pitem Evidently, the worst situation with respect to the number of faults where one can hope to get a meaningful result is $n\geq 2f'+1$. Item~(3) of Lemma~\ref{lem:degradeM} can be used to deduce a result for this case as well: Setting $\a'=0$ and declaring any interval with an unbounded accuracy fault as being ``non-faulty'', we get from (\ref{equ:gracebd}) that $\B{M}_p\cup\B{M}_q$ and hence $\B{M}_p\nccup\B{M}_q$ lies in the union of the intersection of $n-2f'$ ``non-faulty'' intervals in $\B{\cal J}_p$ respectively $\B{\cal J}_q$. \end{rmm} \section{Orthogonal Accuracy Convergence Function} \label{Orthogonal Accuracy Convergence Function} Whereas ${\M}$ is optimal with respect to the length of the resulting accuracy interval, it can nevertheless exhibit large discontinuous jumps even for minor shifts of a faulty input interval, recall Remarks~2 and~3 on Lemma~\ref{lem:monotonicityM}. For that reason, it has already been argued in \cite{Lam87} that a ``naive'' clock synchronization algorithm that places the reference point (= clock value) to the centerpoint of ${\M}$'s result is incapable of guaranteeing small precision if the input intervals are comparatively large. Our example run in Figure~\ref{fig:precmar} justifies this claim: Consider a system of four nodes~A, B, C, D with interval clocks having the following characteristics: \begin{itemize} \item {A's} interval clock is deteriorated by $\pm 2$ units during the resynchronization period~$P$, but actually runs at perfect rate, \item {B's} interval clock is deteriorated by $\pm 1$ unit and is actually one unit ahead of real-time after one period $P$, \item {C's} interval clock is deteriorated by $\pm 1$ unit and is actually one unit behind of real-time after one period $P$, \item {D's} clock exhibits byzantine faulty behavior in the sense that D's accuracy interval received by node~$p$ mimics $p$'s current interval clock. \end{itemize} Assuming fault-free, zero-delay communication and initially perfectly synchronized interval clocks $\B{C}_p(0)=[0\pm\B{1}]$ for $p=A, B, C$, we obtain the scenario depicted in Figure~\ref{fig:precmar}. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{figure}[htb] \begin{center} \unitlength=0.60mm \special{em:linewidth 0.4pt} \linethickness{0.4pt} \begin{picture}(217.33,57.00) \put(20.00,36.00){\circle*{3.00}} \put(20.00,26.00){\circle*{3.00}} \put(20.00,16.00){\circle*{3.00}} \put(20.00,44.00){\line(0,-1){1.00}} \put(20.00,42.00){\line(0,-1){1.00}} \put(20.00,40.00){\line(0,-1){1.00}} \put(20.00,38.00){\line(0,-1){1.00}} \put(20.00,36.00){\line(0,-1){1.00}} \put(20.00,33.00){\line(0,1){1.00}} \put(20.00,32.00){\line(0,-1){1.00}} \put(20.00,30.00){\line(0,-1){1.00}} \put(20.00,28.00){\line(0,-1){1.00}} \put(20.00,26.00){\line(0,-1){1.00}} \put(20.00,24.00){\line(0,-1){1.00}} \put(20.00,22.00){\line(0,-1){1.00}} \put(20.00,20.00){\line(0,-1){1.00}} \put(20.00,18.00){\line(0,-1){1.00}} \put(20.00,46.00){\makebox(0,0)[cb]{{\tiny $t=0$}}} \put(75.00,36.00){\circle*{3.00}} \put(78.04,26.00){\circle*{3.00}} \put(71.96,16.00){\circle*{3.00}} \put(75.00,44.00){\line(0,-1){1.00}} \put(75.00,42.00){\line(0,-1){1.00}} \put(75.00,40.00){\line(0,-1){1.00}} \put(75.00,38.00){\line(0,-1){1.00}} \put(75.00,36.00){\line(0,-1){1.00}} \put(75.00,33.00){\line(0,1){1.00}} \put(75.00,32.00){\line(0,-1){1.00}} \put(75.00,30.00){\line(0,-1){1.00}} \put(75.00,28.00){\line(0,-1){1.00}} \put(75.00,26.00){\line(0,-1){1.00}} \put(75.00,24.00){\line(0,-1){1.00}} \put(75.00,22.00){\line(0,-1){1.00}} \put(75.00,20.00){\line(0,-1){1.00}} \put(75.00,18.00){\line(0,-1){1.00}} \put(75.00,16.00){\line(0,-1){1.00}} \put(75.00,14.00){\line(0,-1){1.00}} \put(75.00,12.00){\line(0,-1){1.00}} \put(75.00,10.00){\line(0,-1){1.00}} \put(75.00,8.00){\line(0,-1){1.00}} \put(75.00,6.00){\line(0,-1){1.00}} \put(75.00,4.00){\line(0,-1){1.00}} \put(75.00,2.00){\line(0,-1){1.00}} \put(75.00,46.00){\makebox(0,0)[cb]{{\tiny $t=P$}}} \put(20.00,16.00){\line(0,-1){1.00}} \put(20.00,14.00){\line(0,-1){1.00}} \put(20.00,12.00){\line(0,-1){1.00}} \put(20.00,10.00){\line(0,-1){1.00}} \put(20.00,8.00){\line(0,-1){1.00}} \put(20.00,6.00){\line(0,-1){1.00}} \put(20.00,4.00){\line(0,-1){1.00}} \put(20.00,2.00){\line(0,-1){1.00}} \put(130.00,36.00){\circle*{3.00}} \put(136.00,26.00){\circle*{3.00}} \put(124.00,16.00){\circle*{3.00}} \put(130.00,44.00){\line(0,-1){1.00}} \put(130.00,42.00){\line(0,-1){1.00}} \put(130.00,40.00){\line(0,-1){1.00}} \put(130.00,38.00){\line(0,-1){1.00}} \put(130.00,36.00){\line(0,-1){1.00}} \put(130.00,33.00){\line(0,1){1.00}} \put(130.00,32.00){\line(0,-1){1.00}} \put(130.00,30.00){\line(0,-1){1.00}} \put(130.00,28.00){\line(0,-1){1.00}} \put(130.00,26.00){\line(0,-1){1.00}} \put(130.00,24.00){\line(0,-1){1.00}} \put(130.00,22.00){\line(0,-1){1.00}} \put(130.00,20.00){\line(0,-1){1.00}} \put(130.00,18.00){\line(0,-1){1.00}} \put(130.00,16.00){\line(0,-1){1.00}} \put(130.00,14.00){\line(0,-1){1.00}} \put(130.00,12.00){\line(0,-1){1.00}} \put(130.00,10.00){\line(0,-1){1.00}} \put(130.00,8.00){\line(0,-1){1.00}} \put(130.00,6.00){\line(0,-1){1.00}} \put(130.00,4.00){\line(0,-1){1.00}} \put(130.00,2.00){\line(0,-1){1.00}} \put(130.00,46.00){\makebox(0,0)[cb]{{\tiny $t=2P$}}} \put(84.01,24.52){\line(0,1){3.00}} \put(84.00,34.52){\line(0,1){3.00}} \put(66.00,34.52){\line(0,1){3.00}} \put(145.00,24.67){\line(0,1){3.00}} \put(127.00,24.67){\line(0,1){3.00}} \put(23.03,34.52){\line(0,1){3.00}} \put(17.00,24.48){\line(0,1){3.00}} \put(23.00,24.48){\line(0,1){3.00}} \put(17.00,14.48){\line(0,1){3.00}} \put(23.00,14.48){\line(0,1){3.00}} \put(4.00,36.00){\makebox(0,0)[cc]{{\footnotesize A}}} \put(4.00,26.00){\makebox(0,0)[cc]{{\footnotesize B}}} \put(4.00,16.00){\makebox(0,0)[cc]{{\footnotesize C}}} \put(4.00,6.00){\makebox(0,0)[cc]{{\footnotesize D}}} \put(21.00,6.00){\makebox(0,0)[cc]{{\footnotesize arb.\ fault}}} \put(76.00,6.00){\makebox(0,0)[cc]{{\footnotesize arb.\ fault}}} \put(131.00,6.00){\makebox(0,0)[cc]{{\footnotesize arb.\ fault}}} \put(185.00,36.00){\circle*{3.00}} \put(194.00,26.00){\circle*{3.00}} \put(176.00,16.00){\circle*{3.00}} \put(185.00,44.00){\line(0,-1){1.00}} \put(185.00,42.00){\line(0,-1){1.00}} \put(185.00,40.00){\line(0,-1){1.00}} \put(185.00,38.00){\line(0,-1){1.00}} \put(185.00,36.00){\line(0,-1){1.00}} \put(185.00,33.00){\line(0,1){1.00}} \put(185.00,32.00){\line(0,-1){1.00}} \put(185.00,30.00){\line(0,-1){1.00}} \put(185.00,28.00){\line(0,-1){1.00}} \put(185.00,26.00){\line(0,-1){1.00}} \put(185.00,24.00){\line(0,-1){1.00}} \put(185.00,22.00){\line(0,-1){1.00}} \put(185.00,20.00){\line(0,-1){1.00}} \put(185.00,18.00){\line(0,-1){1.00}} \put(185.00,16.00){\line(0,-1){1.00}} \put(185.00,14.00){\line(0,-1){1.00}} \put(185.00,12.00){\line(0,-1){1.00}} \put(185.00,10.00){\line(0,-1){1.00}} \put(185.00,8.00){\line(0,-1){1.00}} \put(185.00,6.00){\line(0,-1){1.00}} \put(185.00,4.00){\line(0,-1){1.00}} \put(185.00,2.00){\line(0,-1){1.00}} \put(185.00,46.00){\makebox(0,0)[cb]{{\tiny $t=3P$}}} \put(188.07,14.37){\line(0,1){3.00}} \put(163.99,14.37){\line(0,1){3.00}} \put(205.89,24.52){\line(0,1){3.00}} \put(181.81,24.52){\line(0,1){3.00}} \put(163.90,34.37){\line(0,1){3.00}} \put(205.90,34.37){\line(0,1){3.00}} \put(186.00,6.00){\makebox(0,0)[cc]{{\footnotesize arb.\ fault}}} \put(17.00,15.45){\rule{6.00\unitlength}{1.00\unitlength}} \put(17.03,34.52){\line(0,1){3.00}} \put(17.00,35.53){\rule{6.00\unitlength}{1.00\unitlength}} \put(17.00,25.57){\rule{6.00\unitlength}{1.00\unitlength}} \put(66.00,35.60){\rule{18.00\unitlength}{1.00\unitlength}} \put(78.01,14.52){\line(0,1){3.00}} \put(71.86,24.52){\line(0,1){3.00}} \put(66.01,14.52){\line(0,1){3.00}} \put(72.00,25.53){\rule{12.00\unitlength}{1.00\unitlength}} \put(66.00,15.53){\rule{12.00\unitlength}{1.00\unitlength}} \put(145.00,34.67){\line(0,1){3.00}} \put(115.00,34.67){\line(0,1){3.00}} \put(133.00,14.52){\line(0,1){3.00}} \put(115.00,14.52){\line(0,1){3.00}} \put(127.00,25.62){\rule{18.00\unitlength}{1.00\unitlength}} \put(115.00,35.53){\rule{30.00\unitlength}{1.00\unitlength}} \put(115.00,15.47){\rule{18.00\unitlength}{1.00\unitlength}} \put(164.00,35.43){\rule{42.00\unitlength}{1.00\unitlength}} \put(182.00,25.62){\rule{24.00\unitlength}{1.00\unitlength}} \put(164.00,15.43){\rule{24.00\unitlength}{1.00\unitlength}} \put(9.00,53.00){\vector(1,0){208.33}} \put(217.00,57.00){\makebox(0,0)[cb]{{\footnotesize $t$}}} \put(20.00,52.00){\line(0,1){2.00}} \put(23.00,52.00){\line(0,1){2.00}} \put(17.00,52.00){\line(0,1){2.00}} \put(69.00,52.00){\line(0,1){2.00}} \put(72.00,52.00){\line(0,1){2.00}} \put(66.00,52.00){\line(0,1){2.00}} \put(78.00,52.00){\line(0,1){2.00}} \put(81.00,52.00){\line(0,1){2.00}} \put(75.00,52.00){\line(0,1){2.00}} \put(84.00,52.00){\line(0,1){2.00}} \put(118.00,52.00){\line(0,1){2.00}} \put(121.00,52.00){\line(0,1){2.00}} \put(115.00,52.00){\line(0,1){2.00}} \put(127.00,52.00){\line(0,1){2.00}} \put(130.00,52.00){\line(0,1){2.00}} \put(124.00,52.00){\line(0,1){2.00}} \put(133.00,52.00){\line(0,1){2.00}} \put(139.00,52.00){\line(0,1){2.00}} \put(142.00,52.00){\line(0,1){2.00}} \put(136.00,52.00){\line(0,1){2.00}} \put(145.00,52.00){\line(0,1){2.00}} \put(167.00,52.00){\line(0,1){2.00}} \put(170.00,52.00){\line(0,1){2.00}} \put(164.00,52.00){\line(0,1){2.00}} \put(176.00,52.00){\line(0,1){2.00}} \put(179.00,52.00){\line(0,1){2.00}} \put(173.00,52.00){\line(0,1){2.00}} \put(182.00,52.00){\line(0,1){2.00}} \put(188.00,52.00){\line(0,1){2.00}} \put(191.00,52.00){\line(0,1){2.00}} \put(185.00,52.00){\line(0,1){2.00}} \put(194.00,52.00){\line(0,1){2.00}} \put(200.00,52.00){\line(0,1){2.00}} \put(203.00,52.00){\line(0,1){2.00}} \put(197.00,52.00){\line(0,1){2.00}} \put(206.00,52.00){\line(0,1){2.00}} \end{picture} \end{center} \caption{\em Example showing the lacking precision enhancement property of Marzullo's function $\protect\M$ with centerpoint setting. Since node~D mimics $\protect\B{C}_p(t)$ when received at any node~$p$, the interval computed by $\protect\M_4^3$ at $t=P, 2P, \dots,$ reconfirms the current $\protect\B{C}_p(t)$.} \label{fig:precmar} \end{figure} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Each node receives the interval clocks $\B{C}_p$ of the non-faulty nodes~A, B, C exactly as shown at $t=kP$, $k\geq1$. One observes that the interval $\B{M}_p$ obtained by applying ${\M}_4^3$ to the $\B{I}_p^q$'s received by node~$p$ is always exactly $\B{C}_p$ ---no precision enhancement will ever take place here; the reference points of $\B{C}_B$ and~$\B{C}_C$ will drift apart perpetually. Our algorithm will fix this problem by applying ${\M}_4^3$ to the associated $\B{\pi}^H$-precision intervals $\ppI{\B{I}}_p^q$ instead of $\B{I}_p^q$, recall our exposition in Subsection~\ref{Generic Precision Analysis}. In the example of Figure~\ref{fig:precmar}, $\B{\pi}^H$ must satisfy $|\B{\pi}^H|=2+4$ units because of the initial precision (= 2~units) plus twice the maximum deterioration during $P$ (= $2\cdot 2$~units). The intervals fed into ${\M}_4^3$ are hence trimmed to length $\pi^H$, and considering the resulting intervals $\ppI{\B{M}}_p$ and $\ppI{\B{M}}_q$ at two different nodes $p$ and $q$, one finds that the reference points cannot be further apart than $\pi^H/2$ (centerpoint setting assumed), since $\ppI{\B{M}}_p\nccup\ppI{\B{M}}_q$ has length at most $\pi^H$ by item~(2) of Lemma~\ref{lem:precM}. Since the above considerations are only meaningful for maintaining precision, that is, setting the reference point of $\B{C}_p$, the optimality of ${\M}$ nevertheless recommends its use for determining left and right edge of $\B{C}_p$. However, this requires some care since the reference point computed via the associated precision intervals might lie outside of the accuracy interval. This is demonstrated by the following example: Reconsider our system of four nodes~A, B, C, D, now with the following characteristics: \begin{itemize} \item {A's} interval clock is deteriorated by $\pm 1$ unit and is actually one unit ahead of real-time after one period $P$, \item {B's, C's} interval clocks are deteriorated by $\pm 1$ unit and are actually one unit behind real-time after period $P$, \item {D's} clock exhibits symmetric faults. \end{itemize} Assuming fault-free, zero-delay communication and initially synchronized clocks satisfying $\B{C}_p(t_0)=\ppI{\B{C}}_p(t_0)$ for $p=A,B,C$ and $\B{\pi}_0=[-1,1]$, so that $\B{\pi}^H=[-2,2]$ (since maximum deterioration during $P$ is $\pm1$), consider the evolution of accuracy intervals during two rounds depicted in Figure~\ref{fig:accprec}. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{figure}[htb] \begin{center} \unitlength=0.895mm \special{em:linewidth 0.4pt} \linethickness{0.4pt} \begin{picture}(153.00,91.00) \put(16.00,72.00){\circle*{2.00}} \put(10.00,62.00){\circle*{2.00}} \put(10.00,52.00){\circle*{2.00}} \put(13.00,82.00){\makebox(0,0)[cb]{{\footnotesize $t_0=\tau_0$}}} \put(70.04,62.00){\circle*{2.00}} \put(69.96,52.00){\circle*{2.00}} \put(76.00,82.00){\makebox(0,0)[cb]{{\footnotesize $t_1$}}} \put(130.00,17.00){\circle*{2.00}} \put(139.00,82.00){\makebox(0,0)[cb]{{\footnotesize $t_2$}}} \put(76.13,60.52){\line(0,1){3.00}} \put(121.00,15.67){\line(0,1){3.00}} \put(19.03,70.52){\line(0,1){3.00}} \put(7.00,60.48){\line(0,1){3.00}} \put(13.18,60.48){\line(0,1){3.00}} \put(7.00,50.48){\line(0,1){3.00}} \put(13.18,50.48){\line(0,1){3.00}} \put(1.00,72.00){\makebox(0,0)[cc]{{\footnotesize A}}} \put(1.00,62.00){\makebox(0,0)[cc]{{\footnotesize B}}} \put(1.00,52.00){\makebox(0,0)[cc]{{\footnotesize C}}} \put(1.00,42.00){\makebox(0,0)[cc]{{\footnotesize D}}} \put(7.00,51.45){\rule{6.00\unitlength}{1.00\unitlength}} \put(12.85,70.52){\line(0,1){3.00}} \put(13.00,71.53){\rule{6.00\unitlength}{1.00\unitlength}} \put(7.00,61.57){\rule{6.00\unitlength}{1.00\unitlength}} \put(76.13,50.52){\line(0,1){3.00}} \put(63.96,60.52){\line(0,1){3.00}} \put(64.01,50.52){\line(0,1){3.00}} \put(64.00,61.53){\rule{12.00\unitlength}{1.00\unitlength}} \put(64.00,51.53){\rule{12.00\unitlength}{1.00\unitlength}} \put(121.00,16.62){\rule{18.00\unitlength}{1.00\unitlength}} \put(82.04,72.00){\circle*{2.00}} \put(88.01,70.52){\line(0,1){3.00}} \put(75.86,70.52){\line(0,1){3.00}} \put(76.00,71.53){\rule{12.00\unitlength}{1.00\unitlength}} \put(55.96,42.00){\circle*{2.00}} \put(62.01,40.52){\line(0,1){3.00}} \put(50.01,40.52){\line(0,1){3.00}} \put(50.00,41.53){\rule{12.00\unitlength}{1.00\unitlength}} \put(76.00,27.00){\circle*{2.00}} \put(59.96,36.00){\circle*{2.00}} \put(66.01,34.52){\line(0,1){3.00}} \put(54.01,34.52){\line(0,1){3.00}} \put(54.00,35.53){\rule{12.00\unitlength}{1.00\unitlength}} \put(70.04,17.00){\circle*{2.00}} \put(76.13,15.52){\line(0,1){3.00}} \put(63.96,15.52){\line(0,1){3.00}} \put(64.00,16.53){\rule{12.00\unitlength}{1.00\unitlength}} \put(64.00,58.00){\line(0,-1){1.00}} \put(64.00,56.00){\line(0,-1){1.00}} \put(64.00,54.00){\line(0,-1){1.00}} \put(64.00,52.00){\line(0,-1){1.00}} \put(64.00,50.00){\line(0,-1){1.00}} \put(64.00,48.00){\line(0,-1){1.00}} \put(64.00,46.00){\line(0,-1){1.00}} \put(64.00,36.00){\line(0,-1){1.00}} \put(64.00,34.00){\line(0,-1){1.00}} \put(64.00,32.00){\line(0,-1){1.00}} \put(64.00,30.00){\line(0,-1){1.00}} \put(64.00,28.00){\line(0,-1){1.00}} \put(64.00,26.00){\line(0,-1){1.00}} \put(64.00,60.00){\line(0,-1){1.00}} \put(82.00,74.00){\makebox(0,0)[cb]{{\tiny A at A,B,C}}} \put(70.00,64.00){\makebox(0,0)[cb]{{\tiny B at A,B,C}}} \put(70.00,54.00){\makebox(0,0)[cb]{{\tiny C at A,B,C}}} \put(56.00,44.00){\makebox(0,0)[cb]{{\tiny D at A}}} \put(60.00,38.00){\makebox(0,0)[cb]{{\tiny D at B,C}}} \put(79.00,27.00){\makebox(0,0)[lc]{{\footnotesize $\B{C}_A(t_1)$}}} \put(79.00,17.00){\makebox(0,0)[lc]{{\footnotesize $\B{C}_{B}(t_1)$}}} \put(130.00,7.00){\circle*{2.00}} \put(139.18,5.67){\line(0,1){3.00}} \put(121.00,5.67){\line(0,1){3.00}} \put(121.00,6.62){\rule{18.00\unitlength}{1.00\unitlength}} \put(142.00,27.00){\circle*{2.00}} \put(145.03,25.52){\line(0,1){3.00}} \put(138.82,25.52){\line(0,1){3.00}} \put(139.00,26.53){\rule{6.00\unitlength}{1.00\unitlength}} \put(142.00,29.00){\makebox(0,0)[cb]{{\tiny A at A,B,C}}} \put(130.00,19.00){\makebox(0,0)[cb]{{\tiny B at A,B,C}}} \put(130.00,9.00){\makebox(0,0)[cb]{{\tiny C at A,B,C}}} \put(112.96,37.00){\circle*{2.00}} \put(119.01,35.52){\line(0,1){3.00}} \put(107.01,35.52){\line(0,1){3.00}} \put(107.00,36.53){\rule{12.00\unitlength}{1.00\unitlength}} \put(116.96,31.00){\circle*{2.00}} \put(123.01,29.52){\line(0,1){3.00}} \put(110.89,29.52){\line(0,1){3.00}} \put(111.00,30.53){\rule{12.00\unitlength}{1.00\unitlength}} \put(113.00,39.00){\makebox(0,0)[cb]{{\tiny D at A}}} \put(117.00,33.00){\makebox(0,0)[cb]{{\tiny D at B,C}}} \put(136.11,77.00){\circle*{2.00}} \put(142.00,77.00){\makebox(0,0)[lc]{{\footnotesize $\B{C}_A(t_2)$}}} \put(130.00,57.00){\circle*{2.00}} \put(121.00,55.67){\line(0,1){3.00}} \put(121.00,56.62){\rule{18.00\unitlength}{1.00\unitlength}} \put(121.00,54.00){\line(0,-1){1.00}} \put(121.00,52.00){\line(0,-1){1.00}} \put(121.00,50.00){\line(0,-1){1.00}} \put(121.00,48.00){\line(0,-1){1.00}} \put(121.00,46.00){\line(0,-1){1.00}} \put(121.00,43.00){\line(0,1){1.00}} \put(121.00,42.00){\line(0,-1){1.00}} \put(121.00,40.00){\line(0,-1){1.00}} \put(121.00,38.00){\line(0,-1){1.00}} \put(121.00,36.00){\line(0,-1){1.00}} \put(121.00,32.00){\line(0,-1){1.00}} \put(121.00,30.00){\line(0,-1){1.00}} \put(121.00,28.00){\line(0,-1){1.00}} \put(121.00,26.00){\line(0,-1){1.00}} \put(121.00,24.00){\line(0,-1){1.00}} \put(121.00,22.00){\line(0,-1){1.00}} \put(121.00,20.00){\line(0,-1){1.00}} \put(121.00,18.00){\line(0,-1){1.00}} \put(121.00,16.00){\line(0,-1){1.00}} \put(121.00,13.00){\line(0,-1){1.00}} \put(121.00,11.00){\line(0,-1){1.00}} \put(142.00,57.00){\makebox(0,0)[lc]{{\footnotesize $\B{C}_{C}(t_2)$}}} \put(133.00,54.00){\line(0,1){24.00}} \put(133.00,82.00){\makebox(0,0)[cb]{{\footnotesize $\tau_2$}}} \put(73.00,1.00){\makebox(0,0)[ct]{{\footnotesize $\tau_1$}}} \put(13.00,78.00){\line(0,-1){33.00}} \put(75.80,25.52){\line(0,1){3.00}} \put(76.22,25.52){\line(0,1){3.00}} \put(138.80,75.52){\line(0,1){3.00}} \put(139.23,75.52){\line(0,1){3.00}} \put(139.00,77.00){\vector(-1,0){2.02}} \put(139.23,55.67){\line(0,1){3.00}} \put(139.18,15.67){\line(0,1){3.00}} \put(136.00,50.00){\line(0,-1){1.00}} \put(136.00,48.00){\line(0,-1){1.00}} \put(136.00,46.00){\line(0,-1){1.00}} \put(136.00,44.00){\line(0,-1){1.00}} \put(136.00,42.00){\line(0,-1){1.00}} \put(136.00,39.00){\line(0,1){1.00}} \put(136.00,38.00){\line(0,-1){1.00}} \put(136.00,36.00){\line(0,-1){1.00}} \put(136.00,34.00){\line(0,-1){1.00}} \put(136.00,32.00){\line(0,-1){1.00}} \put(136.00,30.00){\line(0,-1){1.00}} \put(136.00,28.00){\line(0,-1){1.00}} \put(136.00,26.00){\line(0,-1){1.00}} \put(136.00,24.00){\line(0,-1){1.00}} \put(136.00,22.00){\line(0,-1){1.00}} \put(136.00,72.00){\line(0,-1){1.00}} \put(136.00,70.00){\line(0,-1){1.00}} \put(136.00,68.00){\line(0,-1){1.00}} \put(136.00,66.00){\line(0,-1){1.00}} \put(136.00,64.00){\line(0,-1){1.00}} \put(136.00,61.00){\line(0,1){1.00}} \put(136.00,60.00){\line(0,-1){1.00}} \put(136.00,58.00){\line(0,-1){1.00}} \put(136.00,56.00){\line(0,-1){1.00}} \put(136.00,54.00){\line(0,-1){1.00}} \put(136.00,52.00){\line(0,-1){1.00}} \put(144.95,26.50){\dashbox{1.00}(3.00,1.00)[cc]{}} \put(136.00,26.50){\dashbox{1.00}(3.00,1.00)[cc]{}} \put(135.84,25.52){\line(0,1){3.00}} \put(147.96,25.52){\line(0,1){3.00}} \put(148.00,24.00){\line(0,-1){1.00}} \put(148.00,22.00){\line(0,-1){1.00}} \put(142.00,22.00){\vector(-1,0){5.97}} \put(142.00,22.00){\vector(1,0){5.97}} \put(142.00,23.00){\makebox(0,0)[cb]{{\tiny $\pi^H$}}} \put(152.00,91.00){\makebox(0,0)[cb]{{\footnotesize $t$}}} \put(7.00,87.00){\line(0,1){2.00}} \put(10.00,87.00){\line(0,1){2.00}} \put(13.00,87.00){\line(0,1){2.00}} \put(16.00,87.00){\line(0,1){2.00}} \put(19.00,87.00){\line(0,1){2.00}} \put(64.00,87.00){\line(0,1){2.00}} \put(67.00,87.00){\line(0,1){2.00}} \put(70.00,87.00){\line(0,1){2.00}} \put(73.00,87.00){\line(0,1){2.00}} \put(76.00,87.00){\line(0,1){2.00}} \put(79.00,87.00){\line(0,1){2.00}} \put(82.00,87.00){\line(0,1){2.00}} \put(85.00,87.00){\line(0,1){2.00}} \put(88.00,87.00){\line(0,1){2.00}} \put(121.00,87.00){\line(0,1){2.00}} \put(124.00,87.00){\line(0,1){2.00}} \put(127.00,87.00){\line(0,1){2.00}} \put(130.00,87.00){\line(0,1){2.00}} \put(133.00,87.00){\line(0,1){2.00}} \put(136.00,87.00){\line(0,1){2.00}} \put(139.00,87.00){\line(0,1){2.00}} \put(142.00,87.00){\line(0,1){2.00}} \put(145.00,87.00){\line(0,1){2.00}} \put(148.00,87.00){\line(0,1){2.00}} \put(22.00,72.00){\makebox(0,0)[lc]{{\footnotesize $\B{C}_A(t_0)$}}} \put(22.00,62.00){\makebox(0,0)[lc]{{\footnotesize $\B{C}_{B}(t_0)$}}} \put(22.00,52.00){\makebox(0,0)[lc]{{\footnotesize $\B{C}_{C}(t_0)$}}} \put(76.00,42.00){\line(0,-1){1.00}} \put(76.00,42.00){\vector(0,-1){1.00}} \put(121.00,43.00){\vector(0,1){1.00}} \put(139.00,43.00){\vector(0,1){1.00}} \put(22.00,42.00){\makebox(0,0)[lc]{{\footnotesize $\B{C}_{D}$ faulty}}} \put(70.04,7.00){\circle*{2.00}} \put(76.13,5.52){\line(0,1){3.00}} \put(63.96,5.52){\line(0,1){3.00}} \put(64.00,6.53){\rule{12.00\unitlength}{1.00\unitlength}} \put(79.00,7.00){\makebox(0,0)[lc]{{\footnotesize $\B{C}_{C}(t_1)$}}} \put(73.00,4.00){\line(0,1){25.00}} \put(64.00,24.00){\line(0,-1){1.00}} \put(64.00,22.00){\line(0,-1){1.00}} \put(64.00,20.00){\line(0,-1){1.00}} \put(64.00,18.00){\line(0,-1){1.00}} \put(64.00,16.00){\line(0,-1){1.00}} \put(64.00,14.00){\line(0,-1){1.00}} \put(64.00,12.00){\line(0,-1){1.00}} \put(64.00,10.00){\line(0,-1){1.00}} \put(64.00,8.00){\line(0,-1){1.00}} \put(64.00,6.00){\line(0,-1){1.00}} \put(76.00,78.00){\line(0,-1){74.00}} \put(64.00,44.00){\line(0,-1){1.00}} \put(79.00,37.00){\makebox(0,0)[lc]{{\footnotesize $\B{C}_{D}$ faulty}}} \put(130.00,67.00){\circle*{2.00}} \put(121.00,65.67){\line(0,1){3.00}} \put(121.00,66.62){\rule{18.00\unitlength}{1.00\unitlength}} \put(142.00,67.00){\makebox(0,0)[lc]{{\footnotesize $\B{C}_{B}(t_2)$}}} \put(139.23,65.67){\line(0,1){3.00}} \put(136.00,76.00){\line(0,-1){1.00}} \put(136.00,74.00){\line(0,-1){1.00}} \put(121.00,65.00){\line(0,-1){1.00}} \put(121.00,63.00){\line(0,-1){1.00}} \put(121.00,61.00){\line(0,-1){1.00}} \put(64.00,41.00){\vector(0,-1){0.01}} \put(64.00,41.00){\line(0,-1){1.00}} \put(139.00,31.00){\line(0,1){47.00}} \put(139.00,28.00){\line(0,-1){24.00}} \put(0.00,88.00){\vector(1,0){153.00}} \put(44.00,72.00){\line(1,0){1.00}} \put(46.00,72.00){\line(1,0){1.00}} \put(48.00,72.00){\line(1,0){1.00}} \put(50.00,72.00){\line(1,0){1.00}} \put(52.00,72.00){\line(1,0){1.00}} \put(54.00,72.00){\line(1,0){1.00}} \put(56.00,72.00){\line(1,0){1.00}} \put(58.00,72.00){\line(1,0){1.00}} \put(60.00,72.00){\line(1,0){1.00}} \put(62.00,72.00){\line(1,0){1.00}} \put(64.00,72.00){\line(1,0){1.00}} \put(66.00,72.00){\line(1,0){1.00}} \put(68.00,72.00){\line(1,0){1.00}} \put(70.00,72.00){\line(1,0){1.00}} \put(72.00,72.00){\vector(1,0){1.00}} \put(44.00,62.00){\line(1,0){1.00}} \put(46.00,62.00){\line(1,0){1.00}} \put(48.00,62.00){\line(1,0){1.00}} \put(50.00,62.00){\line(1,0){1.00}} \put(52.00,62.00){\line(1,0){1.00}} \put(54.00,62.00){\line(1,0){1.00}} \put(56.00,62.00){\line(1,0){1.00}} \put(58.00,62.00){\line(1,0){1.00}} \put(60.00,62.00){\vector(1,0){1.00}} \put(44.00,52.00){\line(1,0){1.00}} \put(46.00,52.00){\line(1,0){1.00}} \put(48.00,52.00){\line(1,0){1.00}} \put(50.00,52.00){\line(1,0){1.00}} \put(52.00,52.00){\line(1,0){1.00}} \put(54.00,52.00){\line(1,0){1.00}} \put(56.00,52.00){\line(1,0){1.00}} \put(58.00,52.00){\line(1,0){1.00}} \put(60.00,52.00){\vector(1,0){1.00}} \put(44.00,42.00){\line(1,0){1.00}} \put(46.00,42.00){\vector(1,0){1.00}} \put(101.00,17.00){\line(1,0){1.00}} \put(103.00,17.00){\line(1,0){1.00}} \put(105.00,17.00){\line(1,0){1.00}} \put(107.00,17.00){\line(1,0){1.00}} \put(109.00,17.00){\line(1,0){1.00}} \put(111.00,17.00){\line(1,0){1.00}} \put(113.00,17.00){\line(1,0){1.00}} \put(115.00,17.00){\line(1,0){1.00}} \put(117.00,17.00){\vector(1,0){1.00}} \put(101.00,7.00){\line(1,0){1.00}} \put(103.00,7.00){\line(1,0){1.00}} \put(105.00,7.00){\line(1,0){1.00}} \put(107.00,7.00){\line(1,0){1.00}} \put(109.00,7.00){\line(1,0){1.00}} \put(111.00,7.00){\line(1,0){1.00}} \put(113.00,7.00){\line(1,0){1.00}} \put(115.00,7.00){\line(1,0){1.00}} \put(117.00,7.00){\vector(1,0){1.00}} \put(103.00,27.00){\line(1,0){1.00}} \put(105.00,27.00){\line(1,0){1.00}} \put(107.00,27.00){\line(1,0){1.00}} \put(109.00,27.00){\line(1,0){1.00}} \put(111.00,27.00){\line(1,0){1.00}} \put(113.00,27.00){\line(1,0){1.00}} \put(115.00,27.00){\line(1,0){1.00}} \put(117.00,27.00){\line(1,0){1.00}} \put(119.00,27.00){\line(1,0){1.00}} \put(123.00,27.00){\line(1,0){1.00}} \put(125.00,27.00){\line(1,0){1.00}} \put(127.00,27.00){\line(1,0){1.00}} \put(129.00,27.00){\line(1,0){1.00}} \put(131.00,27.00){\line(1,0){1.00}} \put(133.00,27.00){\vector(1,0){1.00}} \put(121.00,27.00){\line(1,0){1.00}} \put(101.00,27.00){\line(1,0){1.00}} \put(101.00,37.00){\line(1,0){1.00}} \put(103.00,37.00){\vector(1,0){1.00}} \end{picture} \end{center} \caption{\em Example of a reference point setting outside the accuracy interval at $t_2$. The accuracy interval $\protect\B{C}_A(t_2)$ computed by applying $\protect\M_4^3$ to the received intervals does not contain the reference point computed as the centerpoint of $\protect\M_4^3$ applied to the associated $\protect\B{\pi}^H$-precision intervals.} \label{fig:accprec} \end{figure} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% At $t_1$, applying $\M_4^3$ to the received accuracy intervals respectively the associated $\B{\pi}^H$-precision intervals (which satisfy $\B{C}_q^p(t_1)=\ppI{\B{C}}_q^p(t_1)$ for $p, q\in\{A,B,C\}$ here) yields $\B{C}_A(t_1)=[t_1\pm\B{\textstyle 0}]$ and $\B{C}_B(t_1)=\B{C}_C(t_1)=[t_1-2\pm\B{2}]$ at the respective nodes; recall that the reference point of $\B{C}_q$ is computed as the centerpoint of $\M$ applied to the $\ppI{\B{C}}_q^p$'s. In order to ensure $\B{\pi}_0$-correctness of clock~A and~B, internal global time $\tau_1$ must be set to $t_1-1$ to lie in the intersection of the renewed $\B{\pi}_0$-precision intervals. Although $\tau_1$ does not lie in $\B{C}_A(t_1)$, this situation is still feasible due to the fact that we decoupled precision and accuracy in the definition of $\B{\pi}$-precision intervals. However, the problem shows up when setting the reference point of clock~A at $t_2$: Applying $\M$ to the received accuracy intervals at A provides $[t_2\pm\B{0}]$, but the reference point evaluates to $t_2-1$, which lies outside. If we ignored this, that is, if we set the reference point to $t_2$, precision would be violated. Therefore, $[t_2\pm\B{0}]$ must be enlarged to the left by 1 to include the reference point. Note also that internal global time $\tau_2$ must be set to $t_2-2$ here. Viewed from a different angle, this problem can be seen as a consequence of the fact that internal global time may drift away from real-time. In Figure~\ref{fig:accprec}, it is node~$D$'s faulty behavior that slows down the overall progress of internal global time relative to real-time. For that reason, we eventually decoupled accuracy and precision in Definition~\ref{def:ivprec}, viewing them as {\em orthogonal\/} issues. %Note that our first approach in %\cite{SS97:1} limited $\B{\pi}$-precision intervals to subintervals %of the accuracy interval (that is, defined $\ppI{\B{I}}=[r\pm\B{\pi}]\cap \B{I}$ %for $\B{I}=[r\pm\B{\alpha}]$), but our example shows that this could %produce empty\footnote{A remedy would be padding any accuracy %interval $\B{R}=[r\pm\B{\alpha}]$ to enforce the %condition $\B{\pi}\subseteq\B{\alpha}$, such that $\tau_1\in %\B{C}_A(t_1)$ in Figure~\ref{fig:accprec} could also be guaranteed. %However, this approach spoils accuracy more than the eventually %chosen enlargement ``on demand'' does.} precision intervals. Note that orthogonality actually opens up the possibility of employing virtually any internal synchronization algorithm for maintaining precision, and to enlarge accuracy as needed, see Remark~3 on Theorem~\ref{thm:convOAacc}. We should add that a similar approach was taken for the adaptive intersection algorithm of NTP (\cite{Mil95}), which is also based upon $\M$. Besides trying to dynamically figure out a reasonable $f$ (thereby sacrificing guaranteed accurateness), it extends the resulting interval appropriately to include the reference points of all apparently non-faulty input intervals. This way, it is guaranteed that the final reference point (computed according to maximum likelihood principles) lies within the final accuracy interval. In order to formalize our orthogonal accuracy convergence function, we first have to introduce a discrete, asymmetric reference point setting operation $\mbox{$\B{\pi}$-center}_{G_S}$. It is a generalization of centerpoint setting, which partitions an interval according to the proportion of $\pi^-:\pi^+$ while accounting for the fact that the CPU used for computing the reference point has integer arithmetic only: According to Definition~\ref{def:OAalgorithm} in Appendix~B, we require all quantities manipulated by our clock synchronization algorithm to be integer