\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 multiples of the {\em
clock-setting granularity\/} $G_S>0$. Therefore, an integer division
(rather than an exact one) is employed in
$\mbox{$\B{\pi}$-center}_{G_S}$, so that the analysis must deal with
the truncation error.
Unfortunately, we cannot simply use exact (= non-discrete) reference
point setting plus a remainder term ${\cal O}(G_S)$ in our analysis.
Since we are aiming at hardware-assisted clock synchronization with worst
case accuracy and precision in the $\mu$s-range and below, see
\cite{SKMNCK99}, this simplification would spoil the very accurate
generic analysis of \cite{SS97:1}: Although $G_S$ is smaller than
clock granularity $G$ for most adjustable clock implementations, it
is nevertheless much larger than the ${\cal O}(\cdot)$-terms
present in the results of \cite{SS97:1}, see Remark~1 on
Theorem~\ref{thm:precOA}. Therefore, we have to
take the trouble of tracking the truncation errors explicitly.
\begin{defin}[Discrete Reference Point Setting]\label{def:refset}
Let an interval $\B{I}=[a,b]$ with $a$, $b$ being integer
multiples of $G_S>0$ and some arbitrary $\B{\pi}=[-\pi^-,\pi^+]$
satisfying $\pi=\pi^-+\pi^+>0$ be given. With $\lfloor x
\rfloor_{G_S}$ denoting truncation of $x$ to the next integer
multiple of $G_S$ being $\leq x$,
and $\lceil x \rceil_{G_S}$
denoting rounding up $x$ to the next integer
multiple of $G_S$ being $\geq x$, we define
\begin{equation}
\mbox{$\B{\pi}$-center}_{G_S}(\B{I}) = \Bigl\lfloor \frac{\pi^-b
+ \pi^+a}{\pi}\Bigr\rfloor_{G_S}.\label{equ:defcent}
\end{equation}
\end{defin}
A few technical lemmas dealing with the properties of
$\mbox{$\B{\pi}$-center}_{G_S}$ are provided in
Appendix~A.
Now we are ready for the formal definition of the orthogonal accuracy
convergence function $\OA$. Basically, the result of ${\OA}$ is the
interval provided by ${\M}$ applied to the accuracy intervals of the
input set $\B{\cal J}$, possibly extended appropriately to include
the reference point. The latter is computed independently
(``orthogonally'') as the $\mbox{$\B{\pi}^H$-center}_{G_S}$ of the
interval obtained by applying ${\M}$ to the associated
$\B{\pi}^H$-precision intervals in the input set $\ppI{\B{\cal J}}$.
\begin{defin}[Convergence Function ${\OA}$]\label{def:OA}
Let $\B{\cal I}$ be a set of $n$ compatible accuracy intervals
and $\B{\cal J}\subseteq\B{\cal I}$ with $|\B{\cal J}|=n'\leq n$ be the set
of non-empty intervals among them. With $\ppI{\B{\cal
J}}$ denoting the set of associated $\B{\pi}^H$-precision intervals for
some given $\B{\pi}^H$ with $\pi^{H-}$, $\pi^{H+}$ being integer multiples
of $G_S$, and $f$ denoting a given fault-tolerance parameter, the
{\em orthogonal accuracy convergence function\/}
$\OA^{\B{\pi}^H}_{n-f}(\B{\cal J})$ (abbreviated by $\OA$) is defined by
\begin{eqnarray}
\mbox{ref}\bigl({\OA}(\B{\cal J})\bigr)
&=& \mbox{$\B{\pi}^H$-center}_{G_S}\bigl({
\M}_{n'}^{n-f}(\ppI{\B{\cal J}})\bigr)\quad\mbox{and}\label{equ:centerOA}\\
{\OA}(\B{\cal J}) &=& {\M}_{n'}^{n-f}(\B{\cal J})
\cup \mbox{ref}\bigl({\OA}(\B{\cal J})\bigr).\label{equ:accurOA}
\end{eqnarray}
\end{defin}
In order to analyze the performance of the interval-based clock
synchronization algorithm of Definition~\ref{def:OAalgorithm}
employing $\OA$, it is sufficient to evaluate the characteristic
functions of $\OA$ according to Definition~\ref{def:charconv}.
Plugging those into the generic results of \cite{SS97:1}, as done in
Section~\ref{Orthogonal Accuracy Algorithm}, the final expressions
for precision, accuracy, etc.\ follow immediately. To improve
readability, we provide $\OA$'s characteristic functions via
two theorems: All precision-related results can be found in
Theorem~\ref{thm:convOAprec}, whereas the more complicated
derivations for accuracy-related quantities are covered by
Theorem~\ref{thm:convOAacc}.
Theorem~\ref{thm:convOAprec} states how $\OA$ affects
precision. It determines, for any pair of nodes~$p$ and~$q$,
(1) how the application of $\OA$ affects precision in the
current round, and (2) what precision is obtained at the
beginning of the next round. As an input, our theorem takes [1]
a bound $\B{\pi}^H$ on the precision of all non-faulty input
intervals, and [2] the maximum ``difference'' $\B{\pi}_I$ of the
intervals received from a single non-faulty sender~$s$ at node~$p$
respectively $q$. We particularly emphasize the quite simple proof of
Theorem~\ref{thm:convOAprec}, which can be attributed to the power of
our generic analysis based upon internal global time.
\begin{thm}[Precision $\OA$]\label{thm:convOAprec}
Let $\B{\cal I}_p=\{\B{I}_p^1,\dots,\B{I}_p^n\}$, $\B{\cal
I}_q=\{\B{I}_q^1,\dots,\B{I}_q^n\}$ be two ordered sets of $n$
compatible accuracy intervals (all representing the \underbar{same}
real-time~$t$) obtained at nodes~$p$ respectively $q$ at the end of a
round, which are in accordance with the fault model of
Assumption~\ref{asum:faultmodel}. Moreover, let the subsets of
non-empty accuracy intervals among them be $\B{\cal
J}_p\subseteq\B{\cal I}_p$, $|\B{\cal J}_p|=n_p\leq n$ and $\B{\cal
J}_q\subseteq\B{\cal I}_q$, $|\B{\cal J}_q|=n_q\leq n$ and
assume that
\begin{itemize}
\item[{[1]}] any non-faulty $\B{I}_p^i\in\B{\cal I}_p$ as well as any
non-faulty $\B{I}_q^i\in \B{\cal I}_q$ is $\B{\pi}^H$-correct for
some given $\B{\pi}^H$ with $\pi^{H+}$, $\pi^{H-}$ being integer
multiples of $G_S$,
\item[{[2]}] any pair of non-faulty intervals $\{\B{I}_p^i$, $\B{I}_q^i\}$
is $\B{\pi}_I$-precise for some given $\B{\pi}_I\subseteq\B{\pi}^H$,
where $\pi_I$ is an integer multiple of $G_S$ with
$\zeta=(\pi^H-\pi_I)\min\{\pi^{H-}, \pi^{H+}\}/\pi^H > G_S$.
\end{itemize}
The convergence function $\OA^{\B{\pi}^H}_{n-\d-\e}$ applied to
$\B{\cal J}_p$ respectively $\B{\cal J}_q$ at node $p$
respectively $q$
is translation invariant and provides
intervals $\B{R}_p=\OA(\B{\cal J}_p)=[T_p'\pm\B{\alpha}_p']$ respectively
$\B{R}_q=\OA(\B{\cal J}_q)=[T_q'\pm\B{\alpha}_q']$ with reference
points being integer multiples of $G_S$. Its precision-related
characteristic functions, which are monotonic with
respect to any interval argument as long as $\pi^{H-}/\pi^H$
remains invariant, are as follows:
\begin{itemize}
\item[(1)] The {\em precision preservation function\/}
$\B{\Phi}(\cdot)$, which ensures that
$\B{R}_p$ and $\B{R}_q$ are $\B{\Phi}(\B{\pi}^H)$-correct,
is
\begin{equation}
\B{\Phi}(\B{\pi}^H)=\B{\pi}^H\label{equ:prpresf}.
\end{equation}
\item[(2)] The {\em precision enhancement function\/}
$\Pi(\cdot)$, which ensures that the set $\{\B{R}_p,\B{R}_q\}$
is $\B{\pi}_0$-precise with
$\pi_0=\Pi(\B{\pi}^H,\B{\pi}_I)<\pi^H$,
evaluates to
\begin{equation}
\Pi(\B{\pi}^H,\B{\pi}_I)=\max\Bigl\{\Bigl\lceil\pi^{H+}+\frac{\pi^{H-}}{\pi^H}\pi_I\Bigr\rceil_{G_S},
\Bigl\lceil\pi^{H-}+\frac{\pi^{H+}}{\pi^H}\pi_I\Bigr\rceil_{G_S}\Bigr\}\label{equ:OAprecenhs}.
\end{equation}
\end{itemize}
\end{thm}
\noindent
{\bf Proof\,}
>From Definition~\ref{def:OA} of ${\OA}$, it is immediately apparent
that $\OA$ is translation invariant since $\M$ is. Moreover,
the reference point of $\B{R}_p=\OA(\B{\cal J}_p)$ respectively
$\B{R}_q=\OA(\B{\cal J}_q)$ is determined by applying ${\M}$
to the $\B{\pi}^H$-precision intervals associated
with $\B{I}_p^i\in\B{\cal J}_p$ respectively $\B{I}_q^i\in\B{\cal J}_q$,
resulting in
\[
\pB{R}_p={\M}_{n_p}^{n-\d-\e}(\ppI{\B{\cal J}_p})\qquad\mbox{and}\qquad
\pB{R}_q={\M}_{n_q}^{n-\d-\e}(\ppI{\B{\cal J}_q}).
\]
Since any non-faulty $\B{I}_p^i$ is
$\B{\pi}^H$-correct according to precondition~[1], it is guaranteed that
$\ppI{\B{I}}_p^i$ contains internal global
time $\tau$, and that $|\ppI{\B{I}}_p^i|\leq\pi^H$, so
that any intersection of such intervals has these properties as well.
Lemma~\ref{lem:accM} applies with $n:=n_p$ and $f:=\d+\e-(n-n_p)$, hence
it follows that $\tau\in\pB{R}_p$ by its item~(1)
and $|\pB{R}_p|\leq\pi^H$ by its item~(2) since
\begin{equation}
n_p-2f-\a' \geq n - 2\d -3\e +n -n_p \geq n -2\d
-3\e \geq 1,\label{equ:newy}
\end{equation}
recall Assumption~\ref{asum:faultmodel}. Since $\OA$ sets the
reference point~$T_p'$ of $\pB{R}_p=[T_p'\pm\B{\pi}_p]$ to
$\mbox{$\B{\pi}^H$-center}_{G_S}(\pB{R}_p)$, applying
Lemma~\ref{lem:accrefset} provided in Appendix~A yields
\[
\pi_p^- =
\Bigl\lfloor\frac{\pi^{H-}}{\pi^H}|\pB{R}_p|\Bigr\rfloor_{G_S} \leq
\frac{\pi^{H-}}{\pi^H}|\pB{R}_p| \leq \pi^{H-}
\]
and
\[
\pi_p^+ =
\Bigl\lceil\frac{\pi^{H+}}{\pi^H}|\pB{R}_p|\Bigr\rceil_{G_S} \leq
\Bigl\lceil\frac{\pi^{H+}}{\pi^H}\pi^H\Bigr\rceil_{G_S} = \pi^{H+};
\]
recall that $\pi^{H+}$ was assumed to be an integer multiple of
$G_S$. Since $\mbox{ref}(\B{R}_p)=\mbox{ref}(\pB{R}_p)$,
the asserted $\B{\pi}^H$-correctness of $\B{R}_p$ and hence
expression (\ref{equ:prpresf}) for $\B{\Phi}(\cdot)$ follows. The
required monotonicity of $\B{\Phi}(\B{\pi}^H)$ with respect to
$\B{\pi}^H$ is immediately apparent.
Of course, exactly the same reasoning holds for $\B{R}_q$, completing
the proof of item~(1).
As far as item~(2) is concerned, we first recall that
any pair of $\B{\pi}^H$-correct intervals $\B{I}_p^i\in\B{\cal J}_p$
and $\B{I}_q^i\in\B{\cal J}_q$ was assumed to be $\B{\pi}_I$-precise
in precondition [2]. Hence it follows that
$|\ppI{\B{I}}_p^i\nccup\ppI{\B{I}}_q^i|\leq \pi^H+\pi_I$, since
$|\ppI{\B{I}}_p^i|,|\ppI{\B{I}}_q^i|\leq \pi^H$ and
$|\mbox{ref}(\B{I}_p^i)-\mbox{ref}(\B{I}_q^i)|\leq\pi_I$ by item~(2) of
Lemma~\ref{lem:corpiprec}. This implies
$|\pB{R}_p\nccup\pB{R}_q|\leq\pi^H+\pi_I$ due to
$\pB{R}_p\nccup\pB{R}_q \subseteq \bigcap_{k=1}^{n-2\d-3\e}
\ppI{\B{I}}^{i_k}_p \nccup \ppI{\B{I}}^{i_k}_q$, recall item~(2) of
Lemma~\ref{lem:degradeM} and (\ref{equ:newy}).
Now we can apply Lemma~\ref{lem:precenh} provided in
Appendix~A with
$\pi_p=\pi_q=\opi_p=\opi_q:=\pi^H$ and $\pi:=\pi^H+\pi_I$,
which eventually yields $|\mbox{ref}(\B{R}_p)-\mbox{ref}(\B{R}_q)|
=|\mbox{ref}(\pB{R}_p)-\mbox{ref}(\pB{R}_q)|
\leq\Pi(\B{\pi}^H,\B{\pi}_I)$ as given by (\ref{equ:OAprecenhs}).
This ensures $\B{\pi}_0$-precision for any
%
%\footnote{Note that {\em any\/}
%would not be true if we had defined $\B{\pi}$-precision intervals as
%subintervals of the accuracy interval, see the comments following
%XXXXX.}
%
$\B{\pi}_0$ with $|\B{\pi}_0|=\pi_0$ as asserted.
The required relation $\pi_0<\pi^H$ is verified via
\[
\pi_0 - G_S \leq \max\Bigl\{\pi^{H+} + \frac{\pi^{H-}}{\pi^H}\pi_I,
\pi^{H-} + \frac{\pi^{H+}}{\pi^H}\pi_I\Bigr\} =
\pi^H- \zeta < \pi^H-G_S,
\]
which follows from (\ref{equ:OAprecenhs}) and the condition imposed
on $\pi_I$ in precondition~[2] of our theorem.
Finally, the required monotonicity of $\Pi(\B{\pi}^H,\B{\pi}_I)$
with respect to $\B{\pi}^H$ and $\B{\pi}_I$ is obvious from
(\ref{equ:OAprecenhs}) by recalling that the potentially problematic
fractions ${\pi^{H-}}/{\pi^H}$ and ${\pi^{H+}}/{\pi^H}$ were
assumed to be invariant. This eventually completes the proof of
Theorem~\ref{thm:convOAprec}. $\Box$
\begin{rmm}
\pitem
The above theorem considers the most general case where
$|\pB{R}_p|$ and $|\pB{R}_q|$ may even be zero. A smaller $\Pi(\cdot)$
could be derived if a (reasonably large) non-zero lower bound on
$|\pB{R}_p|$ and $|\pB{R}_q|$ could be guaranteed.
\pitem
Observe that $\Pi(\B{\pi}^H,\B{\pi}_I)$ given in
(\ref{equ:OAprecenhs}) is minimized when
$\B{\pi}^H$ is symmetric, that is, when $\pi^{H+}=\pi^{H-}$. In that
case, we obtain
\[
\pi_0=\Bigl\lceil\frac{\pi^H+\pi_I}{2}\Bigr\rceil_{G_S} \leq
\frac{\pi^H+\pi_I}{2} + \frac{G_S}{2}.
\]
This gives the maximum {\em
precision enhancement\/} of our convergence function,
refer to \cite{Sch87}. The
convergence factor is $1/2$, which is the
same as provided by the well-known fault-tolerant midpoint (FTM)
convergence function, see \cite{LL88}.
\pitem
The fact that $\B{R}_p$ is $\B{\pi}^H$-correct easily provides
the {\em ``accuracy''\/} $\alpha$ of our convergence function
in the terminology of \cite{Sch87}, which gives the maximum
amount the computed clock value can differ from any non-faulty input
clock value. More specifically, since any non-faulty
input interval is $\B{\pi}^H$-correct, it follows
(see \cite[Lem.~7]{SS97:1})
that $|\alpha|\leq\pi^H$. Hence, ${\OA}$ provides the same
``accuracy'' as FTM and most other convergence functions, however,
with the notable exception of the optimal algorithms in
\cite{FC95:1} and \cite{Sch97:op}.
\end{rmm}
The following Theorem~\ref{thm:convOAacc} shows how $\OA$ affects
accuracy intervals, that is, the on-line bound on a node's maximum
deviation from real-time. As an input, it takes the same
precision-related quantities [1], [2] as
Theorem~\ref{thm:convOAprec}, the intersection of certain precision
intervals [3], and the accuracies of all non-faulty input intervals
[4]. Consult the discussion prior to Definition~\ref{def:charconv} in
Appendix~C for details.
\begin{thm}[Accuracy $\OA$]\label{thm:convOAacc}
Let $\B{\cal I}_p=\{\B{I}_p^1,\dots,\B{I}_p^n\}$, $\B{\cal
I}_q=\{\B{I}_q^1,\dots,\B{I}_q^n\}$ be two ordered sets of $n$
compatible accuracy intervals (all representing the \underbar{same}
real-time~$t$) obtained at nodes $p$ respectively $q$ at the end of a
round, which are in accordance with the fault model of
Assumption~\ref{asum:faultmodel}. Moreover, let the subsets of
non-empty accuracy intervals among them be $\B{\cal
J}_p\subseteq\B{\cal I}_p$, $|\B{\cal J}_p|=n_p\leq n$ and $\B{\cal
J}_q\subseteq\B{\cal I}_q$, $|\B{\cal J}_q|=n_q\leq n$ and
assume that
\begin{itemize}
\item[{[1]}] any non-faulty $\B{I}_p^i\in\B{\cal I}_p$ as well as any
non-faulty $\B{I}_q^i\in \B{\cal I}_q$ is $\B{\pi}^H$-correct for
some given $\B{\pi}^H$ with $\pi^{H+}$, $\pi^{H-}$ being integer
multiples of $G_S$,
\item[{[2]}] any pair of non-faulty intervals $\{\B{I}_p^i$, $\B{I}_q^i\}$
is $\B{\pi}_I$-precise for some given $\B{\pi}_I\subseteq\B{\pi}^H$,
where $\pi_I$ is an integer multiple of $G_S$ with
$\zeta=(\pi^H-\pi_I)\min\{\pi^{H-}, \pi^{H+}\}/\pi^H > G_S$,
\item[{[3]}] for any $s$ with both $\B{I}_p^s$ and $\B{I}_q^s$ being
non-faulty, the intersection of the associated precision
intervals $\ppI{\B{I}}_p^s \cap \ppI{\B{I}}_q^s \cap
\ppI{\B{I}}_p^{\min_p} \cap \ppI{\B{I}}_q^{\min_q}$ respectively
$\ppI{\B{I}}_p^s \cap \ppI{\B{I}}_q^s \cap \ppI{\B{I}}_p^{\max_p}
\cap \ppI{\B{I}}_q^{\max_q}$, where $\min_x$ respectively
$\max_x$ represents that non-faulty node that leads to the leftmost
$\mbox{right}(\ppI{\B{I}}_x^{\min_x})$ respectively the rightmost
$\mbox{left}(\ppI{\B{I}}_x^{\max_x})$ for $x\in\{p,q\}$, has length
at least $\iota_s^+\geq0$ respectively $\iota_s^-\geq0$ (integer multiples
of $G_S$),
\item[{[4]}] the accuracies of any non-faulty
$\B{I}_p^i=[T_p^{i}\pm\B{\alpha}_p^{i}]$ are integer multiples of
$G_S$ satisfying $\B{\alpha}_p^{i}\subseteq\B{\beta}_p^i\in\B{\cal
B}_p$ for a given set of accuracy bounds $\B{\cal
B}_p=\{\B{\beta}_p^1,\dots,\B{\beta}_p^n\}$ (and analogous for
$\B{I}_q^i$ with set of accuracy bounds $\B{\cal B}_q$).
%where
%$\B{\beta}_p^{i}=\B{\beta}_i + \B{\omega}_p^i$ with $\B{\beta}_i$
%respectively $\B{\omega}_p^i$ bounding node~$i$'s initial accuracy
%$\B{\alpha}_{i}$ (present at the beginning of the current round) respectively the
%enlargement $\B{\alpha}_p^i-\B{\alpha}_{i}$ experienced by $i$'s initial
%accuracy on its ``way'' to node~$p$,
\end{itemize}
The convergence function $\OA^{\B{\pi}^H}_{n-\d-\e}$ applied to
$\B{\cal J}_p$ respectively $\B{\cal
J}_q$ at node $p$ respectively $q$ provides accurate intervals
$\B{R}_p=\OA(\B{\cal J}_p)=[T_p'\pm\B{\alpha}_p']$ respectively
$\B{R}_q=\OA(\B{\cal J}_q)=[T_q'\pm\B{\alpha}_q']$ with
reference point and accuracies being integer multiples of $G_S$.
Its accuracy-related characteristic functions, which are
monotonic with respect to any interval argument as long as $\pi^{H-}/\pi^H$
remains invariant, are as follows:
\begin{itemize}
\item[(1)] The {\em conditional accuracy preservation functions\/}
$\aleph^-(\cdot)$, $\aleph^+(\cdot)$, which guarantee $\B{\alpha}_p'
\subseteq [-\aleph^-(\B{\cal B}_p,\B{\pi}^H,\forall s:\iota_s^-),
\aleph^+(\B{\cal
B}_p,\B{\pi}^H,\forall s:\iota_s^+)]$, read
\begin{eqnarray}
\aleph^-(\B{\cal B}_p,\B{\pi}^H,\forall s: \iota_s^-) &=&
\beta_p^{x,-} + \Bigl\lfloor\frac{\pi^{H+}}{\pi^H}(\pi^H-\iota_x^-)
\Bigr\rfloor_{G_S},\label{equ:fab}\\
\aleph^+(\B{\cal B}_p,\B{\pi}^H,\forall s: \iota_s^+) &=&
\beta_p^{x,+} + \Bigl\lceil\frac{\pi^{H-}}{\pi^H}(\pi^H-\iota_x^+)
\Bigr\rceil_{G_S},\label{equ:fabplu}
\end{eqnarray}
where $x$ denotes the node with the $n-2\d-3\e$-largest
accuracy bounds among $\B{\cal B}_p$, that is,
\[
\beta_p^{x,-} =
\max_{i:n-2\d-3\e}\{\beta_p^{i,-}\}
\quad\mbox{and}\quad
\beta_p^{x,+} =
\max_{i:n-2\d-3\e}\{\beta_p^{i,+}\}
\]
with
$\max_{i:m} \cal B$ denoting the $m$-th largest element of the
set ${\cal B}=\{\beta^i: 1\leq i \leq n\}$.
\item[(2)] The {\em conditional intersection enhancement functions\/}
$\Im^-(\cdot)$ respectively $\Im^+(\cdot)$, which ensure that the set
$\{\B{R}_p,\B{R}_q\}$ is $\B{\pi}_0^{\iota_{pq}^-}$-precise respectively
$\B{\pi}_0^{\iota_{pq}^+}$-precise with
$\pi_0^{\iota_{pq}^-} =
\Im^-(\B{\pi}^H,\B{\pi}_I)$ respectively
$\pi_0^{\iota_{pq}^+}=
\Im^+(\B{\pi}^H,\B{\pi}_I)$
for worst-case settings related to negative respectively
positive accuracy, evaluate to
\begin{equation}
\Im^-(\B{\pi}^H,\B{\pi}_I) =
\Bigl\lceil\frac{\pi^{H-}}{\pi^H}\pi_I\Bigr\rceil_{G_S}
\quad\mbox{respectively}\quad
\Im^+(\B{\pi}^H,\B{\pi}_I) =
\Bigl\lceil\frac{\pi^{H+}}{\pi^H}\pi_I\Bigr\rceil_{G_S}.
\label{equ:ims}
\end{equation}
\end{itemize}
\end{thm}
\noindent
{\bf Proof\,}
%Since ${\M}$ is obviously translation
%invariant and monotonic by item~(2) of Lemma~\ref{lem:monotonicityM},
%the same is true for ${\OA}$, at least if no enlargement due the
%inclusion of an excessive reference point occurs,
%cf.~(\ref{equ:accurOA}). However, we only have to establish weak
%monotonicity, where the reference points of the input intervals are
%assumed to be invariant (see \cite[Def.~10]{SS97:1}), hence enlargement
%does not cause problems either since it depends solely on the
%reference points.
>From Definition~\ref{def:OA}, it is evident that the accuracies
${\alpha'}_p^+$, ${\alpha'}_p^-$ in $\B{R}_p$ and ${\alpha'}_q^+$,
${\alpha'}_q^-$ in $\B{R}_q$ ---as well as their reference points---
are integer multiples of $G_S$. Finally, item~(1) of
Lemma~\ref{lem:accM} applied to (\ref{equ:accurOA}) makes sure that
$\B{R}_p$ and $\B{R}_q$ are accurate.
Therefore, it only remains to bound $\B{\alpha'}_p$ (without loss of
generality, since the analogous result for $\B{R}_q$ is obtained by
exchanging $p$ and $q$ in our theorem).
For that purpose, we need an arrangement of input
intervals that maximizes, say, the positive accuracy ${\alpha'}_p^+$ subject
to the given
lower bounds $\forall s: \iota_s^+$ on the intersection of certain
non-faulty input precision intervals.
Note that this worst-case scenario must
also cover situations where the reference point lies outside of the
accuracy interval, recall our considerations at the
beginning of this section.
Abbreviating the $n-2\d-3\e$-largest of $p$'s accuracy bounds
by $\beta=\max_{i:n-2\d-3\e}\{
\beta_p^{i+}\}$, the worst-case scenario for ${\alpha_p'}^+$ is depicted in
Figure~\ref{fig:accproof}. Note that we will provide the detailed
argument for ${\alpha'}_p^+$ only; ${\alpha'}_p^-$ is derived
analogously.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{figure}[htb]
\begin{center}
\unitlength=1.00mm
\special{em:linewidth 0.4pt}
\linethickness{0.4pt}
\begin{picture}(94.00,83.00)
\put(33.00,69.00){\circle*{2.00}}
\put(24.00,67.67){\line(0,1){3.00}}
\put(24.00,68.62){\rule{18.00\unitlength}{1.00\unitlength}}
\put(35.00,63.00){\circle*{2.00}}
\put(26.00,62.62){\rule{18.00\unitlength}{1.00\unitlength}}
\put(29.00,69.00){\line(-1,0){17.00}}
\put(31.00,63.00){\line(-1,0){17.00}}
\put(11.00,69.00){\line(-1,0){1.00}}
\put(9.00,69.00){\line(-1,0){1.00}}
\put(7.00,69.00){\line(-1,0){1.00}}
\put(13.00,63.00){\line(-1,0){1.00}}
\put(11.00,63.00){\line(-1,0){1.00}}
\put(9.00,63.00){\line(-1,0){1.00}}
\put(42.00,67.67){\line(0,1){3.00}}
\put(44.00,61.67){\line(0,1){3.00}}
\put(83.00,67.67){\line(0,1){3.00}}
\put(35.00,57.00){\line(0,1){5.00}}
\put(94.00,69.00){\makebox(0,0)[lc]{{\footnotesize $\B{I}_p^{u_1}$}}}
\put(94.00,63.00){\makebox(0,0)[lc]{{\footnotesize $\B{I}_p^{u_{n-2\d-3\e}}$}}}
\put(26.00,61.67){\line(0,1){3.00}}
\put(81.00,61.67){\line(0,1){3.00}}
\put(83.00,69.00){\line(-1,0){41.00}}
\put(81.00,63.00){\line(-1,0){39.00}}
\put(30.00,60.00){\makebox(0,0)[cb]{{\tiny $\pi^{H-}$}}}
\put(29.00,9.00){\circle*{2.00}}
\put(20.00,8.62){\rule{18.00\unitlength}{1.00\unitlength}}
\put(25.00,9.00){\line(-1,0){17.00}}
\put(7.00,9.00){\line(-1,0){1.00}}
\put(5.00,9.00){\line(-1,0){1.00}}
\put(3.00,9.00){\line(-1,0){1.00}}
\put(38.00,7.67){\line(0,1){3.00}}
\put(94.00,9.00){\makebox(0,0)[lc]{{\footnotesize $\B{I}_{p/q}^{\min}$}}}
\put(20.00,7.67){\line(0,1){3.00}}
\put(75.00,7.67){\line(0,1){3.00}}
\put(75.00,9.00){\line(-1,0){39.00}}
\put(37.00,77.00){\circle*{2.00}}
\put(28.00,76.62){\rule{18.00\unitlength}{1.00\unitlength}}
\put(33.00,77.00){\line(-1,0){17.00}}
\put(15.00,77.00){\line(-1,0){1.00}}
\put(13.00,77.00){\line(-1,0){1.00}}
\put(11.00,77.00){\line(-1,0){1.00}}
\put(46.00,75.67){\line(0,1){3.00}}
\put(94.00,77.00){\makebox(0,0)[lc]{{\footnotesize $\B{I}_{p/q}^{\max}$}}}
\put(28.00,75.67){\line(0,1){3.00}}
\put(83.00,75.67){\line(0,1){3.00}}
\put(83.00,77.00){\line(-1,0){39.00}}
\put(38.26,65.00){\line(0,-1){1.00}}
\put(38.26,62.00){\line(0,1){1.00}}
\put(38.26,59.00){\line(0,-1){1.00}}
\put(38.26,57.00){\line(0,-1){1.00}}
\put(38.26,55.00){\line(0,-1){1.00}}
\put(38.26,53.00){\line(0,-1){1.00}}
\put(38.26,51.00){\line(0,-1){1.00}}
\put(38.26,83.00){\line(0,-1){1.00}}
\put(38.26,81.00){\line(0,-1){1.00}}
\put(38.26,79.00){\line(0,-1){1.00}}
\put(38.26,77.00){\line(0,-1){1.00}}
\put(38.26,75.00){\line(0,-1){1.00}}
\put(38.26,73.00){\line(0,-1){1.00}}
\put(38.26,71.00){\line(0,-1){1.00}}
\put(38.26,69.00){\line(0,-1){1.00}}
\put(38.26,67.00){\line(0,-1){1.00}}
\put(33.00,82.00){\vector(1,0){5.00}}
\put(32.00,83.00){\makebox(0,0)[cb]{{\footnotesize $\iota_x$}}}
\put(26.00,48.67){\rule{12.00\unitlength}{1.00\unitlength}}
\put(26.00,47.67){\line(0,1){3.00}}
\put(38.00,47.67){\line(0,1){3.00}}
\put(32.00,49.00){\circle*{2.00}}
\put(81.00,47.67){\line(0,1){3.00}}
\put(37.00,49.00){\line(1,0){44.00}}
\put(32.00,49.00){\line(-1,0){17.00}}
\put(14.00,49.00){\line(-1,0){1.00}}
\put(12.00,49.00){\line(-1,0){1.00}}
\put(10.00,49.00){\line(-1,0){1.00}}
\put(38.26,23.00){\line(0,-1){1.00}}
\put(38.26,20.00){\line(0,1){1.00}}
\put(38.26,19.00){\line(0,-1){1.00}}
\put(38.26,17.00){\line(0,-1){1.00}}
\put(38.26,45.00){\line(0,-1){1.00}}
\put(38.26,42.00){\line(0,1){1.00}}
\put(38.26,41.00){\line(0,-1){1.00}}
\put(38.26,39.00){\line(0,-1){1.00}}
\put(38.26,37.00){\line(0,-1){1.00}}
\put(38.26,35.00){\line(0,-1){1.00}}
\put(38.26,33.00){\line(0,-1){1.00}}
\put(38.26,31.00){\line(0,-1){1.00}}
\put(38.26,29.00){\line(0,-1){1.00}}
\put(38.26,27.00){\line(0,-1){1.00}}
\put(38.26,25.00){\line(0,-1){1.00}}
\put(38.26,49.00){\line(0,-1){1.00}}
\put(38.26,47.00){\line(0,-1){1.00}}
\put(94.00,49.00){\makebox(0,0)[lc]{{\small $\B{R}_p$}}}
\put(31.00,22.00){\circle*{2.00}}
\put(22.00,21.62){\rule{18.00\unitlength}{1.00\unitlength}}
\put(27.00,22.00){\line(-1,0){17.00}}
\put(9.00,22.00){\line(-1,0){1.00}}
\put(7.00,22.00){\line(-1,0){1.00}}
\put(5.00,22.00){\line(-1,0){1.00}}
\put(40.00,20.67){\line(0,1){3.00}}
\put(94.00,22.00){\makebox(0,0)[lc]{{\footnotesize $\B{I}_q^{u_{n-2\d-3\e}}$}}}
\put(77.00,20.67){\line(0,1){3.00}}
\put(77.00,22.00){\line(-1,0){39.00}}
\put(29.00,16.00){\circle*{2.00}}
\put(20.00,14.67){\line(0,1){3.00}}
\put(20.00,15.62){\rule{18.00\unitlength}{1.00\unitlength}}
\put(25.00,16.00){\line(-1,0){17.00}}
\put(7.00,16.00){\line(-1,0){1.00}}
\put(5.00,16.00){\line(-1,0){1.00}}
\put(3.00,16.00){\line(-1,0){1.00}}
\put(38.00,14.67){\line(0,1){3.00}}
\put(79.00,14.67){\line(0,1){3.00}}
\put(94.00,16.00){\makebox(0,0)[lc]{{\footnotesize $\B{I}_q^{u_1}$}}}
\put(79.00,16.00){\line(-1,0){41.00}}
\put(22.00,29.67){\rule{16.00\unitlength}{1.00\unitlength}}
\put(30.00,30.00){\circle*{2.00}}
\put(38.00,28.67){\line(0,1){3.00}}
\put(94.00,30.00){\makebox(0,0)[lc]{{\small $\B{R}_q$}}}
\put(77.00,28.67){\line(0,1){3.00}}
\put(77.00,30.00){\line(-1,0){39.00}}
\put(27.00,30.00){\line(-1,0){17.00}}
\put(9.00,30.00){\line(-1,0){1.00}}
\put(7.00,30.00){\line(-1,0){1.00}}
\put(5.00,30.00){\line(-1,0){1.00}}
\put(33.00,27.00){\makebox(0,0)[cb]{{\tiny $\pi_I$}}}
\put(33.00,25.00){\vector(1,0){2.00}}
\put(34.00,25.00){\vector(-1,0){3.00}}
\put(32.00,49.00){\line(0,1){5.00}}
\put(54.00,53.00){\vector(1,0){27.00}}
\put(55.00,53.00){\vector(-1,0){23.00}}
\put(57.00,54.00){\makebox(0,0)[cb]{{\footnotesize $\beta'$}}}
\put(40.00,60.00){\makebox(0,0)[cb]{{\tiny $\pi^{H+}$}}}
\put(29.00,46.00){\makebox(0,0)[ct]{{\tiny $\pi_0^{-}$}}}
\put(36.00,46.00){\makebox(0,0)[ct]{{\tiny $\pi_0^{+}$}}}
\put(26.99,34.00){\makebox(0,0)[cb]{{\tiny $\pi_0^{-}$}}}
\put(33.99,34.00){\makebox(0,0)[cb]{{\tiny $\pi_0^{+}$}}}
\put(31.00,39.00){\makebox(0,0)[cb]{{\footnotesize $\zeta'$}}}
\put(38.26,13.00){\line(0,-1){1.00}}
\put(38.26,10.00){\line(0,1){1.00}}
\put(38.26,9.00){\line(0,-1){1.00}}
\put(38.26,7.00){\line(0,-1){1.00}}
\put(38.26,15.00){\line(0,-1){1.00}}
\put(73.00,66.00){\makebox(0,0)[cc]{{$\stackrel{\textstyle.}{\stackrel{\textstyle.}{.}}$}}}
\put(39.00,46.00){\line(0,1){2.03}}
\put(25.85,65.00){\line(0,-1){1.00}}
\put(25.85,62.00){\line(0,1){1.00}}
\put(25.85,83.00){\line(0,-1){1.00}}
\put(25.85,81.00){\line(0,-1){1.00}}
\put(27.85,79.00){\line(0,-1){1.00}}
\put(27.85,77.00){\line(0,-1){1.00}}
\put(25.85,75.00){\line(0,-1){1.00}}
\put(25.85,73.00){\line(0,-1){1.00}}
\put(25.85,71.00){\line(0,-1){1.00}}
\put(25.85,69.00){\line(0,-1){1.00}}
\put(25.85,67.00){\line(0,-1){1.00}}
\put(25.85,49.00){\line(0,-1){1.00}}
\put(22.00,20.67){\line(0,1){3.00}}
\put(22.00,28.67){\line(0,1){3.00}}
\put(31.00,22.00){\line(0,1){4.00}}
\put(35.00,24.00){\line(0,1){34.00}}
\put(59.00,59.00){\vector(-1,0){24.00}}
\put(59.00,59.00){\vector(1,0){22.00}}
\put(58.00,60.00){\makebox(0,0)[cb]{{\footnotesize $\beta$}}}
\put(25.00,47.00){\line(1,0){13.98}}
\put(23.00,32.00){\line(1,0){14.02}}
\put(73.00,19.00){\makebox(0,0)[cc]{{$\stackrel{\textstyle.}{\stackrel{\textstyle.}{.}}$}}}
\put(37.00,31.00){\line(0,1){2.03}}
\put(23.00,31.00){\line(0,1){2.03}}
\put(25.00,46.00){\line(0,1){2.03}}
\put(29.98,32.03){\circle*{0.65}}
\put(32.00,46.98){\circle*{0.65}}
\put(81.33,27.00){\line(0,1){2.00}}
\put(81.33,30.00){\line(0,1){2.00}}
\put(81.33,33.00){\line(0,1){2.00}}
\put(81.33,36.00){\line(0,1){2.00}}
\put(81.33,39.00){\line(0,1){2.00}}
\put(81.33,42.00){\line(0,1){2.00}}
\put(81.33,45.00){\line(0,1){2.00}}
\put(81.33,48.00){\line(0,1){2.00}}
\put(81.33,51.00){\line(0,1){2.00}}
\put(81.33,54.00){\line(0,1){2.00}}
\put(81.33,57.00){\line(0,1){2.00}}
\put(81.33,60.00){\line(0,1){2.00}}
\put(81.33,63.00){\line(0,1){2.00}}
\put(21.67,22.00){\line(0,1){2.00}}
\put(21.67,25.00){\line(0,1){2.00}}
\put(21.67,28.00){\line(0,1){2.00}}
\put(21.67,31.00){\line(0,1){2.00}}
\put(21.67,34.00){\line(0,1){2.00}}
\put(21.67,37.00){\line(0,1){2.00}}
\put(21.67,40.00){\line(0,1){2.00}}
\put(21.67,43.00){\line(0,1){2.00}}
\put(21.67,46.00){\line(0,1){2.00}}
\put(21.67,49.00){\line(0,1){2.00}}
\put(33.00,37.00){\vector(-1,0){1.00}}
\put(29.00,37.00){\vector(1,0){1.00}}
\put(30.00,37.00){\line(1,0){2.00}}
\put(30.00,38.00){\line(0,-1){8.00}}
\put(32.00,36.00){\line(0,1){13.00}}
\put(24.00,12.00){\makebox(0,0)[cb]{{\tiny $\pi^{H-}$}}}
\put(34.00,12.00){\makebox(0,0)[cb]{{\tiny $\pi^{H+}$}}}
\put(33.00,82.00){\vector(-1,0){7.00}}
\put(25.85,79.00){\line(0,-1){1.00}}
\put(25.85,77.00){\line(0,-1){1.00}}
\put(38.00,3.00){\makebox(0,0)[ct]{{\footnotesize $R$}}}
\put(25.85,59.00){\line(0,-1){1.00}}
\put(25.85,57.00){\line(0,-1){1.00}}
\put(25.85,55.00){\line(0,-1){1.00}}
\put(25.85,53.00){\line(0,-1){1.00}}
\put(25.85,50.00){\line(0,-1){1.00}}
\put(25.85,61.00){\line(0,-1){1.00}}
\end{picture}
\end{center}
\caption{\em Worst-case scenario for ${\alpha_p'}^+=\beta'$ with
resulting precision $\zeta'$. The intersection of the leftmost
non-faulty precision interval $\protect\ppI{\protect\B{I}}_{p/q}^{\min}$ with
any non-faulty $\protect\ppI{\protect\B{I}}_p^x$ has length $\iota_x$.
The $n-2\d-3\e$ nc-unions of input intervals $\protect\VB{I}_p^{u_i}
\nccup\protect\VB{I}_q^{u_i}$ contain the resulting
$\protect\VB{R}_p\nccup\protect\VB{R}_q$.}
\label{fig:accproof}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
First, let $\VB{I}=[T-\pi^-,T+\alpha^+]$ be the {\em mixed
interval\/} of an arbitrary accuracy interval
$\B{I}=[T\pm\B{\alpha}]$ with its associated $\B{\pi}$-precision
interval $\ppI{\B{I}}=[T\pm\B{\pi}]$. Mixed intervals are in fact ideally
suited for attacking our problem: Since left and right edge of the
result of
$\M$ (and hence $\OA$) are computed independently of each other, and
$\mbox{right}(\VB{I}_p^s)=\mbox{right}(\B{I}_p^s)$ respectively
$\mbox{left}(\VB{I}_p^s)=\mbox{left}(\ppI{\B{I}}_p^s)$, it follows that
$\mbox{right}(\VB{R}_p)=\mbox{right}(\B{R}_p)$ respectively
$\mbox{left}(\VB{R}_p)=\mbox{left}(\ppI{\B{R}}_p)$ as well.
Analyzing the result
of $\M$ in terms of mixed intervals, however, is easy since the
hybrid fault model in Assumption~\ref{asum:faultmodel} guarantees
that the sets of mixed input intervals $\VB{\cal I}_p^s$, $\VB{\cal
I}_q^s$ are in accordance with the fault model of
Definition~\ref{def:pairfaultiv}, which underlies the results on
Marzullo's function~$\M$ derived in Section~\ref{Marzullo
Function}.
To see that Figure~\ref{fig:accproof} provides a worst-case scenario
for ${\alpha_p'}^+ = \beta'$, we first argue that $|\VB{R}_p|$
cannot be larger than $\beta+\pi^{H-}$, since item~(2) of
Lemma~\ref{lem:accM} in conjunction with (\ref{equ:newy}) reveals
that $\VB{R}_p$ lies within at least $n-2\d-3\e\geq1$ non-faulty input
intervals $\VB{I}_p^{b_k}\in \B{\cal J}_p$. Note that it is assumed
in Figure~\ref{fig:accproof} that $\B{I}_p^{u_i}=\B{I}_p^{b_i}$ has
the $i$-th largest accuracy bound $\beta_p^{i+}$ and
$\VB{I}_p^{u_{i+1}}\subseteq \VB{I}_p^{u_i}$. This implies that
$\mbox{left}(\VB{R}_p)$ cannot be further left. Moreover, in an attempt
to maximize $\beta'$, it could not be set further right either due to
the monotonicity property (\ref{equ:monpice}) of
$\mbox{$\B{\pi}$-center}_{G_S}$.
Next, from item~(2) of Lemma~\ref{lem:degradeM} it follows that
there are at least $n-2\d-3\e$ pairs of non-faulty intervals
$\{\B{I}^{u_k}_p$, $\B{I}^{u_k}_q\}$ (present in $\B{\cal J}_p$ respectively
$\B{\cal J}_q$) such that $\VB{R}_p\nccup\VB{R}_q \subseteq
\bigcap_{k=1}^{n-2\d-3\e}\VB{I}^{u_k}_p \nccup \VB{I}^{u_k}_q$.
Since the reference points (and hence the left edges of the mixed
intervals) of any non-faulty pair $\B{I}_p^s$, $\B{I}_q^s$ can be at
most $\pi_I$ apart according to
precondition~[2], $\mbox{left}(\VB{R}_q)$ cannot be further left than
shown in Figure~\ref{fig:accproof}.
Finally, as far as the worst position of $\mbox{right}(\pB{R}_p)$ is
concerned, we know from precondition~[3] of our theorem that no
non-faulty precision interval $\ppI{\B{I}}_p^s$, $\ppI{\B{I}}_q^s$
can have a right edge left of $R$ in Figure~\ref{fig:accproof}.
Hence, from the distributed
minimal intersection property of $\M$ in item~(1) of
Lemma~\ref{lem:degradeM}, it follows that both $\pB{R}_p$ and
$\pB{R}_q$ must have this property as well. It follows that we have
to consider $\mbox{right}(\pB{R}_p)=R$ and $\mbox{right}(\pB{R}_q)=R$
for worst-case settings with respect to $\beta'$ only, since
the monotonicity property (\ref{equ:monpice})
of $\mbox{$\B{\pi}$-center}_{G_S}$ implies again that setting
$\mbox{right}(\pB{R}_p)$ further right
would provide a smaller $\beta'$ only. Similarly, setting
$\mbox{right}(\pB{R}_q)$ further right could only decrease
$\zeta'$, which would enlarge $\iota_x'$ in the next round and hence
provide a smaller $\beta'$ then, see below.
Evaluating $\beta'$ for the above situation is simple: By using
(\ref{equ:almi}) and $-\lceil x \rceil = \lfloor -x \rfloor$
(see~\cite[Sec.~1.2.4, Ex.~4]{Knu73}), we find
\begin{equation}
\beta' = \beta + \pi^{H-} -
\Bigl\lfloor\frac{\pi^{H-}}{\pi^H}\iota_x\Bigr\rfloor_{G_S}
= \beta +
\Bigl\lceil\frac{\pi^H}{\pi^H}\pi^{H-}-\frac{\pi^{H-}}{\pi^H}\iota_x\Bigr\rceil_{G_S},\label{equ:equbeta}
\end{equation}
which easily yields expression (\ref{equ:fabplu}) for $\aleph^+(\cdot)$.
The required monotonicity is immediately apparent, given that
$\pi^{H+}/\pi^H$ and $\pi^{H-}/\pi^H$ were assumed to be invariant.
Next, we have to prove the expression for
$\Im^+(\cdot)=\mbox{ref}(\B{R}_p)-\mbox{ref}(\B{R}_q)$ given in
item~(2) of our theorem, which is bounded by $\zeta'$ in
Figure~\ref{fig:accproof}. Noting that
$\mbox{left}(\B{R}_p)-\mbox{left}(\B{R}_q)=\pi_I$ here, we obtain
\begin{eqnarray}
\zeta' &=& \pi_I +
\Bigl\lfloor\frac{\pi^{H-}}{\pi^H}\iota_x\Bigr\rfloor_{G_S} -
\Bigl\lfloor\frac{\pi^{H-}}{\pi^H}(\pi_I+\iota_x)\Bigr\rfloor_{G_S}
\nonumber\\
&=& \Bigl\lfloor\frac{\pi^{H-}}{\pi^H}\iota_x\Bigr\rfloor_{G_S}
+ \Bigl\lceil\frac{\pi^{H+}}{\pi^H}\pi_I -
\frac{\pi^{H-}}{\pi^H}\iota_x\Bigr\rceil_{G_S}\nonumber\\
&\leq& \Bigl\lceil\frac{\pi^{H+}}{\pi^H}\pi_I
\Bigr\rceil_{G_S},
\end{eqnarray}
where we used the ``triangle inequality'' $\lceil x + y \rceil \leq
\lceil x \rceil + \lceil y \rceil$ (see~\cite[Sec.~1.2.4,
Ex.~7]{Knu73}). This eventually confirms the expression for
$\Im^+(\cdot)$ in (\ref{equ:ims}). The required monotonicity of
$\Im^+(\cdot)$ is again immediately apparent.
The analogous expressions for $\aleph^-(\cdot)$ respectively
$\Im^-(\cdot)$
can be obtained by considering Figure~\ref{fig:accproof} mirrored at the
(dashed) vertical line $R$ and exchanging $\pi^{H+}$ and $\pi^{H-}$ etc.
Comparing (\ref{equ:almi}) and (\ref{equ:alplu}) reveals that
$\aleph^-(\cdot)$ given by (\ref{equ:fab}) follows from
replacing $\lfloor .\rfloor$ by $\lceil . \rceil$ in (\ref{equ:equbeta}).
Similarly, we find
\begin{eqnarray}
{\zeta}' &=& \pi_I + \Bigl\lceil\frac{\pi^{H+}}{\pi^H}\iota_x\Bigr\rceil_{G_S}
- \Bigl\lceil\frac{\pi^{H+}}{\pi^H}(\pi_I+\iota_x)\Bigr\rceil_{G_S}\nonumber\\
&=& \Bigl\lceil\frac{\pi^{H-}}{\pi^H}\pi_I +
\frac{\pi^{H+}}{\pi^H}(\pi_I+\iota_x)\Bigr\rceil_{G_S} -
\Bigl\lceil\frac{\pi^{H+}}{\pi^H}(\pi_I+\iota_x)\Bigr\rceil_{G_S}
\nonumber\\
&\leq& \Bigl\lceil\frac{\pi^{H-}}{\pi^H}\pi_I
\Bigr\rceil_{G_S} + \Bigl\lceil
\frac{\pi^{H+}}{\pi^H}(\pi_I+\iota_x)\Bigr\rceil_{G_S}
-\Bigl\lceil\frac{\pi^{H+}}{\pi^H}(\pi_I+\iota_x)\Bigr\rceil_{G_S} \nonumber\\
&=& \Bigl\lceil\frac{\pi^{H-}}{\pi^H}\pi_I
\Bigr\rceil_{G_S},\nonumber
\end{eqnarray}
which confirms the expression for $\Im^-(\cdot)$ in (\ref{equ:ims}).
To complete the proof of our theorem, it only remains to
show that the worst-case scenario considered here is also {\em
globally\/} valid. It is of course locally valid, in the sense that
there is no scenario that provides a worse $\beta'$ for the given
$\iota_x$. However, the resulting $\zeta'$ is quite small, and since
$\zeta'$ determines $\iota_x$ ---and hence $\beta'$--- in the next
round\footnote{Note that $\iota_x$ does actually not depend upon~$x$
since $\zeta'$ is uniformly valid, see Theorem~\ref{thm:accOA}.},
the question arises whether a locally suboptimal setting could
provide a worse overall accuracy. In view of (\ref{equ:fabplu}) and
(\ref{equ:fab}), it is sufficient to check whether
$\beta'+\zeta'=\mbox{right}(\B{R}_p)-\mbox{ref}(\B{R}_q)$
is maximal in the scenario of Figure~\ref{fig:accproof}, which is of
course true by construction. This eventually completes the proof of
Theorem~\ref{thm:convOAacc}. $\Box$
\begin{rmm}
\pitem
There is a straightforward modification of
${\OA}$ that improves accuracy by exploiting further information from
reference point setting. More specifically, any interval
$\B{I}\in\B{\cal J}$ satisfying
$\ppI{\B{I}}\cap{\M}_{n'}^{n-\d-\e}(\ppI{\B{\cal J}}) = \emptyset$ is
faulty since its associated $\B{\pi}^H$-precision interval does not
contain internal global time $\tau$ and may thus be discarded prior
to computing the accuracy interval in (\ref{equ:accurOA}). Item~(3)
of Lemma~\ref{lem:monotonicityM} implies that the accuracy of this
modified version is not worse than ${\OA}$'s, and should in fact be
better in most executions, in particular, if accuracies are large.
\pitem
Apart from clock state synchronization elaborated on in this paper,
Theorems~\ref{thm:convOAprec} and~\ref{thm:convOAacc} can also be
used immediately for clock rate synchronization. The latter is an
interesting alternative to high-performance quartz clocks when
targeting clock synchronization with very high precision, where
decreasing any clock's drift rate to, say, $\rho \leq 10^{-7}$ is
mandatory. Interestingly enough, this problem is also tractable by
interval-based techniques: A generic analysis for clock rate
synchronization, which relies on the same paradigm as \cite{SS97:1},
was conducted in \cite{Scho97}. It shows that any convergence
function suitable for interval-based clock synchronization ---like
$\OA$--- can be reused in the rate setting as well.
\pitem
It is interesting to note that statements and proof of our major
Theorems~\ref{thm:convOAprec} and~\ref{thm:convOAacc} apply literally
when the Marzullo function employed for computing the reference point
(\ref{equ:centerOA}) in $\OA$'s Definition~\ref{def:OA} is replaced
by certain other interval-based functions.
For example, it is possible to recast the
well-known fault-tolerant midpoint convergence function (FTM) of
\cite{LL88} into an equivalent interval-based version FTM-I (similar to the
one employed in \cite{Lam87}) that operates on equally-sized intervals.
Recall that the input precision intervals in
(\ref{equ:centerOA}) are obtained by mounting the same
interval $\B{\pi}^H$ at the accuracy intervals' reference
points, resulting in identical length. Similar pigeonhole principle
proofs as in Section~\ref{Marzullo Function}
can then be used to show that the pivotal upper bounds of
Lemma~\ref{lem:accM} and~\ref{lem:precM} for $\M$ apply to FTM-I as well.
\end{rmm}
\section{Orthogonal Accuracy Algorithm}
\label{Orthogonal Accuracy Algorithm}
In this section, we will plug in the characteristic functions of the
orthogonal accuracy convergence function $\OA$ into the generic
expressions for precision, accuracy, etc.\ of
Theorem~\ref{thm:precandacc} in Appendix~C.
This provides a complete characterization of the worst-case
performance of the orthogonal accuracy algorithm OA. In order to
briefly introduce the various parameters of our system model arising
in the resulting expressions, we restated the generic algorithm's
definition (\cite[Def.~7]{SS97:1}) in Definition~\ref{def:OAalgorithm};
consult \cite[Assum.~1--4]{SS97:1} for additional information.
The first of our major theorems describes the worst-case performance
of OA with respect to precision. It assumes instantaneous clock correction in
Step~(T) of OA, although most results carry over literally to
continuous amortization, see \cite[Thm.~2]{SS97:1} for details.
\begin{thm}[Precision Algorithm OA]\label{thm:precOA}
For the system model complying to
\cite[Assum.~1--4]{SS97:1} and the fault model in
Assumption~\ref{asum:faultmodel},
the orthogonal accuracy algorithm
with instantaneous clock correction, transmission delay compensation
\begin{eqnarray}
\Delta&\geq&
2\varepsilon_{\max}+\varepsilon_{\max}^++(B+3)u_{\max}+2G+G_S+\delta_{\max}(1+\rho_{\max}^-)\nonumber\\
&&+(2P+\Lambda+\Omega
+2\Gamma_{\max}-2\Gamma_{\min}-2\delta_{\min})\rho_{\max}\nonumber\\
&&+{\cal O}(P\rho_{\max}^2 + G\rho_{\max} +
\varepsilon_{\max}\rho_{\max})\label{equ:deltaOAalg},
\end{eqnarray}
and the (symmetric!)
\begin{eqnarray}
\B{\pi}^H
&=&\B{\pi}_0 + 2 \B{u}_{\max} + \overline{\B{G}} + \B{\varepsilon}_{\max}+
(P+\Gamma_{\max}-\Gamma_{\min}-\delta_{\min})\B{\rho}_{\max}\nonumber\\
&&+ {\cal O}(P\rho_{\max} + G +
\varepsilon_{\max})\B{\rho}_{\max}\label{equ:piHB}
\end{eqnarray}
used in $\OA^{\B{\pi}^H}_{n-\d-\e}$
requires ${\cal O}(n\log n)$ computation time to
synchronize the (non-faulty) clocks of $n$~nodes as follows:
\noindent{(1) } Initial worst-case precision (that is, the precision at
the beginning of each round of the slowest non-faulty clock)
\begin{equation}
\pi_{0,\max} = \pi_0 + u_{\max} + G +
(\Gamma_{\max}-\Gamma_{\min})\rho_{\max} + {\cal O}(P\rho_{\max}^2 +
G\rho_{\max} + \varepsilon_{\max}\rho_{\max})\label{equ:pi0mx}
\end{equation}
where $\B{\pi}_0=[-\pi_0^-,\pi_0^+]$ is
given by
\begin{eqnarray}
\pi_0^- &=& \frac12\Bigl(\varepsilon_{\max} +Bu_{\max}+ G + G_S +
(\Lambda + \Omega + \Delta + \Gamma_{\max} -
\delta_{\min})\rho_{\max}\Bigr)\nonumber\\
&&+2u_{\max}^++\varepsilon_{\max}^+ + (P+\Gamma_{\max} -\Gamma_{\min}
-\delta_{\min})\rho_{\max}^+ \nonumber\\
&&+{\cal O}(P\rho_{\max}^2 + G\rho_{\max} +
\varepsilon_{\max}\rho_{\max})\label{equ:algpi0m}\\
\pi_0^+ &=& \frac12\Bigl(\varepsilon_{\max} + Bu_{\max} + G + G_S+
(\Lambda + \Omega + \Delta + \Gamma_{\max} -
\delta_{\min})\rho_{\max} \Bigr) \nonumber\\
&&+2u_{\max}^-+\varepsilon_{\max}^- + G + (P+\Gamma_{\max} -\Gamma_{\min}
-\delta_{\min})\rho_{\max}^- \nonumber\\
&&+{\cal O}(P\rho_{\max}^2 + G\rho_{\max} +
\varepsilon_{\max}\rho_{\max})\label{equ:algpi0p},
\end{eqnarray}
so that
\begin{eqnarray}
\pi_0 &=& 2\varepsilon_{\max} +(B+2)u_{\max} + 2G + G_S\\\nonumber
&&+ (P+\Lambda + \Omega + \Delta + 2\Gamma_{\max} -
\Gamma_{\min}-2\delta_{\min})\rho_{\max}\nonumber\\
&&+{\cal O}(P\rho_{\max}^2 + G\rho_{\max} +
\varepsilon_{\max}\rho_{\max})\label{equ:pi0thm}.
\end{eqnarray}
\noindent{(2) } Overall worst-case
precision $\pi_{\max}$ satisfying
\begin{eqnarray}
\pi_{\max}&=& 2\varepsilon_{\max} +(B+3)u_{\max} + 3G +
G_S\nonumber\\
&&+(2P + \Lambda + \Omega + \Delta + 2\Gamma_{\max} -
\Gamma_{\min} - 2\delta_{\min})\rho_{\max}\nonumber\\
&&+ \max\Bigl\{\varepsilon_{\max}^++2u_{\max}^+ +(2\Gamma_{\max}-
2\Gamma_{\min}-\delta_{\min})\rho_{\max}^+,\nonumber\\
&&\varepsilon_{\max}^- +2u_{\max}^- +G +
(2\Gamma_{\max}-2\Gamma_{\min}-\delta_{\min})\rho_{\max}^-, 0\Bigr\}\nonumber\\
&&+{\cal O}(P\rho_{\max}^2 + G\rho_{\max} +
\varepsilon_{\max}\rho_{\max}).\label{equ:defpimaxOA}
\end{eqnarray}
\noindent{(3) } Any two non-faulty nodes~$p$, $q$
resynchronize within real-time
$t_p^R-t_q^R$ satisfying
\[
\Gamma_p-\Gamma_q - {\pi}_P \leq t_p^R-t_q^R \leq \Gamma_p-\Gamma_q +
{\pi}_P
\]
for
\begin{equation}
{\pi}_P={\pi}_0 + u_{\max} + P{\rho}_{\max} + {\cal O}(P\rho_{\max}^2 + G\rho_{\max} +
\varepsilon_{\max}\rho_{\max}).\label{equ:piPP}
\end{equation}
\noindent{(4) } Adjustments of at most $\Upsilon$ are
applied to the local
clock of any non-faulty node, which are bounded according to
$-\pi^- \leq \Upsilon \leq \pi^+$ with
\begin{eqnarray}
\pi^-&=& 2\varepsilon_{\max} +(B+3)u_{\max} + 2G +G_S\label{piminthm} \\
&&+(2P + \Lambda + \Omega + \Delta + 2\Gamma_{\max} -
\Gamma_{\min} - 2\delta_{\min})\rho_{\max} + \varepsilon_{\max}^+ + u_{\max}^+\nonumber\\
&&+ (\Gamma_{\max}-\Gamma_{\min}-\delta_{\min})\rho_{\max}^+
+{\cal O}(P\rho_{\max}^2 + G\rho_{\max} +
\varepsilon_{\max}\rho_{\max}),\nonumber
\end{eqnarray}
\begin{eqnarray}
\pi^+&=& 2\varepsilon_{\max} +(B+3)u_{\max} + 3G +G_S \label{pipluthm}\\
&&+(2P + \Lambda + \Omega + \Delta + 2\Gamma_{\max} -
\Gamma_{\min} - 2\delta_{\min})\rho_{\max}+ \varepsilon_{\max}^- + u_{\max}^-\nonumber\\
&&+(\Gamma_{\max}-\Gamma_{\min}-\delta_{\min})\rho_{\max}^-
+{\cal O}(P\rho_{\max}^2 + G\rho_{\max} +
\varepsilon_{\max}\rho_{\max}).\nonumber
\end{eqnarray}
\end{thm}
\noindent
{\bf Proof\,} The computational complexity of the orthogonal accuracy
algorithm is primarily determined by the complexity of computing the
convergence function $\OA$, which is ${\cal O}(n \log n)$ due to the
two evaluations of ${\M}$ employed in $\OA$, recall
Definition~\ref{def:OA} and~\ref{def:M}.
By item~(1) of Theorem~\ref{thm:precandacc},
$\B{\pi}_0$ is the solution of the equation
$|\B{\pi}_0| = \Pi(\B{\pi}^H,\B{\pi}_I)$ involving $\OA$'s precision
enhancement function $\Pi(\cdot)$ given by (\ref{equ:OAprecenhs}).
Precision enhancement is optimal if $\B{\pi}^H$ given by
(\ref{equ:defpiHgeneric}) is a symmetric interval,
recall the remarks following Theorem~\ref{thm:convOAprec}. Note that
the condition imposed on $\pi_I$ in precondition~[2] of
Theorem~\ref{thm:convOAprec} is also amply fulfilled in this case, just compare
(\ref{equ:defpiIgeneric}) and (\ref{equ:piHB}).
Hence, writing
$\B{\pi}^H=\B{\pi}_0+\B{\pi}_1$ with
\begin{eqnarray}
\B{\pi}_1
&=& 2\B{u}_{\max} + \overline{\B{G}} + \B{\varepsilon}_{\max}+
(P+\Gamma_{\max}-\Gamma_{\min}-\delta_{\min})
\B{\rho}_{\max}\label{equ:pieinsdef} \\
&&+{\cal O}(P\rho_{\max} + G +\varepsilon_{\max})\B{\rho}_{\max}\nonumber ,
\end{eqnarray}
we exploit the freedom of choosing an arbitrary reference point of
$\B{\pi}_0$ to enforce this symmetry: Setting
\begin{equation}
\B{\pi}_0=\Bigl[-\Bigl(\lceil\pi_I/2\rceil_{G_S} +
\pi_1^+\Bigr), \lceil\pi_I/2\rceil_{G_S} +
\pi_1^-\Bigr]\label{equ:pi0intv}
\end{equation}
such that $\pi_0=2\lceil\pi_I/2\rceil_{G_S}+\pi_1$ provides a symmetric interval
\begin{equation}
\B{\pi}^H=\B{\pi}_0+\B{\pi}_1=\Bigl[-\Bigl(\lceil\pi_I/2\rceil_{G_S} +
\pi_1\Bigr), \lceil\pi_I/2\rceil_{G_S} + \pi_1\Bigr]\label{equ:piHHH}
\end{equation}
with $\pi^H=2\lceil\pi_I/2\rceil_{G_S}+2\pi_1$. Evaluating
$\Pi(\B{\pi}^H,\B{\pi}_I)$ given by (\ref{equ:OAprecenhs}) yields
\[
\max\Bigl\{\Bigl\lceil\pi^{H+} +
\frac{\pi^{H-}}{\pi^H}\pi_I\Bigr\rceil_{G_S}, \Bigl\lceil\pi^{H-} +
\frac{\pi^{H+}}{\pi^H}\pi_I\Bigr\rceil_{G_S}\Bigr\}=
\]
\begin{eqnarray}
&=&\Bigl\lceil\frac{\pi^H+\pi_I}{2}\Bigr\rceil_{G_S}
=\Bigl\lceil\lceil\pi_I/2\rceil_{G_S} + \pi_1
+\pi_I/2 \Bigr\rceil_{G_S}\nonumber\\
&=& 2\lceil\pi_I/2\rceil_{G_S} + \pi_1 =
\pi_0\label{equ:defpi0ges}
\end{eqnarray}
as required; recall that $\pi_1$ and all other precision values are
integer multiples of $G_S$ since its constituting parameters have
this property, see Definition~\ref{def:OAalgorithm}.
Plugging in $\pi_1^+$, $\pi_1^-$ resulting from (\ref{equ:pieinsdef})
and $\lceil\pi_I/2\rceil_{G_S}\leq \pi_I/2 + G_S/2$ with
$\pi_I=|\B{\pi}_I|$ from (\ref{equ:defpiIgeneric}) into (\ref{equ:pi0intv})
confirms the values of $\pi_0^-$, $\pi_0^+$ given in
(\ref{equ:algpi0m}) and (\ref{equ:algpi0p}).
Addition or, alternatively, substitution in
(\ref{equ:defpi0ges}) provides the value of $\pi_0$ stated in
(\ref{equ:pi0thm}). Last but not least, (\ref{equ:pi0mx}) providing
$\pi_{0,\max}$ is only a restatement of (\ref{equ:pi0max}).
Next, the value $\pi_P$ given in (\ref{equ:piPP}) is obtained
by plugging in (conservative) maximum bounds for
$\B{u}_{p/q}$ and $\B{\rho}_{p/q}$ in (\ref{equ:piP}).
Plugging in the swapped
$\overline{\B{\Phi}}(\B{\pi}^H)=\overline{\B{\pi}}^H$
according to item~(1)
of Theorem~\ref{thm:convOAprec} and the definition (\ref{equ:piHB}) of $\B{\pi}^H$
into (\ref{equ:piiii}) provides
\begin{eqnarray}
\B{\pi}&=& \overline{\B{\pi}}_0 + 2 \overline{\B{u}}_{max} + {\B{G}} +
\overline{\B{\varepsilon}}_{\max}+
\Bigl(P+\Gamma_{\max}-\Gamma_{\min}-\delta_{\min} \nonumber\\
&&+{\cal O}(P\rho_{\max} + G +
\varepsilon_{\max})\Bigr)\overline{\B{\rho}}_{\max}\nonumber\\
&&+\B{\pi}_0 + \B{u}_{\max}+ \Bigl(P+{\cal
O}(P\rho_{\max} + G + \varepsilon_{\max})\Bigr)\B{\rho}_{\max}\nonumber,
\end{eqnarray}
from where the values of $\pi^-$, $\pi^+$
given in (\ref{piminthm}) and (\ref{pipluthm}) follow easily.
Now it is possible to evaluate (\ref{equ:pimax}) in
Theorem~\ref{thm:precandacc}, which confirms the value of $\pi_{\max}$ stated
in (\ref{equ:defpimaxOA}).
The proof of Theorem~\ref{thm:precOA} is almost completed; we only
have to justify the value of $\Delta$ given in
(\ref{equ:deltaOAalg}).
Plugging in the expressions for $\pi_0$ and $\pi={\cal
O}(\varepsilon_{\max} + G + P\rho_{\max})$
into the definition of $\Delta$ in (\ref{equ:deltadefalg}), we
easily obtain
\begin{eqnarray}
\Delta&\geq&\frac{1}{1+\rho_{\max}^+}\Bigl(2\varepsilon_{\max} +
(B+3)u_{\max} + 2G +G_S +\delta_{\max} +\varepsilon_{\max}^+\nonumber\\
&&+ (2P+\Lambda + \Omega + \Delta + 2\Gamma_{\max} -
2\Gamma_{\min}-2\delta_{\min})\rho_{\max}\nonumber\\
&&+{\cal O}(P\rho_{\max}^2 + G\rho_{\max} +
\varepsilon_{\max}\rho_{\max})\Bigr)\nonumber\\
&=& \frac{Z + \Delta\rho_{\max}}{1+\rho_{\max}^+}.\nonumber
\end{eqnarray}
Solving this for $\Delta$ yields
\begin{eqnarray}
\Delta &\geq& \frac{Z}{1-\rho_{\max}^-} = Z\Bigl(1+\rho_{\max}^-+{\cal
O}\bigl((\rho_{\max}^-)^2\bigr)\Bigr) \nonumber\\
&=&
2\varepsilon_{\max}+\varepsilon_{\max}^++(B+3)u_{\max}+2G+G_S +\delta_{\max}\nonumber\\
&&+(2P+\Lambda+\Omega
+2\Gamma_{\max}-2\Gamma_{\min}-2\delta_{\min})\rho_{\max}\nonumber\\
&&+\delta_{\max}\rho_{\max}^- + {\cal O}(P\rho_{\max}^2 + G\rho_{\max} +
\varepsilon_{\max}\rho_{\max}).\nonumber
\end{eqnarray}
This eventually completes the proof of Theorem~\ref{thm:precOA}. $\Box$
\begin{rmm}
\pitem
For usual settings, the ${\cal O}(\cdot)$-terms
in our theorem are very small and can be neglected in practice.
Their only purpose is to specify the order of magnitude of the neglected
terms.
\pitem
The precision results above are valid for
\underbar{any} setting of the parameters defined in the system
model. Our analysis hence provides the worst-case
behavior of the algorithm under the worst setting of parameters,
like $\B{\rho}_p = \B{\rho}_{\max}$ for any node~$p$. One could
derive improved worst-case results for more relaxed
parameterizations, although our algorithm does not benefit much from
such situations unless refined worst-case bounds are compiled into it;
after all, $\OA$ depends on $\B{\pi}^H$!
\pitem
With respect to worst-case precision, our orthogonal accuracy
algorithm is equivalent to the well-known fault tolerant midpoint
algorithm (FTM) of \cite{LL88}, see Remark~3 following
Theorem~\ref{thm:convOAacc}. FTM has the same computational
complexity ${\cal O}(n\log n)$ and the same worst-case precision
$$
\pi_{\max} \approx 5\varepsilon + 4P\rho
$$
(in a comparable setting);
our terminology relates to the one of \cite{LL88} by
$\pi_{\max}=\gamma$, $\varepsilon_{\max}=2\varepsilon$ and
$\rho_{\max}=2\rho$. Both algorithms require initially synchronized
clocks as well.
Our algorithm is hence slightly suboptimal with respect to worst-case
precision: $\pi_{\max}$ exceeds the provably necessary and tight
lower bound $4\varepsilon+4P\rho$ (see~\cite{FC95:2}, \cite{FC95:1}) by
$\varepsilon$. The maximum correction $\Upsilon\approx
5\varepsilon+4P\rho$ applied to the clock of a non-faulty node
exceeds the tight lower bound of $2P\rho$ considerably.
\end{rmm}
The next theorem provides algorithm OA's worst-case behavior
with respect to accuracy.
\begin{thm}[Accuracy Algorithm OA]\label{thm:accOA}
For the system model complying to \cite[Assum.~1--4]{SS97:1}
and the fault model in Assumption~\ref{asum:faultmodel}, the
accuracies $\alpha_q^{k+1,-}$, $\alpha_q^{k+1,+}$ of a non-faulty
node~$q$'s accuracy interval
$\B{A}_q^{k+1}(t_q^{k+1})=[T_q^{k+1}\pm\B{\alpha}_q^{k+1}]$ at the
beginning of round $k+1$, $k\geq0$, as computed by the orthogonal
accuracy algorithm OA with transmission delay compensation $\Delta$
given by (\ref{equ:deltaOAalg}) and $\B{\pi}^H$ given
by (\ref{equ:piHB}), are integer multiples of $G_S$ satisfying the
following properties:
\noindent{(1) } The interval of accuracy satisfies
$\B{\alpha}_q^{k+1}\subseteq\B{\beta}_q^{k+1}$ with
\begin{eqnarray}
\beta_q^{k+1,-}
&=&\max_{p: n-2\d-3\e}\biggl\{\Bigl\{\beta_p^{k,-} +u_p^- + u_q^- + G +G_A
+ {\varepsilon}_{pq}^- + (P-\Delta-\Gamma_{p})\rho_{p}^-\nonumber\\
&&+ (\Gamma_q + \Delta -\delta_{pq}){\rho}_q^- +
(\Lambda+\Omega) \max\{\rho_q^- -
\rho_p^-, 0\}\Bigr\}_{p\neq q}\nonumber\\
&&\cup \Bigl\{ \beta_q^{k,-} + u_q^- + P\rho_q^-\Bigr\}\biggr\} \nonumber\\
&&+\lfloor \pi^H/4 \rfloor_{G_S} + {\cal O}(P\rho_{\max}^2 + G\rho_{\max} +
\varepsilon_{\max}{\rho}_{\max})\label{equ:detaccurminusthm}\\
&\leq&\max_{p:n-2\d-3\e} \{\beta_p^{k,-}\} + u_{\max}^- + G +G_A+
\varepsilon_{\max}^- \nonumber\\
&&+ (P-\Delta-\Gamma_{\min})\rho_{\max}^-
+u_q^- + (\Gamma_q + \Delta -\delta_{\min}){\rho}_q^-\nonumber\\
&&+\lfloor \pi^H/4 \rfloor_{G_S} + {\cal O}(P\rho_{\max}^2 + G\rho_{\max} +
\varepsilon_{\max}\rho_{\max})\label{equ:bdetaccurminusthm},\\
\beta_q^{0,-}
&=& \alpha_q^{0,-} + \lceil \pi^H/4
\rceil_{G_S},\label{equ:accnullmi}\\
\beta_q^{k+1,+} &=&
\max_{p:n-2\d-3\e} \biggl\{\Bigl\{\beta_p^{k,+} +u_p^+ + u_q^+ +
G_A + {\varepsilon}_{pq}^+ +
(P-\Delta-\Gamma_{p})\rho_{p}^+ \nonumber\\
&&+(\Gamma_q + \Delta
-\delta_{pq}){\rho}_q^+ + (\Lambda+\Omega) \max\{\rho_q^+ -
\rho_p^+, 0\}\Bigr\}_{p\neq q}\nonumber\\
&&\cup \Bigl\{ \beta_q^{k,+} + u_q^+ + P\rho_q^+\Bigr\}\biggr\}\nonumber\\
&&+ \lceil \pi^H/4 \rceil_{G_S}
+ {\cal O}(P\rho_{\max}^2 + G\rho_{\max} +
\varepsilon_{\max}{\rho}_{\max})\label{equ:detaccurplusthm}\\
&\leq&\max_{p: n-2\d-3\e} \{\beta_p^{k,+}\} +u_{\max}^+
+ G_A + \varepsilon_{\max}^+
+ (P-\Delta-\Gamma_{\min})\rho_{\max}^+ \nonumber\\
&&+u_q^+ +(\Gamma_q + \Delta -\delta_{\min}){\rho}_q^+\nonumber\\
&&+ \lceil \pi^H/4 \rceil_{G_S} + {\cal O}(P\rho_{\max}^2 + G\rho_{\max} +
\varepsilon_{\max}\rho_{\max}),\label{equ:bdetaccurplusthm}\\
\beta_q^{0,+} &=& \alpha_q^{0,+} + \lfloor \pi^H/4
\rfloor_{G_S},\label{equ:accnullpl}
\end{eqnarray}
where $\max_{p: m} {\cal B}$ denotes the $m$-th largest element
of the set ${\cal B}=\{\beta_p: 1\leq p \leq n\}$, $\B{\alpha}_q^0\subseteq\B{\pi}_0$ is the
initial interval of accuracies, and
\begin{eqnarray}
\pi^H &=& 3\varepsilon_{\max} +(B+4)u_{\max} + 3G + G_S \nonumber\\
&&+(2P+\Lambda + \Omega + \Delta + 3\Gamma_{\max} -
2\Gamma_{\min}-3\delta_{\min})\rho_{\max}\nonumber\\
&&+{\cal O}(P\rho_{\max}^2 + G\rho_{\max} +
\varepsilon_{\max}\rho_{\max}),\label{equ:equpiH}
\end{eqnarray}
note that $\lfloor \pi^H/4 \rfloor_{G_S}
\leq \pi^H/4$ and $\lceil \pi^H/4 \rceil_{G_S}
\leq \pi^H/4 + G_S/2$.
\noindent{(2) } The maximum deviation of node~$q$'s reference point
$T_q^{k+1}$ from real-time $t_q^{k+1}$ (``traditional accuracy'') at the
beginning of round~$k+1$, $k\geq0$, reads
\begin{eqnarray}
T_q^{k+1} - t_q^{R,k} &\leq& \pi_0^- +
(k+1)\Bigl(2u_{\max}^- + G + \varepsilon_{\max}^-\nonumber\\
&&+ (P+\Gamma_{\max}-\Gamma_{\min}-\delta_{\min})\rho_{\max}^- \nonumber\\
&&+ {\cal O}(P\rho_{\max}^2 + G\rho_{\max} +
\varepsilon_{\max}\rho_{\max})\Bigr)\label{equ:bdettradaccurminusthmsum},\\
T_q^{k+1} - t_q^{R,k} &\geq&
-\pi_0^+ - (k+1)\Bigl(2u_{\max}^+ + \varepsilon_{\max}^+\nonumber\\
&&+ (P+\Gamma_{\max}-\Gamma_{\min}-\delta_{\min})\rho_{\max}^+ \nonumber\\
&&+ {\cal O}(P\rho_{\max}^2 + G\rho_{\max} +
\varepsilon_{\max}\rho_{\max})\Bigr)\label{equ:bdettradaccurplusthmsum},
\end{eqnarray}
where $\pi_0^-$ and $\pi_0^+$ are given by (\ref{equ:algpi0m}) and
(\ref{equ:algpi0p}), respectively.
\\
\noindent{(3) } The inverse rate
$r_{q}=\lim_{k\to\infty}\frac{t_q^{R,k}-t_q^0}{T_q^{k+1} -
T_q^0}$, where $T_q^0=C_q(t_q^0)$ is node~$q$'s local time at the
beginning of round~$k=0$, of the synchronized clock at node~$q$ lies within
\[
\left[1\pm\left(\B{\rho}_{\max} + \frac{
2 \B{u}_{\max} + \overline{\B{G}} + \B{\varepsilon}_{\max}+
(\Gamma_{\max}-\Gamma_{\min}-\delta_{\min})\B{\rho}_{\max}}{P}\right.\right.
\]
\begin{equation}
+{\cal O}(P\rho_{\max} + G +
\varepsilon_{\max})\B{\rho}_{\max}\Bigg)
\Bigg]\label{equ:globrateOA}.
\end{equation}
\end{thm}
\noindent
{\bf Proof\,} We showed in the proof of Theorem~\ref{thm:precOA}
that $\B{\pi}^H$ given by (\ref{equ:piHB}), which immediately leads to
(\ref{equ:equpiH}), is a symmetric interval, hence
$\pi^{H+}/\pi^H=\pi^{H-}/\pi^H=1/2$. Since both $\pi^{H-}$ and
$\pi^{H+}$ are integer multiples of $G_S$, it follows that the error
in estimating $\lceil\pi^H/4\rceil_{G_S}$ by $\pi^H/4$ is at most
$G_S/2$ as asserted.
According to item~(0) of Theorem~\ref{thm:precandacc}, the bounds
$\beta_q^{k+1,-}$
respectively $\beta_q^{k+1,+}$ are just $\OA$'s
accuracy preservation functions $\aleph^-(\cdot)$
respectively $\aleph^+(\cdot)$
derived in item~(1) of Theorem~\ref{thm:convOAacc}: For round~$k=0$,
evaluating (\ref{equ:defjotanull}) according to the initial
synchronization assumption in item~(0) of Definition~\ref{def:OAalgorithm}
forces us to assume a zero-length common
intersection $\iota_s^{0,-}=\iota_s^{0,+}=0$ for any node~$s$.
Plugging this into (\ref{equ:fab}) respectively (\ref{equ:fabplu}) governed
by (\ref{equ:defbetak}) and using (\ref{equ:defbetakp})
provides
\begin{eqnarray}
\aleph^-(\B{\cal B}_q^1,\B{\pi}^H,\forall s:0) &=&
\max_{i:n-2\d-3\e} \{\beta_i^{0,-} + \omega_q^{i,-}\} +
\pi^{H+}\nonumber\\
& =& \max_{i:n-2\d-3\e} \{\alpha_i^{0,-} + \omega_q^{i,-}\} +
\lceil\pi^H/4\rceil_{G_S} + \lfloor\pi^H/4\rfloor_{G_S}
\nonumber\\
\aleph^+(\B{\cal B}_q^1,\B{\pi}^H,\forall s:0) &=&
\max_{i:n-2\d-3\e} \{\beta_i^{0,+} + \omega_q^{i,+}\} +
\pi^{H-}\nonumber\\
&=& \max_{i:n-2\d-3\e} \{\alpha_i^{0,+} + \omega_q^{i,+}\}\nonumber\\
&&+\lceil\pi^H/4\rceil_{G_S} + \lfloor\pi^H/4\rfloor_{G_S}\label{equ:mynull}
\end{eqnarray}
where we used $\pi^H/2 - \lceil\pi^H/4\rceil_{G_S}
= \lfloor\pi^H/4\rfloor_{G_S}$.
For round $k\geq1$, we have $\iota_s^k=\iota_s^{k,-} = \iota_s^{k,+} =
\pi_0 - \lceil\pi_I/2\rceil_{G_S}$ uniformly for any node~$s$ due
to (\ref{equ:defjotak}) respectively (\ref{equ:defjotakplu}) in conjunction
with (\ref{equ:ims}). Therefore,
\[
\frac{1}{2}(\pi^H-\iota_s^k)=
\frac{\pi^H-\pi_0+\lceil\pi_I/2\rceil_{G_S}}{2} =
\frac{\pi_1+\lceil\pi_I/2\rceil_{G_S}}{2} = \pi^H/4,
\]
where we used (\ref{equ:piHHH}). Plugging this
into (\ref{equ:fab}) respectively (\ref{equ:fabplu}) and using
(\ref{equ:defbetak}) and (\ref{equ:defbetakp}) again provides
\begin{eqnarray}
\aleph^-(\B{\cal B}_q^{k+1},\B{\pi}^H,\forall s:\iota_s^{k,-}) &=&
\max_{i:n-2\d-3\e} \{\beta_i^{k,-} + \omega_q^{i,-}\} +
\lfloor\pi^H/4\rfloor_{G_S}\nonumber\\
\aleph^+(\B{\cal B}_q^{k+1},\B{\pi}^H,\forall s:\iota_s^{k,+}) &=&
\max_{i:n-2\d-3\e} \{\beta_i^{k,+} + \omega_q^{i,+}\} +
\lceil\pi^H/4\rceil_{G_S}.\label{equ:myone}
\end{eqnarray}
Replacing $i$ by $p$ and plugging in the definition of
$\B{\omega}_q^p$ given in (\ref{equ:defbetakp}) and
(\ref{equ:thmalphaqq}), expressions (\ref{equ:detaccurminusthm}) and
(\ref{equ:detaccurplusthm}) follow. Uniformly bounding the terms that
depend on $p$ by their maximum values and applying
Lemma~\ref{lem:ubmax} readily confirms (\ref{equ:bdetaccurminusthm})
and (\ref{equ:bdetaccurplusthm}); note that a certain technical
condition in \cite[(16)]{SS97:1}, namely, $\delta_{\min}\B{\rho}_{\max}
\subseteq \B{\varepsilon}_{\max}$,
ensures that the derived bound is valid for $p=q$ as well.
To justify the initial values (\ref{equ:accnullmi}) and
(\ref{equ:accnullpl}), we just note that (\ref{equ:mynull}) and
(\ref{equ:myone}) differ only by $\lfloor \pi^H/4\rfloor_{G_S}$,
which can conveniently be put into $\beta_q^{0,+}$ and
$\beta_q^{0,-}$.
Turning our attention to traditional accuracy, we first plug in
$\OA$'s precision preservation function $\B{\Phi}(\B{\pi}^H)=\B{\pi}^H$ into
(\ref{equ:tradacc}) to obtain
\begin{equation}
T_q^{k+1} - t_q^{R,k} \in \overline{\B{\pi}}_0 +
(k+1)(\overline{\B{\pi}}^H - \overline{\B{\pi}}_0);
\end{equation}
inserting the swapped expression for $\B{\pi}^H-\B{\pi}_0$
obtained from (\ref{equ:piHB})
easily yields (\ref{equ:bdettradaccurminusthmsum}) and
(\ref{equ:bdettradaccurplusthmsum}). Finally, plugging in
$\B{\pi}^H-\B{\pi}_0$ into (\ref{equ:globrate}) also justifies
expression~(\ref{equ:globrateOA}) for the inverse rate of the
synchronized clock,
completing the proof of Theorem~\ref{thm:accOA}.
$\Box$
\begin{rmm}
\pitem
OA provides the same, slightly suboptimal worst-case traditional
accuracy and drift as the FTM algorithm of
\cite{LL88}: The synchronized clocks drift away from real-time by at
most the maximum drift $\rho_{\max}$ of the (worst) physical clock
plus some smaller terms. Note that it has been proved in \cite{ST87}
that the worst-case drift cannot be better than the drift of the
physical clocks. Algorithms that are optimal in this respect have
been provided in \cite{ST87}, \cite{FC95:1}, and \cite{Sch97:op}.
\pitem
It is important to note that accuracy intervals can grow much
faster than traditional accuracy, which reveals the major weakness of
the orthogonal accuracy algorithm:
Evaluating the results of Theorem~\ref{thm:accOA} for the
simplified worst-case parameter setting
$\B{\rho}_p=\B{\rho}_{\max}:=[-\rho,\rho]$,
$\B{\varepsilon}_{pq}=\B{\varepsilon}_{\max}:=[-\varepsilon,\varepsilon]$,
$\B{u}_{\max}:=[-u,u]$,
it is obvious that $\B{\beta}_q^k=\B{\beta}^k$ is the same for any
$q$. Plugging in those settings into expression (\ref{equ:equpiH}) for $\pi^H$,
we find
\begin{eqnarray}
\pi^H/4 &=& 3\varepsilon/2 +(B+4)u/2 + 3G/4
+ G_S/4 \nonumber\\
&&+\Bigl(P+\frac{\Lambda + \Omega + \Delta + 3\Gamma_{\max} -
2\Gamma_{\min}-3\delta_{\min}}{2}\Bigr)\rho\nonumber\\
&&+{\cal O}(P\rho^2 + G\rho +
\varepsilon\rho)\nonumber,
\end{eqnarray}
and feeding everything into the formulas for negative accuracy
(\ref{equ:bdetaccurminusthm}) and positive accuracy
(\ref{equ:bdetaccurplusthm}) yields
\begin{eqnarray}
\beta^{k+1,-} &\leq& \beta^{k,-} + 5\varepsilon/2
+ (B+8)u/2 + 7G/4 + G_A +
G_S/4 \nonumber\\
&&+\bigl(2P+\Lambda/2 + \Omega/2 +
\Delta/2 + 5\Gamma_{\max}/2-2\Gamma_{\min} -
5\delta_{\min}/2\bigr)\rho\nonumber\\
&&+{\cal O}(P\rho^2+G\rho+\varepsilon\rho)\nonumber\\
\beta^{k+1,+} &\leq& \beta^{k,+} + 5\varepsilon/2
+ (B+8)u/2 + 3G/4 + G_A +
3G_S/4 \nonumber\\
&&+\bigl(2P+\Lambda/2 + \Omega/2 +
\Delta/2 + 5\Gamma_{\max}/2-2\Gamma_{\min} -
5\delta_{\min}/2\bigr)\rho\nonumber\\
&&+{\cal O}(P\rho^2+G\rho+\varepsilon\rho)\nonumber.
\end{eqnarray}
Ignoring smaller order terms, this means that both positive and
negative accuracy could possibly grow as much as $2P\rho+5\varepsilon/2$
during each round.
Plugging in the above parameter settings in
(\ref{equ:bdettradaccurminusthmsum}) respectively
(\ref{equ:bdettradaccurplusthmsum}), it turns out that traditional
accuracy can increase respectively
decrease essentially by $P\rho+\varepsilon$
during each
round. Therefore, either positive or negative accuracy could grow
more than twice as fast as traditional accuracy (although this cannot happen
simultaneously for both). Intuitively, this is due to the fact that the
reference point and any edge could move into opposite directions at
resynchronization, because faulty intervals might affect the accuracy
and precision algorithm differently. Remember that it can even happen
that the reference point is placed outside the originally computed
accuracy interval.
\pitem
There are several directions one can follow in order to devise
convergence functions that behave better with respect to the accuracy
bounds:
\begin{itemize}
\item One should consider algorithms that maintain precision
and accuracy not orthogonally but rather in an integrated way.
\item One could try to reduce the ``power'' of the precision
algorithm with respect to causing internal global time to drift from
real-time. In fact, OA enforces precision by quite radical
corrections (suboptimal maximum clock corrections $\Upsilon$, see
Remark~3 following Theorem~\ref{thm:precOA}) that are incompatible
with the progress of real-time. The {\em optimal precision convergence
function\/} $\B{\cal OP}$ analyzed in \cite{Sch97:op} shows how far one
can get with this approach.
\item There might be ways of limiting the adverse effects of faulty
clocks.
\end{itemize}
\end{rmm}
\section{Conclusions}
In this paper, we introduced and rigorously analyzed a novel
convergence function-based orthogonal accuracy clock
synchronization algorithm OA. Belonging to the class of
interval-based algorithms, it both guarantees bounded
internal synchronization precision and provides on-line bounds on
the instantaneous accuracy with respect to external time as well. OA
employs the orthogonal accuracy convergence function $\OA$ in
the generic algorithm of \cite{SS97:1}, which encodes two (almost)
independent algorithms for maintaining precision and accuracy based
on the Marzullo function ${\M}$.
Our comprehensive analysis utilized the powerful
interval-based framework established in \cite{SS97:1}. Based upon a
thorough investigation of the worst-case performance
of $\M$, we provided accurate expressions for all worst-case
performance measures, like precision, maximum clock correction,
accuracy, etc. With respect to worst-case precision, it turned out
that OA performs equivalent to the well-known {\em fault-tolerant
midpoint\/} (FTM) algorithm of
\cite{LL88}: Maximum precision $5\varepsilon + 4P\rho$, maximum clock
correction $5\varepsilon + 4P\rho$, and global drift $\rho$ +
smaller terms are hence all slightly sub-optimal.
The major weakness of OA lies in the fact that its worst
case accuracy bounds could grow by $2P\rho+5\varepsilon/2$ during
each round, which is more than twice the worst-case
growth $P\rho+\varepsilon$
of actual (traditional) accuracy.
A general advantage of our results over traditional ones is that
they are suitable for very high-accuracy clock synchronization as
well. This is primarily a consequence of a very detailed system
model, which incorporates several non-standard issues like non-zero
clock granularity and broadcast latencies. An novel perception-based
hybrid fault model covering arbitrary and restricted
node and link faults is also utilized; among its particular
strengths is proper modeling of independent receive omissions.
The most important fact revealed by our detailed formulas is that clock
granularity ($G$) and, in particular, rate adjustment uncertainty
(usually $u=G/m$, for some small positive integer $m$) of discrete
rate-adjustment techniques have a considerable impact (as much as $12
u + 4 G$) upon achievable worst-case precision and accuracy. This
makes clear that any attempt to approach $1~\mu s$ worst-case
precision ---as targeted by our SynUTC-project, see
\cite{SKMNCK99}--- must utilize clocks with $G, u \ll 1 \mu s$.
Future work in this area will primarily be devoted to an improvement
of the definitely sub-optimal accuracy interval of any orthogonal
accuracy algorithm. We are currently looking at a promising candidate
algorithm that maintains precision and accuracy in an integrated way,
which will hopefully provide considerably improved accuracy bounds.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Appendices
\section*{Appendix A: Technical Lemmas}
\begin{lem}[Properties of Discrete Reference Point
Setting]\label{lem:accrefset}
Let $\B{I}=[a,b]$ with $0\leq a\leq b$ being integer multiples of
$G_S>0$ and an
arbitrary interval $\B{\pi}=[-\pi^-,\pi^+]$ with $\pi=\pi^-+\pi^+>0$
be given. Then,
\begin{equation}
\mbox{$\B{\pi}$-center}_{G_S}([a,b]) \leq
\mbox{$\B{\pi}$-center}_{G_S}([a+x,b+y]) \label{equ:monpice}
\end{equation}
for any $x, y \geq0$ being integer multiples of $G_S$, and
the accuracies in the interval $[r\pm\B{\alpha}]$ obtained from $\B{I}$ by
setting the reference point to
$r=\mbox{$\B{\pi}$-center}_{G_S}(\B{I})$ satisfy
\begin{eqnarray}
\alpha^- &=& \Bigl\lfloor
\frac{\pi^-}{\pi}|\B{I}|\Bigr\rfloor_{G_S},\label{equ:almi}\\
\alpha^+ &=& \Bigl\lceil
\frac{\pi^+}{\pi}|\B{I}|\Bigr\rceil_{G_S}.\label{equ:alplu}
\end{eqnarray}
\end{lem}
\noindent
{\bf Proof\,} Monotonicity (\ref{equ:monpice}) follows immediately
from the definition (\ref{equ:defcent}) of
$\mbox{$\B{\pi}$-center}_{G_S}$ and monotonicity of $\lfloor x \rfloor$.
The expressions for positive and negative accuracy yield
\[
\alpha^- = \Bigl\lfloor \frac{\pi^-b +
\pi^+a}{\pi}\Bigr\rfloor_{G_S} - a = \Bigl\lfloor \frac{\pi^-b
+ \pi^+a - \pi a}{\pi}\Bigr\rfloor_{G_S} =
\Bigl\lfloor
\frac{\pi^-}{\pi}|\B{I}|\Bigr\rfloor_{G_S}
\]
and
\[
\alpha^+ = b - \Bigl\lfloor \frac{\pi^-b +
\pi^+a}{\pi}\Bigr\rfloor_{G_S} = b + \Bigl\lceil -\frac{\pi^-b
+ \pi^+a}{\pi}\Bigr\rceil_{G_S}
%= \Bigl\lceil \frac{\pi b - \pi^-b - \pi^+a }{\pi}\Bigr\rceil_{G_S}
=\Bigl\lceil \frac{\pi^+}{\pi}|\B{I}|\Bigr\rceil_{G_S},
\]
where we used the well-known fact $-\lceil x \rceil = \lfloor -x
\rfloor$ (see, for example~\cite[Sec.~1.2.4, Ex.~4]{Knu73}). $\Box$
\begin{lem}[Precision Enhancement]\label{lem:precenh}
Let $\B{I}_p$, $\B{I}_q$ be two consistent intervals with
length $0\leq|\B{I}_p|\leq \opi_p$, $0\leq|\B{I}_q|\leq \opi_q$ being
integer multiples of $G_S$, and
$\mbox{ref}(\B{I}_p)=\mbox{$\B{\pi}_p$-center}_{G_S}(\B{I}_p)$,
$\mbox{ref}(\B{I}_q)=\mbox{$\B{\pi}_q$-center}_{G_S}(\B{I}_q)$ for some
$\B{\pi}_p=[-\pi_p^-,\pi_p^+]$ and $\B{\pi}_q=[-\pi_q^-,\pi_q^+]$. If
$|\B{I}_p\nccup \B{I}_q|\leq \pi$ with
$\max\{\opi_p,\opi_q\}\leq\pi\leq \opi_p+\opi_q$, then
\[
|\mbox{ref}(\B{I}_p)-\mbox{ref}(\B{I}_q)|
\leq
\]
\[
\leq
\left\{ \begin{array}{ll}
\max\Bigl\{\Bigl\lceil\frac{\pi_q^-}{\pi_q}\opi_q+\frac{\pi_p^+}{\pi_p}(\pi-\opi_q)\Bigr\rceil_{G_S},
\Bigl\lceil\frac{\pi_p^-}{\pi_p}\opi_p+\frac{\pi_q^+}{\pi_q}(\pi-\opi_p)\Bigr\rceil_{G_S}
\Bigr\} & \mbox{if $\frac{\pi_q^-}{\pi_q} \geq \frac{\pi_p^+}{\pi_p}$,}\\
\max\Bigl\{\Bigl\lceil\frac{\pi_p^+}{\pi_p}\opi_p+\frac{\pi_q^-}{\pi_q}(\pi-\opi_p)\Bigr\rceil_{G_S},
\Bigl\lceil\frac{\pi_q^+}{\pi_q}\opi_q+\frac{\pi_p^-}{\pi_p}(\pi-\opi_q)\Bigr\rceil_{G_S}
\Bigr\} & \mbox{otherwise.}
\end{array} \right.
\]
\end{lem}
\noindent
{\bf Proof\,} Apart from discreteness of
$\mbox{$\B{\pi}_p$-center}_{G_S}$, this is a straightforward linear
programming problem. One has
to look out for an arrangement of the consistent intervals $\B{I}_p=[a,b]$
and $\B{I}_q=[c,d]$ that maximizes the distance of their reference points.
More specifically, recalling the definition of $\mbox{$\B{\pi}$-center}_{G_S}$
(Definition~\ref{def:refset}), we are interested in
\begin{equation}
u=\min\Bigl\{\Bigl\lfloor\frac{\pi_p^+a+\pi_p^-b}{\pi_p}\Bigr\rfloor_{G_S} -
\Bigl\lfloor\frac{\pi_q^+c+\pi_q^-d}{\pi_q}\Bigr\rfloor_{G_S}\Bigr\}\label{equ:minim}
\end{equation}
subject to
$b-a \leq \opi_p$,
$a-b \leq 0$,
$d-c \leq \opi_q$,
$c-d \leq 0$,
$b \leq \pi$,
$d \leq \pi$,
$c \leq b$,
$a \leq d$,
where $a,b,c,d \geq 0$ are integer multiples of $G_S$. Note
that (\ref{equ:minim}) covers
arrangements where $\mbox{ref}(\B{I}_p)\leq
\mbox{ref}(\B{I}_q)$ only; minimizing provides the maximum distance
for negative values only. However, since the problem is symmetric in
$p$ and $q$, the maximum value for reverse arrangements follows
immediately by exchanging $p$ and $q$.
Fortunately, it is not difficult to identify the worst-case scenario.
Ignoring discreteness for the moment, that is, assuming $G_S=0$, if
\begin{equation}
\frac{\pi_q^-}{\pi_q} \geq \frac{\pi_p^+}{\pi_p},\label{equ:condit}
\end{equation}
the maximum distance of the reference points occurs
when $\B{I}_q$ is made as large as possible, that is,
$|\B{I}_q|=\opi_q$,
leaving at most $|\B{I}_p|=\pi-\opi_q$ for $\B{I}_p$; recall
that we assumed $\pi \leq \opi_p+\opi_q$.
Returning to the discrete case, this suggests that the minimum value
of (\ref{equ:minim}) satisfies
\begin{equation}
-u =
\Bigl\lceil\frac{\pi_p^+}{\pi_p}\lfloor\pi-\opi_q\rfloor_{G_S}
\Bigr\rceil_{G_S}+\lfloor\frac{\pi_q^-}{\pi_q}\opi_q\rfloor_{G_S}
\leq\Bigl\lceil\frac{\pi_p^+}{\pi_p}(\pi-\opi_q)+\frac{\pi_q^-}{\pi_q}\opi_q\Bigr\rceil_{G_S},
\label{equ:soluq}
\end{equation}
recall Lemma~\ref{lem:accrefset}; the upper bound follows easily from
moving the second term into the first one and then omitting
$\lfloor\cdot\rfloor_{G_S}$.
However, we have to confirm that discreteness of
$\mbox{$\B{\pi}$-center}_{G_S}$ does not impose a different
maximum value. More specifically, we have to show that ---starting from
(\ref{equ:soluq})--- shrinking $|\B{I}_q|=\opi_q$ by $k G_S$
for some integer $k\geq0$ and simultaneously enlarging
$|\B{I}_p|=\lfloor\pi-\opi_q\rfloor_{G_S}
\leq \pi-\opi_q$ by the same amount does not lead to a larger
value of $-u$. For any $k\geq0$, we find
\begin{eqnarray}
-u(k) &=&
\Bigl\lceil\frac{\pi_p^+}{\pi_p}(\lfloor\pi-\opi_q\rfloor_{G_S}+k
G_S)\Bigr\rceil_{G_S}
+ \Bigl\lfloor
\frac{\pi_q^-}{\pi_q}(\opi_q-k G_S)\Bigr\rfloor_{G_S}\nonumber\\
&\leq&
\Bigl\lceil\frac{\pi_p^+}{\pi_p}(\lfloor\pi-\opi_q\rfloor_{G_S}+k G_S)
+ \frac{\pi_q^-}{\pi_q}(\opi_q-k G_S)\Bigr\rceil_{G_S}\nonumber\\
&\leq&
\Bigl\lceil\frac{\pi_p^+}{\pi_p}\lfloor\pi-\opi_q\rfloor_{G_S}
+\frac{\pi_q^-}{\pi_q}\opi_q\Bigr\rceil_{G_S},\label{equ:res1}
\end{eqnarray}
by virtue of condition~(\ref{equ:condit}), thus confirming our
conjecture (\ref{equ:soluq}).
If, on the other hand, condition~(\ref{equ:condit}) is not true,
the minimum (considering $G_S=0$ first) occurs when $\B{I}_p$ is made as
large as possible, providing the value
\begin{equation}
-u' = \frac{\pi_p^+}{\pi_p}\opi_p+\frac{\pi_q^-}{\pi_q}(\pi-\opi_p).
\end{equation}
As before, this suggests the minimum value
\begin{equation}
-u' =
\lceil\frac{\pi_p^+}{\pi_p}\opi_p\rceil_{G_S}
+\Bigl\lfloor\frac{\pi_q^-}{\pi_q}\lfloor\pi-
\opi_p\rfloor_{G_S}\Bigr\rfloor_{G_S}
\leq
\Bigl\lceil\frac{\pi_p^+}{\pi_p}\opi_p
+\frac{\pi_q^-}{\pi_q}(\pi-\opi_p)\Bigr\rceil_{G_S}
\label{equ:solup}
\end{equation}
for the discrete case. For any $k\geq0$, we find
\begin{eqnarray*}
-u'(k)&=& \Bigl\lceil\frac{\pi_p^+}{\pi_p}(\opi_p-k G_S)\Bigr\rceil_{G_S}
+ \Bigl\lfloor
\frac{\pi_q^-}{\pi_q}(\lfloor\pi
-\opi_p\rfloor_{G_S}+k G_S)\Bigr\rfloor_{G_S}\nonumber\\
&\leq&
\Bigl\lceil\frac{\pi_p^+}{\pi_p}(\opi_p-k G_S)
+ \frac{\pi_q^-}{\pi_q}(\lfloor\pi -\opi_p\rfloor_{G_S}+k
G_S)\Bigr\rceil_{G_S}\nonumber\\
&\leq&
\Bigl\lceil\frac{\pi_p^+}{\pi_p}\opi_p
+ \frac{\pi_q^-}{\pi_q}\lfloor\pi -\opi_p\rfloor_{G_S}
\Bigr\rceil_{G_S},\nonumber\\
\end{eqnarray*}
which also confirms (\ref{equ:solup}) and completes the case of
arrangements $\mbox{ref}(\B{I}_p) \leq \mbox{ref}(\B{I}_q)$.
To establish the result for reverse arrangements, we
only have to exchange $p$ and $q$. Rewriting condition (\ref{equ:condit})
appropriately reads
\[
\frac{\pi_p^-}{\pi_p} = 1 - \frac{\pi_p^+}{\pi_p} \geq
1 - \frac{\pi_q^-}{\pi_q} = \frac{\pi_q^+}{\pi_q},
\]
which is fulfilled if and only if (\ref{equ:condit}) is satisfied. Exchanging $p$ and
$q$ in (\ref{equ:soluq}) and (\ref{equ:solup}) and taking the
maximum of the appropriate values eventually completes the proof of
the lemma. $\Box$
\begin{lem}[Uniform Bounds $m$-Maxima]\label{lem:ubmax} Let ${\cal S}=\{z_i\}_{1\leq i
\leq n}$ with $z_i=x_i+y_i$ and $y$ be given, such that $x_i\leq x_j$
for $i0$, and by the initial synchronization assumption in
Definition~\ref{def:OAalgorithm} for round~$k=0$.
It only remains to confirm that the precision intervals associated
with any (non-faulty) $\B{I}_p^s$ and $\B{I}_q^s$ ---fed into the
convergence function at node~$p$ and~$q$--- have a mutual
intersection with either $\B{I}_p^{\min_p}$ and $\B{I}_q^{\min_q}$ of
length at least $\iota_s^+$ as well. However, the drift and delay
compensation operations used to obtain round~$k$'s $\B{I}_x^s$ from
$\B{A}_s^k$ have been explicitly
designed to preserve accurateness, so they must preserve any initial
mutual intersection. Hence, choosing $\iota_q^{k+1,+}$ and
$\iota_q^{k+1,-}$ according to
(\ref{equ:defjotak})--(\ref{equ:defjotanull}) is legitimate.
Turning our attention to item~(4), we know that $\B{A}_q^{k+1}$ is
$\B{\Phi}(\B{\cal P}_q,\B{\pi}^H,\B{\pi}_I)$-correct
with respect to $\tau^k$
by virtue of item~(2) of Definition~\ref{def:charconv} and hence
$\B{\Phi}$-correct. Note that $\B{\Phi}\subseteq\B{\Phi}(\B{\cal
P},\B{\pi}^H,\B{\pi}_I)$
is a simple consequence of monotonicity of $\B{\Phi}(\cdot)$.
Moreover, from item~(3) of Definition~\ref{def:charconv},
it follows that all $\B{A}_p^{k+1}$ are $\B{\pi}_0$-precise. Hence it is
possible to choose $\tau^{k+1}\in \bigcap_p
\ppI{\B{A}}_p^{k+1}$, as justified by Definition~\ref{def:ivprec}, and
we claim that we may in fact choose
$\tau^{k+1}$ so that
\[
-(\Phi^+ - \pi_0^+) \leq \tau^{k+1}-\tau^{k} \leq
\Phi^- - \pi_0^-.
\]
If this was not feasible,
there would exist an interval $\ppI{\B{A}}_r^{k+1}$ of length $\pi_0$
with $\tau^{k+1}=\mbox{left}(\ppI{\B{A}}_r^{k+1})$ or else
$\tau^{k+1}=\mbox{right}(\ppI{\B{A}}_r^{k+1})$ that satisfies
$\tau^k \not\in \ppI{\B{A}}_r^{k+1}+(\B{\Phi} -
\B{\pi}_0)=\B{\Phi}$. This, however, would contradict
$\B{\Phi}$-correctness of $\B{A}_r^{k+1}$.
The bound (\ref{equ:tradacc}) is a simple consequence of the fact
that internal global time progresses as real-time does during a
round, so that the maximum deviation between internal global time and
real-time remains the same during any round. Therefore, we just have to
add up the worst-case internal global time ``jumps'' at each round.
The initial deviation (in round~$0$) is zero since choosing
$\tau^0(t)=t$ is legitimate due to the initial synchronization
assumption in Definition~\ref{def:OAalgorithm}. Hence, to complete
the proof of (\ref{equ:tradacc}), it only remains to add the
maximum deviation between $\tau^{k+1}$ and the reference point
$T_q^{k+1}$ of $\B{A}_q^{k+1}$, which is trivial since the latter is
$\B{\pi}_0$-correct.
To derive expression (\ref{equ:globrate}) for the rate of the
synchronized clocks, we multiply (\ref{equ:tradacc}) by -1 to arrive
at
\begin{equation}
t_q^{R,k} - t_q^0 \in T_q^{k+1} - T_q^0 - (t_q^0 - T_q^0) + \B{\pi}_0
+ (k+1) \bigl(\B{\Phi}-\B{\pi}_0\bigr).\label{equ:glrat}
\end{equation}
>From the initial synchronization assumptions in item~(0) of
Definition~\ref{def:OAalgorithm}, we gather $t_q^0 - T_q^0 \in
\B{\alpha}_q^0 \subseteq \B{\pi}_0$. Moreover, from step~(T) of the
algorithm in conjunction with the fact that the maximum clock
adjustment was shown to satisfy $\Upsilon_q\in\B{\pi}$ in item~(3) of
this theorem, we obtain $T_q^{k+1}-T_q^0 = (k+1)P + {\cal O}(\pi)$.
Plugging this into (\ref{equ:glrat}), we find
\[
\frac{t_q^{R,k}-t_q^0}{T_q^{k+1} -
T_q^0} \in 1 + \frac{[-\pi_0,\pi_0] + (k+1)
\bigl(\B{\Phi}-\B{\pi}_0\bigr) }{(k+1)P + {\cal O}(\pi) }.
\]
Taking the limit for $k\to\infty$ eventually provides
(\ref{equ:globrate}) and completes the proof of our theorem. $\Box$
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% begin structure picture
\newpage
\unitlength=0.790mm
\special{em:linewidth 0.4pt}
\linethickness{0.4pt}
\begin{picture}(165.00,232.00)
\put(0.00,216.00){\makebox(0,0)[lb]{{\scriptsize\bf Basics}
\scriptsize\bf (Sec.~\ref{sec:2})}}
\put(5.00,209.00){\makebox(0,0)[lb]{\scriptsize Def.~\refp{def:ivrels}: Interval relations}}
\put(5.00,204.00){\makebox(0,0)[lb]{\scriptsize Def.~\refp{def:ivprec}: Precision intervals}}
\put(5.00,199.00){\makebox(0,0)[lb]{\scriptsize Def.~\refp{def:picorrness}: $\B{\pi}$-correctness}}
\put(5.00,194.00){\makebox(0,0)[lb]{\scriptsize Lem.~\refp{lem:corpiprec}: $\B{\pi}$-prec. vs. prec.}}
\put(0.00,192.00){\framebox(65.00,21.00)[cc]{}}
\put(85.00,232.00){\makebox(0,0)[lb]{{\scriptsize\bf Fault Model}
\scriptsize\bf (Sec.~\ref{Fault Model})}}
\put(90.00,225.00){\makebox(0,0)[lb]{\scriptsize Def.~\refp{def:classfaults}: Single faults}}
\put(90.00,220.00){\makebox(0,0)[lb]{\scriptsize Def.~\refp{def:pairfaultiv}: Pairwise faults}}
\put(90.00,215.00){\makebox(0,0)[lb]{\scriptsize Asum.~\refp{asum:faultmodel}: Hybrid fault model}}
\put(85.00,192.00){\makebox(0,0)[lb]{{\scriptsize\bf Marzullo's Function}
\scriptsize\bf (Sec.~\ref{Marzullo Function})}}
\put(90.00,185.00){\makebox(0,0)[lb]{\scriptsize Def.~\refp{def:M}: Marzullo function}}
\put(90.00,180.00){\makebox(0,0)[lb]{\scriptsize Lem.~\refp{lem:accM}: Accuracy $\M$}}
\put(90.00,175.00){\makebox(0,0)[lb]{\scriptsize Lem.~\refp{lem:monotonicityM}: Monotonicity $\M$}}
\put(90.00,170.00){\makebox(0,0)[lb]{\scriptsize Lem.~\refp{lem:precM}: Precision $\M$}}
\put(90.00,165.00){\makebox(0,0)[lb]{\scriptsize Lem.~\refp{lem:degradeM}: Graceful degrad.}}
\put(85.00,137.00){\makebox(0,0)[lb]{{\scriptsize\bf $\OA$ Conv. Function}
\scriptsize\bf (Sec.~\ref{Orthogonal Accuracy Convergence Function}, App.~C)}}
\put(90.00,130.00){\makebox(0,0)[lb]{\scriptsize Def.~\refp{def:refset}: $\B{\pi}$-center}}
\put(90.00,125.00){\makebox(0,0)[lb]{\scriptsize Def.~\refp{def:OA}: Conv. function $\OA$}}
\put(90.00,120.00){\makebox(0,0)[lb]{\scriptsize Lem.~\refp{lem:accrefset}: Properties $\B{\pi}$-center}}
\put(90.00,115.00){\makebox(0,0)[lb]{\scriptsize Lem.~\refp{lem:precenh}: Precision enhancement}}
\put(90.00,110.00){\makebox(0,0)[lb]{\scriptsize Thm.~\refp{thm:convOAprec}: Precision properties $\OA$}}
\put(90.00,105.00){\makebox(0,0)[lb]{\scriptsize Thm.~\refp{thm:convOAacc}: Accuracy properties $\OA$}}
\put(0.00,128.00){\makebox(0,0)[lb]{{\scriptsize\bf Generic Conv. Function}
\scriptsize\bf (App.~C)}}
\put(5.00,116.00){\makebox(0,0)[lb]{\scriptsize Def.~\refp{def:charconv}: Generic $\CV$}}
\put(0.00,109.00){\framebox(65.00,16.00)[cc]{}}
\put(0.00,77.00){\makebox(0,0)[lb]{{\scriptsize\bf Generic Alg.\ \& Analysis}
\scriptsize\bf (App.~B \& C)}}
\put(5.00,70.00){\makebox(0,0)[lb]{\scriptsize Def.~\refp{def:OAalgorithm}: Generic algorithm}}
\put(5.00,65.00){\makebox(0,0)[lb]{\scriptsize Thm.~\refp{thm:precandacc}: Instant.\ correct.}}
\put(0.00,63.00){\framebox(65.00,11.00)[cc]{}}
\put(85.00,82.00){\makebox(0,0)[lb]{{\scriptsize\bf OA Algorithm \& Analysis}
\scriptsize\bf (Sec.~\ref{Orthogonal Accuracy Algorithm})}}
\put(90.00,70.00){\makebox(0,0)[lb]{\scriptsize Thm.~\refp{thm:precOA}: Precision OA}}
\put(90.00,65.00){\makebox(0,0)[lb]{\scriptsize Thm.~\refp{thm:accOA}: Accuracy OA}}
\put(0.00,37.00){\makebox(0,0)[lb]{{\scriptsize\bf System Model}
\scriptsize\bf (\cite{SS97:1}, App.~B)}}
\put(5.00,30.00){\makebox(0,0)[lb]{\scriptsize \cite[Assum.~1]{SS97:1}: Exec. times}}
\put(5.00,25.00){\makebox(0,0)[lb]{\scriptsize \cite[Assum.~2]{SS97:1}: Local clocks}}
\put(5.00,20.00){\makebox(0,0)[lb]{\scriptsize \cite[Assum.~3]{SS97:1}: Interval clocks}}
\put(5.00,15.00){\makebox(0,0)[lb]{\scriptsize \cite[Assum.~4]{SS97:1}: Transm. char.}}
\put(0.00,13.00){\framebox(65.00,21.00)[cc]{}}
\put(85.00,58.00){\framebox(80.00,21.00)[cc]{}}
\put(85.00,102.00){\framebox(80.00,32.00)[cc]{}}
\put(85.00,213.00){\framebox(80.00,16.00)[cc]{}}
\put(85.00,163.00){\framebox(65.00,26.00)[cc]{}}
\put(124.00,102.00){\vector(0,-1){14.00}}
\put(31.00,41.00){\vector(0,1){22.00}}
\put(31.00,109.00){\vector(0,-1){28.00}}
\put(118.00,163.00){\vector(0,-1){22.00}}
\put(118.00,213.00){\vector(0,-1){17.00}}
\put(158.00,213.00){\vector(0,-1){72.00}}
\put(50.00,192.00){\vector(1,-1){51.00}}
\put(31.00,1.00){\makebox(0,0)[cc]{\bf Generic Analysis (\cite{SS97:1})}}
\put(124.00,1.00){\makebox(0,0)[cc]{\bf Orthogonal Accuracy Analysis}}
\put(31.00,192.00){\vector(0,-1){59.00}}
\put(0.00,232.00){\makebox(0,0)[lb]{\large\bf Overview of the Analysis}}
\end{picture}
% end structure picture
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Acknowledgments}
I am indebted to Klaus Schossmaier for his valuable comments on
the many versions of this paper. A long list of enhancements was also
provided by the anonymous referees, which greatly helped me to
improve the exposition of the analysis. Their considerable efforts
spent on scrutinizing the long manuscript are gratefully acknowledged.
\subsection*{Acknowledgment of support}
This research is part of
our project SynUTC ({\em http://www.auto.tuwien.ac.at/
Projects/SynUTC/\/}),
which has been supported by the
Austrian Science Foundation (FWF)
under grant no.~P10244-\"OMA and
the Austrian START programme
Y41-MAT.
\bibliographystyle{alpha}
\bibliography{cj00-03}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% begin glossary
\newpage
\centerline{\large\bf Glossary}
{\small
\begin{center}
\begin{tabular}{p{0.28\textwidth}p{0.56\textwidth}r}
{\bf Name} & {\bf Meaning} & {\bf Page} \\
$\aleph^+(\cdot)$, $\aleph^-(\cdot)$ & accuracy preservation function
& \pageref{def:charconv}\\
$\B{\alpha}=[-\alpha^-,\alpha^+]$ & interval of accuracies of
$\B{I}=[r\pm\B{\alpha}]$& \pageref{pag:accuriv} \\
$\alpha=\alpha^-+\alpha^+$ & length of $\B{\alpha}$ & \pageref{pag:accuriv}\\
$\B{\alpha}^0_p=[-\alpha_p^{0-},\alpha_p^{0+}]$ & initial accuracies at
node $p$ & \pageref{def:OAalgorithm}\\
$C(t), C_p(t)$ & ordinary clock (node $p$) & \pageref{pag:clock}\\
$\B{C}_p(t)=[C_p(t)\pm\B{\alpha}_p(t)]$ & local interval clock of node
$p$ & \pageref{pag:clock}\\
$\delta_{\max}, \delta_{\min}$ & uniform bounds on transmission
delay characteristics & \pageref{def:OAalgorithm}\\
$\Delta$ & transmission delay compensation & \pageref{def:OAalgorithm}\\
$\B{\varepsilon}_{\max}$
& maximum transmission delay uncertainty & \pageref{def:OAalgorithm}\\
$\e$ & number of asymmetric respectively arbitrary faults
& \pageref{asum:faultmodel} \\
$\c$ & number of crash faults & \pageref{lem:precM} \\
$\d$ & number of symmetric respectively simple faults
& \pageref{asum:faultmodel} \\
$\a$ & number of unbounded accuracy faults & \pageref{lem:accM} \\
$G$ & clock granularity & \pageref{def:OAalgorithm}\\
$G_S$ & clock setting granularity & \pageref{def:OAalgorithm}\\
$\Gamma_{\max}, \Gamma_{\min}$ & uniform bounds on computational delay
characteristics & \pageref{def:OAalgorithm}\\
$\Im_-(\cdot)$, $\Im_+(\cdot)$ & intersection enhancement function &
\pageref{def:charconv}\\
$\B{I}$, $\B{A}$ & (accuracy) intervals & \pageref{pag:intervals} \\
$\overline{\B{I}}$ & swapped interval $[r\mp\B{\alpha}]$ &
\pageref{eq:swapintv}\\
$\ppI{\B{I}}$ & $\B{\pi}$-precision interval associated with $\B{I}$
& \pageref{def:ivprec}\\
$\B{\cal I}_p$ & ordered set received intervals at $p$ & \pageref{def:OAalgorithm}\\
$\Lambda_{\max}$ & logical time maximum broadcast latency
& \pageref{def:OAalgorithm}\\
$\M$ & Marzullo's function & \pageref{def:M}\\
$\max_{i:m}\{s_i\}$ & $m$-th largest element among $\{s_i\}$ &
\pageref{thm:convOAacc}\\
$n$ & number of nodes & \pageref{pag:noden}\\
$\omega_{\max}$ & logical time maximum broadcast oper.\ delay &
\pageref{def:OAalgorithm}\\
$\OA$ & orthogonal accuracy convergence function & \pageref{def:OA}\\
$P$ & round period & \pageref{def:OAalgorithm}\\
$\B{\Phi}(\cdot)$ & precision preservation function & \pageref{def:charconv}\\
$\B{\pi}=[-\pi^-, \pi^+]$ & (generic) interval of precision & \pageref{def:ivprec}\\
$\pi=\pi^-+\pi^+$ & length of $\B{\pi}$ & \pageref{def:ivprec}\\
$\B{\pi}_0=[-\pi_0^-,\pi_0^+]$ & ideal initial precision & \pageref{thm:precandacc}\\
$\B{\pi}^H=[-\pi^{H-},\pi^{H+}]$ & uniform precision exchanged
intervals & \pageref{thm:precandacc}\\
\end{tabular}
\end{center}
}
{\small
\begin{center}
\begin{tabular}{p{0.28\textwidth}p{0.56\textwidth}r}
$\B{\pi}_I$ & uniform precision of perceptions & \pageref{thm:precandacc}\\
$\B{\pi}$-accurate & correct with respect to $t$ and $\B{\pi}$-precise
& \pageref{def:ivprec}\\
$\B{\pi}$-center & asymmetric reference point setting & \pageref{def:refset}\\
$\B{\pi}$-correct & correct with respect to both $t$ and $\tau$
& \pageref{def:picorrness}\\
$\B{\pi}$-precise & precise interval set & \pageref{def:ivprec}\\
$\Pi(\cdot)$ & precision enhancement function & \pageref{def:charconv}\\
$\mbox{ref}(\B{I})$ & reference point of interval $\B{I}$
& \pageref{pag:refpt}\\
$\tau$, $\tau^k$ & internal global time (of round $k$)
& \pageref{def:picorrness}\\
\end{tabular}
\end{center}
}
% end glossary
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{document}