Chicago Journal of Theoretical Computer Science

The MIT Press

Volume 2000, Article 3 Orthogonal Accuracy Clock Synchronization

ISSN 1073–0486. MIT Press Journals, Five Cambridge Center, Cambridge, MA 02142-1493 USA; (617)253-2889; journals-orders@mit.edu, journals-info @mit.edu. Published one article at a time in L^{A}TEX source form on the Internet. Pagination varies from copy to copy. For more information and other articles see

• http://mitpress.mit.edu/CJTCS/

• http://www.cs.uchicago.edu/publications/cjtcs/

• ftp://mitpress.mit.edu/pub/CJTCS

• ftp://cs.uchicago.edu/pub/publications/cjtcs The Chicago Journal of Theoretical Computer Science is abstracted or indexed in Research Alert◯^{R}, SciSearch◯^{R}, Current Contents◯^{R}/Engineering Computing & Technology, and CompuMath Citation Index◯^{R}. \begin{matrix}c \\ ◯ \end{matrix}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; journals-rights@mit.edu. The 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.

Editor-in-Chief: Janos Simon

Consulting Editors: Joseph Halpern, Eric Allender, Raimund Seidel

Editors:

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ó 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

Managing Editor: Michael J. O’Donnell

Electronic Mail: chicago-journal@cs.uchicago.edu

Orthogonal Accuracy Clock Synchronization

Ulrich Schmid s@auto.tuwien.ac.at

July 31, 2000

Abstract

We present description and analysis of a novel 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 [SS97a] 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 worstcase performance as the well-known fault-tolerant midpoint algorithm of [LWL88]. 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.

1 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 ([Lis93]). In addition, since time rules daily life and hence most commercial computer applications, a welldefined relation between system time and external standard time 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 [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 [Sch97b].

Among those is our research on clock validation introduced in [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^{1} 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 [Mar84] and further exploited in [Lam87], [Mar90], [OSF92], [Sch95], [Mil95], [BI96], [SS97a], [Sch97c], 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.

1Our experimental evaluation ([HS97]) of the failures of six different GPS timing receivers revealed an average error probability of about 10^{−6}, with several different failure modes.

In [SS97a], 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 [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 orthogonal accuracy algorithm OA obtained by employing the orthogonal accuracy convergence function OA in the generic algorithm of [SS97a]. It is organized as follows: Section 2 introduces our interval-based clock synchronization framework, including the generic algorithm (Subsection 2.1 and Appendix B), the generic precision analysis (Subsection 2.2 and Appendix C), and the perception-based hybrid fault model (Subsection 2.3). Section 3 is devoted to an in-depth investigation of Marzullo’s function M, which plays a central role in the analysis of 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.

2 Interval-based Clock Synchronization

The core idea of the interval-based paradigm introduced in [Mar84] is to represent real-time (= external time) t not just by a time-dependent local clock value C(t), but rather by a local interval clock C(t) = [C(t) − α^{−}(t), C(t) + α^{+}(t)]. Any C(t) must be maintained appropriately to secure the accurateness property t ∈ C(t), which is of course increasingly meaningful if α(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 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 ± 150 ns”, see [Dan97], [HS97] for more information.

Interval clock readings A = [T − α^{−}, T + α^{+}] = [T ± α] taken at some fixed real-time t_{0}, that is, A = C(t_{0}), as well as intervals derived from those by means of the basic operations introduced in Subsection 2.1, are called accuracy intervals. They are the basic units of information processed by interval-based clock synchronization algorithms and disseminated via messages, and consist of A’s reference point (logical time^{2}) T and its interval of accuracies α taken relatively to the reference point. Note carefully that, given some A = [T ±α] representing real-time t, we can never assume T = t, and not even t ∈ A if A is not accurate, that is, faulty.

2.1 Generic Algorithm

The system model of [SS97a] assumes a distributed system consisting of n nodes, which communicate with each other by message passing over a fully connected point-to-point or broadcast network. Each node is equipped with a processor (with integer arithmetic only) for executing the clock synchronization algorithm, a network interface, and a local interval clock C_{p}(t) that continuously displays p’s local accuracy interval. Consult [SKM^{+}00] for details of an advanced prototype implementation based upon our Network Time Interface M-Module.

An interval-based clock synchronization algorithm is in charge of maintaining C_{p}(t) in a way that secures the following properties:

(P) Precision requirement: There is some fixed precision π_{max} ≥ 0 such that |C_{p}(t) − C_{q}(t)| ≤ π_{max} for all nodes p, q that are non-faulty up to real-time t.

(A) Accuracy requirement: The interval of accuracies α_{p}(t) is such that −α_{p}^{+}(t) ≤ C_{p}(t) − t ≤ α_{p}^{−}(t) for all nodes p that are non-faulty up to real-time t.

2Note 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.

Note that we restrict our attention to α_{p}^{+}(t), α_{p}^{−}(t) = O(t), with the implied constant^{3} 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) ≡ 0 (see [DHS86]).

The generic interval-based clock synchronization algorithm of [SS97a] (restated as Definition 9 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 ≥ 1:

1. Initiation of a full message exchange (FME) to provide each node with the accuracy intervals of all other nodes in the system.

2. Preprocessing of the set of received accuracy intervals to make them all “compatible”, that is, represent the same real-time.

3. Application of a suitable interval-valued convergence function to the set of preprocessed intervals to compute and subsequently apply a clock correction upon C_{p}(t) for resynchronization.

4. Keeping track of real-time by means of C_{p}(t) up to the next resynchronization.

The algorithm relies upon two basic operations called drift compensation and delay compensation. 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 [SS97a, Def. 5]. The following Figure 1 shows an example of drift compensated intervals based upon some initial interval A_{0} = [T_{0} ± α] representing t_{0}, which is of course assumed to be accurate (hence t_{0} ∈ 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ΔT for some fixed ΔT, i ≥ 1, leading to accuracy intervals A_{i} = A_{0} + [iΔT ± iΔT ρ]. We assume a fast but deaccelerating clock with a maximum drift ∈ [−ρ, ρ] here and ignore advanced issues like clock granularity and discrete rate adjustment uncertainty for simplicity. For accurateness, deterioration must ensure that any A_{i} intersects with the line T = t.

3Throughout this paper, we use the O(·)-notation to characterize the order of magnitude of neglected terms. An expression like α_{p}^{−}(t) = O(t) means that there is some (reasonably small) fixed constant M > 0 such that |α_{p}^{−}(t)| ≤ M|t|.

[figure: T; t; real-time T = t; T_{0} = C(t_{0}); T_{1}; T_{2}; t_{0}; t_{1}; t_{2}; T_{3} = C(t_{3}); t_{3}; [T_{0} ± α]; ΔT; ΔT; ΔT; [T_{0} ± α] + [2ΔT ± 2ΔT ρ]; (inverse) local clock; [T_{0} ± α] + [ΔT ± ΔT ρ]; [T_{0} ± α] + [3ΔT ± 3ΔT ρ]]

Figure 1: Example of drift compensation in case of a fast but deaccelerating clock with maximum drift ∈ [−ρ, ρ]. Proper deterioration ensures intersection with the line t = T.

The delay compensation operation employed in Step 2 of the algorithm maintains accurateness of intervals that are transmitted over a network experiencing variable transmission delays δ′ ∈ [δ ± ε], with δ denoting the deterministic part of the delay. As before, positive and negative accuracy must be enlarged according to [SS97a, Def. 6] to account for the maximum uncertainty in transmission delay ε. This is illustrated in Figure 2, where it is assumed that the actual transmission delay is δ′ > δ and the sender node p’s clock is drift-free, that is, progresses as real-time does.

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 A_{p} is assumed to be accurate, we must have t_{p} ∈ A_{p} here. When interpreting Figure 2, one should consider the intervals A_{p} and A_{q}^{p} as “fixed” (since they do not depend upon the actual transmission delay δ′), whereas the reception time t_{q}^{p} and hence the interval A′_{p} vary with δ′. It is apparent that t_{q}^{p} ∈ A_{q}^{p} is always maintained if t_{q}^{p} remains within the dash-boxed region of the t-axis, that is, if δ′ ∈ [δ ± ε].

Together, drift compensation and delay compensation are employed to

[figure: t; δ; δ′; ε^{−}; ε^{+}; T; T; α^{−}; α^{+}; A_{p} = [T_{p} ± α]; A′_{p} = [T′_{p} ± α]; T_{p}; T′_{p} = T_{p} + δ′; T_{q}^{p} = T_{p} + δ; A_{q}^{p} = [T_{q}^{p} ± α + ε]; node p; node q; t_{p}; t_{q}^{p}; (Sender); (Receiver); δ′; δ; ε^{−}; ε^{+}]

Figure 2: Example of delay compensation when sending I from node p to q. The received interval must be enlarged by ε to secure accurateness.

make all received intervals compatible, that is, represent a common realtime t_{q}^{R}: For an accuracy interval A_{p} sent by node p ≠ q at real-time t_{p}, delay compensation is applied to provide the receiver q with an interval A_{q}^{p} that covers the sender’s current accuracy interval at the real-time of reception t_{q}^{p}. This interval 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_{q}^{R}) = T_{q}^{R}, requiring an appropriate drift compensation to obtain the final accuracy interval I_{q}^{p}. Provided that T_{q}^{R} is chosen large enough to ensure that the intervals of all non-faulty nodes can be received and processed, it follows by construction that I_{q}^{p} is accurate if (1) A_{p} was accurate, (2) transmission delay was not excessive, and (3) the receiver q is not faulty.

Finally, a suitable convergence function is applied to the set I_{q} of node q’s intervals I_{q}^{p} in Step 3, which provides a (small) interval that both contains real-time t_{q}^{R} (that is, is accurate) and enhances precision —despite some possibly faulty 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 [SS97a] was conducted for a generic convergence function CV, which can be any interval-valued function that satisfies certain properties stated in Definition 11 in Appendix C.

2.2 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 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^{4} 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 [SS97a].

To that end, we first introduce the basic notation used throughout the paper: Our elementary objects are real intervals I = [x, y], x ≤ y, with lower edge x = left(I) and upper edge y = right(I); the empty interval ∅ satisfies ∄t : t ∈ ∅. For an interval I = [x, y], |I| = y − x denotes its length and center(I) = (x + y)/2 its centerpoint. The sum of two intervals is defined by [x, y] + [u, v] = [x + u, y + v], the scalar product by s · [x, y] = [sx, sy] for s ≥ 0, and the translation by I + a = I + [a, a] = [x + a, y + a] for some arbitrary scalar a. For two intervals [x, y], [u, v], the intersection is [x, y] ∩ [u, v] = [max{x, u}, min{y, v}] if u ≤ y, v ≥ x, and ∅ otherwise; the union reads [x, y] ∪ [u, v] = [min{x, u}, max{y, v}]. Note that the definition of the union is also valid for [x, y] ∩ [u, v] = ∅, 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] ∪ u = [x, y] ∪ [u, u]. Finally, we will need the non-commutative union (abbreviated nc-union) defined by [x, y] ⊔ [u, v] = [x, v] if x ≤ v and ∅ otherwise.

Accuracy intervals, as introduced at the beginning of this section, are intervals extended by a distinguished reference point r, which partitions the interval into a negative accuracy α^{−} and a positive accuracy α^{+} according to

A = [r ± α] = [r − α^{−}, r + α^{+}].  (1)

Herein, ref(A) = r denotes A’s reference point, α = [−α^{−}, α^{+}] its interval of accuracies, and α = |α| = α^{+} + α^{−} its length. Note that we use bold letters like A for both ordinary intervals and accuracy intervals, since its actual type is usually clear from the context. Similarly, calligraphic bold letters like A are used to denote a set of intervals or accuracy intervals.

4They are not totally independent, as the computed reference point could lie outside the accuracy interval, see Figure 6.

For accuracy intervals I = [r ± α] and J = [s ± β], we have left(I) = r − α^{−}, right(I) = r + α^{+}, |I| = α^{+} + α^{−} = α, center(I) = r + (α^{+} − α^{−})/2, I+J = [r+s±γ] where γ = α+β = [−(α^{−}+β^{−}), α^{+}+β^{+}], I+a = [r+a±α] for an arbitrary scalar a, and sI = [sr ± μ] with μ = sα = [−sα^{−}, sα^{+}] for any scalar s ≥ 0. Finally, there is also a notation to express intervals obtained from (1) by swapping positive and negative accuracy, namely

\overline{I} = \overline{[r ± α]} = [r ∓ α] = [r − α^{+}, r + α^{−}] = [r ± \overline{α}]  (2)

where \overline{α} = [−α^{+}, α^{−}] = −α.

Definition 1 (Interval Relations [SS97a, Def. 1]) Accuracy intervals are categorized as follows:

(1) Two accuracy intervals I = I(t_{1}) representing t_{1} and J = J(t_{2}) representing t_{2} are compatible if and only if t_{1} = t_{2}.

(2) Two compatible accuracy intervals I and J are consistent if and only if I ∩ J ≠ ∅.

(3) An accuracy interval I = I(t) representing real-time t is accurate if and only if t ∈ I.

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 π-precision is a key for our interval-based precision analysis. The underlying idea is to capture precision π of two clocks C_{p}(t) and C_{q}(t), that is, |C_{p}(t) − C_{q}(t)| ≤ π, by means of consistency of suitably constructed precision intervals.

Definition 2 (Precision Intervals [SS97a, Def. 2]) Given some fixed π = [−π^{−}, π^{+}] with π^{−}, π^{+} ≥ 0 and π = |π| = π^{−} + π^{+}, and a set of n ≥ 2 compatible accuracy intervals I = {I_{1}, …, I_{n}} with I_{j} = [r_{j} ± α_{j}], the πprecision interval Î_{j} associated with I_{j} is defined as Î_{j} = [r_{j} ± π]. The set I is called π-precise if and only if ⋂_{j=1}^{n} Î_{j} ≠ ∅.

Figure 3 shows two accuracy intervals along with their associated precision intervals. Note carefully that associated π-precision intervals are not maintained “online,” as are accuracy intervals, but rather computed from the reference points by adding the “static” values of −π^{−}, π^{+} 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 1 reveals that π-precision implies (traditional) precision π = |π|. Its assertions are quite trivial, as can be seen from the associated precision intervals shown in Figure 3.

Lemma 1 (π-Precision vs. Precision) Given a π-precise set I = {I_{1}, …, I_{n}} of n ≥ 2 compatible accuracy intervals I_{j} = [r_{j} ± α_{j}], then

(1) |Î_{i} ∪ Î_{j}| ≤ 2π for any 1 ≤ i, j ≤ n,

(2) |r_{i} − r_{j}| ≤ π for any 1 ≤ i, j ≤ n.

Proof See [SS97a], Lemma 3. □

Although the definition of π-precision is a key for our precision analysis, there are only a few occasions where π-precise intervals are encountered explicitly. In most cases, the slightly stronger predicate of π-accurateness (implying π-precision) is used, which is based on a suitable notion of an internal global time τ = τ(t). More specifically, it was shown in [SS97a] that it makes sense to stipulate an “artificial” internal global time τ^{k} = τ^{k}(t) = τ_{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 τ_{0}^{k} = τ^{k}(t_{0}^{k}) represents τ^{k}’s initial offset with respect to real-time. Like real-time, internal global time is not directly accessible, and usually τ^{k}(t) ≠ t. However, internal global time of any fixed round is equivalent to real-time for specifying durations, and we can unambiguously write Î = Î(t) = Î(τ^{k}) for τ^{k} = τ^{k}(t), meaning that Î represents τ^{k}(t) if and only if I represents t.

The concept of internal global time makes it possible to define an analogue to accurateness as follows.

Definition 3 (π-correctness [SS97a, Def. 3]) For π = [−π^{−}, π^{+}] with π^{−}, π^{+} ≥ 0,

(1) an accuracy interval I = I(t) is π-accurate (with respect to internal global time τ^{k} = τ^{k}(t) of round k) if and only if the π-precision interval Î = Î(τ^{k}) associated with I satisfies τ^{k} ∈ Î, (2) an accuracy interval I is π-correct (with respect to real-time and in-

ternal global time of round k) if and only if I is both π-accurate and accurate,

(3) a set I of compatible accuracy intervals is π-correct if all members are π-correct.

The following Figure 3 shows an example of two π-correct intervals.

[figure: t; τ; α_{1}^{+}; α_{2}^{+}; π^{+}; I_{1}; I_{2}; α_{1}^{−}; α_{2}^{−}; π^{−}; π^{+}; π^{−}; r_{1}; r_{2}; Î_{1}; Î_{2}]

Figure 3: Example of two π-accurate intervals. Both accuracy intervals and (bold) π-precision intervals are accurate with respect to t and τ, respectively.

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 C(t) of non-faulty interval clocks are π_{0}-correct at some real-time t^{0} in round k, that is, their associated π_{0}-precision intervals contain τ^{k}(t^{0}). In order to capture real-time t by 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′ ∈ C_{p}(t′) for t′ > t^{0}, then the associated π^{H}- precision interval Ĉ_{p}(t′) captures internal global time τ^{k}(t′) > τ^{k}(t^{0}) as well, provided that π^{H} is the result of enlarging π_{0} by the maximum amount any 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 π_{0} to π^{H} guarantees π^{H}-correctness of all non-faulty C_{p}(t′), this cannot ensure \underline{bounded} precision for t → ∞. Periodic resynchronizations are required for this purpose, giving rise to our round-based algorithm. More specifically, at the end of the kth round, the nodes’ current π^{H}-correct local interval clocks are set to newly computed accuracy intervals that are π_{0}-precise for some π_{0} ⊂ π^{H} (= precision enhancement provided by the convergence function). Note that we cannot safely assume π_{0}-correctness here, since it will usually happen that round k’s internal global time τ^{k} does not lie in the intersection of the new π_{0}-precision intervals. However, if a new initial offset τ_{0}^{k+1} for internal global time τ^{k+1}(t) is defined for round k + 1, π_{0}-correctness with respect to τ^{k+1} can of course be guaranteed. Consequently, resynchronization starts the next round k + 1, during which initial precision π_{0} again deteriorates to π^{H}.

Note carefully that only the interval clocks’ associated π^{H}-precision intervals experience (precision) enhancement during resynchronization. The local interval clocks 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 π^{H}-precision intervals during round 0, …, k. This eventually explains why t and τ will usually be apart, as mentioned earlier.

Generally speaking, the major advantage of the interval-based precision analysis developed in [SS97a]^{5} 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 π-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 I(t) = [T ± α] is provided by its interval of accuracies α and the associated π-precision interval: Since all (non-faulty) accuracy intervals must contain real-time t and internal global time τ by construction, the latter times serve as a “common reference” for relating different intervals. Of course, the particular reference point ref(I) may lie anywhere in [t − α^{+}, t + α^{−}] and [τ − π^{+}, τ + π^{−}], according to the actually experienced clock drift, transmission delay, and initial accuracy, but there is no need for dealing with it explicitly.

5Note that we provide a few extensions of the generic analysis of [SS97a] in Appendix C, which are used instead of the original version where required.

2.3 Fault Model

In [SS97a], 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 perception-based hybrid fault model for this purpose, which is a refinement of the “abstract fault model” suggested in [SS97a]. 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’ 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 nonfaulty participants in the system. This way, both node \underline{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 I_{q} = {I_{q}^{s} : 1 ≤ s ≤ n} received and preprocessed at any non-faulty node q during an FME, recall Subsection 2.1. Since the precision requirement (P) only demands that any two non-faulty clocks must satisfy |C_{p}(t) − C_{q}(t)| ≤ π, without regard to the other nodes in the system, the pair of perceptions I_{p}, I_{q} can be considered in isolation; faulty receiving nodes (which may behave arbitrarily anyway) can entirely be ignored. Therefore, global fault assumptions —like the one that \underline{all} receivers perceive a certain fault consistently— are not required.

Rather than on the system-wide number of faults during a round (say, f ≤ ⌊(n − 1)/3⌋), we can hence rely upon the number of faulty pairs of intervals {I_{p}^{s} ∈ I_{p}, I_{q}^{s} ∈ I_{q}} at two non-faulty nodes p, q ≠ 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 I_{p}^{s} = 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 I_{p}^{s} and I_{q}^{s} to differ slightly. This fact requires special treatment in our analysis, see Lemma 4. 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 I_{p}^{s} or 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 I_{p}, 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 ([DHS86]) remain valid. The opposite covering, however, cannot be assumed in general since the faulty (pairs of) intervals in two different pairs of perceptions I_{p}, I_{q} and I_{v}, I_{w} need \underline{not} originate in the same set of sending nodes.

For that reason, our perception-based fault model also allows to accurately model 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 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.

Definition 4 (Single Faults) An interval I representing t can suffer from the following faults:

• Omission: Missing interval, expressed by I = ∅.

• Non-accurate interval: t ∉ I.

• Unbounded accuracy: t ∈ I but |I| too large according to some condition (that need not be known explicitly).

Remarks 1. Non-accurate intervals can be caused by timing faults due to a faulty sending node/clock or excessive transmission delays, or by accuracy faults due to a faulty sending node/clock or a damaged message.

2. 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 4), it is nevertheless true that even limiting α^{−}, α^{+} accordingly cannot prevent faulty nodes from considerably spoiling the “average” behavior.

3. Whereas it is usually impossible to decide locally whether an interval I is accurate or not, it is of course possible to detect omission faults. Hence, given a set I of n ≥ 1 compatible intervals with f′_{o} ≥ 0 of them exhibiting omission faults, it is trivial to discard the f′_{o} omissive ones from I and to proceed with the reduced set J containing the n′ = n − f′_{o} non-empty intervals only.

For our precision analysis, the single-interval faults of Definition 4 must be complemented by faults of pairs of intervals I_{p}^{s} and 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 hybrid fault model (refer to [AK96], [WS00]). It will allow us to exploit the fact that masking f symmetric faults with OA requires only n ≥ 2f + 1, whereas n ≥ 3f + 1 is needed if all faults are asymmetric ones ([DHS86]). Since a large number of asymmetric faults is very unlikely in practice, see [Sch95], this effectively leads to a smaller n for tolerating a given number of faults, see (3).

The following Definition 5 exhaustively specifies all possible faults of pairs of intervals.

Definition 5 (Pairwise Faults) A pair of compatible accuracy intervals {I_{p}^{s}, I_{q}^{s}} originating in a single sending node s and representing real-time t suffers from

• a crash fault if and only if I_{p}^{s} = I_{q}^{s} = ∅,

• a symmetric fault if and only if either

(1) both I_{p}^{s} and I_{q}^{s} are not accurate in the sense of t < left(I_{p}^{s}) and t < left(I_{q}^{s}), or else t > right(I_{p}^{s}) and t > right(I_{q}^{s}), (2) without loss of generality, I_{p}^{s} = ∅ and I_{q}^{s} ≠ ∅ does not suffer from

an unbounded accuracy fault,

• an asymmetric fault if and only if either

(1) both I_{p}^{s} and I_{q}^{s} are not accurate in the sense of t > right(I_{p}^{s}) and t < left(I_{q}^{s}) or else t > right(I_{q}^{s}) and t < left(I_{p}^{s}) (true byzantine fault),

(2) without loss of generality, I_{p}^{s} ≠ ∅ is faulty and I_{q}^{s} is arbitrary (and none of the other faults applies).

Remarks 1. The “classical” asymmetric fault ([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 2.

2. The “classical” symmetric fault ([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.

3. 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.

4. We do not consider \underline{systemwide} consistently perceived benign faults ([WS00]) explicitly, since they are simple to accommodate in our context: To tolerate f_{b} benign faults, n ≥ f_{b} + 1 is sufficient.

5. Note that Definition 5 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.

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 4, recall Figure 3. 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/τ-symmetrically) or inconsistently (t/τ-asymmetrically): Let a single accuracy interval I that is faulty with respect to real-time t and/or internal global time τ be called t/τ-symmetrically faulty if either

t < left(I) and τ < left(Î), or t > right(I) and τ > right(Î);

otherwise, it is considered t/τ-asymmetrically faulty. A set F of faulty accuracy intervals is identically t/τ-symmetrically faulty if t (and hence also τ) is either to the left or to the right for all members of F.

Assumption 1 (Perception-based Hybrid Fault Model F) Let a pair of accuracy intervals {I_{p}^{s}, I_{q}^{s}} originating in a single sending node s and representing real-time t, with the associated precision intervals {Î_{p}^{s}, Î_{q}^{s}} representing τ, be called

(1) simple faulty if it suffers from a crash fault or a symmetric fault with respect to t and/or τ and both faulty intervals (only present if no omission took place) are identically t/τ-symmetrically faulty,

(2) arbitrary faulty if it suffers either from an asymmetric fault with respect to t and/or τ, or a symmetric fault involving at least one t/τasymmetrically faulty interval. Alternatively, an arbitrary fault could also be just a simple one.

For all pairs of non-faulty nodes p and q, consider the ordered sets^{6} of intervals I_{p} = {I_{p}^{1}, …, I_{p}^{n}} and I_{q} = {I_{q}^{1}, …, 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 9. We assume that at most f_{a} respectively f_{s} of the n pairs of intervals {I_{p}^{s}, I_{q}^{s}}, 1 ≤ s ≤ n, suffer from arbitrary respectively simple faults, where f_{a} and f_{s} are such that

n ≥ 3f_{a} + 2f_{s} + 1.  (3)

3 Marzullo’s 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 [Mar84] and termed Marzullo function in [Lam87]. Although its relevance was recognized in several papers (for example, see [Lam87], [Mar90], [OSF92], [Sch95], [Mil95]), it has been studied thoroughly in the context of replicated sensors only, see [Mar90] and [BI96]. For clock synchronization purposes, a number of additional properties are required, which will be established subsequently.

Definition 6 (Marzullo Function) Given a set I = {I_{1}, …, I_{n}} of n ≥ 1 (non-empty) compatible intervals with at least n − f ≥ 1 of the intervals being accurate, M_{n}^{n−f}(I) is defined as the largest interval whose edges lie in the intersection of at least n − f different I_{j}’s.

Therefore, to compute the left and right edge of M_{n}^{n−f}(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}({I_{1}+Δ, …, I_{n}+Δ}) = M_{n}^{n−f}({I_{1}, …, I_{n}})+ Δ for any real Δ, and can be computed in O(n log n) time by sorting the intervals’ edges, see [Mar90] for details. Figure 4 shows an example for n = 4 and f = 1. Note that the unknown t cannot lie in the region between right(I_{3}) and left(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_{4}^{3}.

6We use the term ordered sets for I_{p} and I_{q} to stress the fact that the intervals in both input sets can be uniquely grouped as n pairs {I_{p}^{s} ∈ I_{p}, I_{q}^{s} ∈ I_{q}} originating in the same sending node s, 1 ≤ s ≤ n.

t (unknown)^{I_{3}}  ^{I_{4}}^{I_{2}}^{I_{1}} incorrect M_{4}^{3}(I)

Figure 4: Example of the Marzullo function M for n = 4 and f = 1. The edges of the result lie in n − f = 3 input intervals.

The most important feature of M is fault-tolerance with respect to faulty input intervals. For example, Figure 4 shows that M_{4}^{3} provides an accurate result despite the fact that I_{4} was non-accurate. We will now embark formally on M’s capabilities in this respect, according to the following roadmap:

1. We start with the “single node case,” where M’s result M_{p} computed at a particular non-faulty node p is considered in isolation. It suffices to account for single faults according to Definition 4 here, which affect M’s input intervals at node p.

• Lemma 2 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 M_{p}.

• Lemma 3 provides a few monotonicity properties of M, that is, upper bound results like M_{n}^{n−f}(I) ⊆ M_{n}^{n−(f+k)}(I).

Note that those results are primarily required for accuracy analysis.

2. For precision analysis, we also require pairwise properties, that is, statements relating the results M_{p} and M_{q} of M computed at two different nodes p and q. Therefore, we have to consider pairwise faults according to Definition 5 here, which affect the pair {I_{p}^{s}, I_{q}^{s}} received in the broadcast from node s.

• Lemma 4 gives the number of non-faulty pairs of intervals required for tolerating a certain number of faults, and provides both a lower bound on M_{p} ∩ M_{q} and an upper bound on M_{p} ⊔ M_{q}; recall our definition of the nc-union in Section 2.2.

• Lemma 5 adopts Lemma 4 to a slightly extended fault model and, most importantly, shows what happens to M_{p} ⊔ M_{q} when the fault assumptions are violated.

We should add here that all lemmas of this section deal with elementary intervals only, even without reference points. Dealing with fully-fledged πaccurate intervals (incorporating both precision and accuracy intervals) according to Figure 3 will be postponed to the final analysis of OA in Section 4.

The following Lemma 2 reveals how M behaves in the presence of faults according to Definition 4. Extending the accomplishments of [Mar84] and [Mar90], it answers the question of how many non-faulty intervals are required for tolerating a certain number of non-accurate intervals (f_{n}) and unbounded accuracy faults (f_{u}). The most important property shown is that M’s result lies within the intersection of n − 2f_{n} − 3f_{u} ≥ 1 non-faulty input intervals.

Lemma 2 (Accuracy M) Let J = {J_{1}, …, J_{n}} be a set of n ≥ 1 nonempty compatible accuracy intervals representing t, and define w^{h} to be the length of the largest intersection of h ≥ 1 non-faulty intervals among them, that is, w^{h} = max{|W | : W ∈ W^{h}} for

W^{h} = {W : W = ⋂_{i=1}^{h} J_{w_{i}} with indices w_{i} ≠ w_{j} for i ≠ j
and J_{w_{i}} ∈ J being non-faulty}.

If f′_{u} ≥ 0 of the J_{j} suffer from unbounded accuracy faults and f′_{n} ≥ 0 are non-accurate, where f′_{u} ≤ f_{u} and f′_{n} ≤ f_{n} with f′_{u}+f′_{n} = f′ ≤ f_{u}+f_{n} = f < n (so that n − f′ ≥ n − f > 0 of the n intervals are non-faulty), then:

(1) M = M_{n}^{n−f}(J) is accurate and contains any intersection W ∈ W^{n−f} of n − f ≥ 1 different non-faulty input intervals J_{w_{1}}, …, J_{w_{n−f}}, that is,

W = ⋂_{j=1}^{n−f} J_{w_{j}} ⊆ M,  (4)

so that |M| ≥ w^{n−f} (minimal intersection property).

(2) There are at least n − 2f − f′_{u} ≥ n − 2f − f_{u} different non-faulty input intervals J_{b_{1}}, …, J_{b_{n−2f−f′_{u}}} ∈ J such that

M ⊆ ⋂_{j=1}^{n−2f−f′_{u}} J_{b_{j}} ⊆ ⋂_{j=1}^{n−2f−f_{u}} J_{b′_{j}},  (5)

where the set of indices {b′_{j}}_{1≤j≤n−2f−f_{u}} is obtained from {b_{j}}_{1≤j≤n−2f−f′_{u}} by discarding f_{u} − f′_{u} elements. Hence, |M| ≤ w^{n−2f−f′_{u}} ≤ w^{n−2f−f_{u}}.

(3) There are at least f − f′ + 1 ≥ 1 non-faulty intervals J_{ℓ_{k}} respectively J_{r_{k}}, 1 ≤ k ≤ f −f′+1, in J satisfying left(M) ≤ left(J_{ℓ_{k}}) respectively right(M) ≥ right(J_{r_{k}}).

Proof Since M = M_{n}^{n−f}(J) contains any intersection of at least n − f input intervals by definition, it obviously contains any intersection of n − f non-faulty intervals W = ⋂_{j=1}^{n−f} J_{w_{j}} ∈ W^{n−f}. Note that w_{j}, 1 ≤ j ≤ n − f, just denote the indices of the contributing intervals with respect to J here. Therefore, it follows that t ∈ M and |M| ≥ 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 M with non-faulty input intervals is g′_{l} + g′_{r} ≥ 2(n − f) − 2f′_{u} − f′_{n}, because an interval J_{j} suffering from an unbounded accuracy fault (f′_{u}) could intersect with both edges of M, whereas a non-accurate interval (f′_{n}) can only intersect with one edge of M due to t ∉ J_{j} but t ∈ M. However, since there are only g′ = n − f′ different non-faulty intervals in J = {J_{1}, …, J_{n}}, the pigeonhole principle reveals that

g′_{l} + g′_{r} − g′ ≥ 2n − 2f − 2f′_{u} − f′_{n} − n + f′ = n − 2f − f′_{u}

of the intersected accurate intervals, say J_{b_{1}}, …, J_{b_{n−2f−f′_{u}}}, must be the same. Therefore, M must lie in the intersection of those intervals and |M| ≤ w^{n−2f−f′_{u}} as asserted. The upper bound in (5) follows immediately from f′_{u} ≤ f_{u}.

Finally, to prove item (3), consider without loss of generality the left edge of M. We show by contradiction that the left edge of at least f − f′ + 1 nonfaulty intervals lies at or right of left(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 left(M). However, this would contradict the minimal intersection property established in item (1), completing the proof of our lemma. □

Remarks 1. We excluded omission faults in our lemma, since M as defined in Definition 6 cannot deal with empty intervals. However, as mentioned in Remark 3 following Definition 4, intervals with omission faults can easily be discarded before M is applied. Therefore, if f′_{o} of presumed n intervals suffer from an omission fault, we just have to set n := n − f′_{o} and f := f − f′_{o} in Lemma 2 to obtain the results for this case as well. Note that it is feasible to let f depend on f′_{o}, see Lemma 4 below.

2. Interpreting item (2) of Lemma 2 and the previous remark in terms of the usual fault-tolerance degree notion, it follows that n ≥ f′_{o} + 2f + f′_{u} + 1 nodes are required to guarantee that M remains bounded by the length of at least one non-faulty input interval. Hence, as many as

n ≥ \{ \begin{matrix}f′_{o} + 1 & for f′_{o} omission faults, \\ 2f_{n} + 1 & for f′_{n} ≤ f_{n} non-accurate intervals, \\ 2f_{u} + f′_{u} ≤ 3f_{u} & for f′_{u} ≤ f_{u} unbounded accuracy faults \end{matrix}

nodes are required for tolerating faults of the given type. It is thus apparent that M can tolerate ⌊(n − 1)/2⌋ non-accurate intervals but only ⌊(n − 1)/3⌋ intervals that suffer from unbounded accuracy faults, see [Mar90]. Note carefully that the numbers above do not solely depend on the actual number of faults (f′_{u}), but also on their maximum number (f_{u}); this is due to the fact that the latter is compiled into the superscript argument of M.

3. The lower bound on |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 minimal intersection property was coined in [Mar84]. Note that M contains any intersection of n − f intervals, hence includes intersections involving unbounded accuracy faults as well.

4. Item (3) just says that M contains the left and right edge of at least one (not necessarily the same) non-faulty interval.

The following Lemma 3 establishes a few useful monotonicity relations with respect to both parameters and input arguments of M.

Lemma 3 (Monotonicity M) Let I = {I_{1}, …, I_{n}} be a set of n > f ≥ 0 compatible non-empty accuracy intervals representing t, with f′, 0 ≤ f′ ≤ f, faulty ones among them. Then, M_{n}^{n−f}(I) is accurate and satisfies the following monotonicity relations:

(1) M_{n}^{n−f}(I) ⊆ M_{n}^{n−(f+k)}(I) for any integer k with 0 ≤ k < n − f,

(2) M_{n}^{n−f}(I) ⊆ M_{n}^{n−f}(J) for any J = {J_{1}, …, J_{n}} with I_{l} ⊆ J_{l} for 1 ≤ l ≤ n,

(3) For f ≥ f′ ≥ 1, if L = I\{I_{j}} is obtained by discarding some faulty interval I_{j} from I, M_{n−1}^{(n−1)−(f−1)}(L) = M_{n−1}^{n−f}(L) is accurate and satisfies

M_{n−1}^{n−f}(L) ⊆ M_{n}^{n−f}(I).  (6)

Proof In the proof of item (1) of Lemma 2, we argued that M = M_{n}^{n−f}(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 J contains the intersection of the corresponding intervals in I if it is non-empty at all. By the same token as before, it hence follows that M_{n}^{n−f}(J) must contain M_{n}^{n−f}(I) as well.

For proving item (3), the same argument is used again. First of all, n > f ≥ 1 implies that n−1 > f −1 ≥ 0, hence M_{n−1}^{(n−1)−(f−1)}(L) is accurate. Moreover, discarding a faulty I_{j} in I and simultaneously reducing f by 1 leaves the superscript argument (n − 1) − (f − 1) = n − f in M_{n−1}^{n−f}(L) unchanged. Since the interval containing any intersection of n − f input intervals in I must contain the interval containing any intersection of n − f intervals in L ⊆ I, the statement given in item (3) of our lemma follows. □

Remarks 1. It is immediately apparent from the definition of M that M_{n}^{1}(I) = ⋃_{i} I_{i} and M_{n}^{n}(I) = ⋂_{i} I_{i}, hence M_{n}^{n−f} “changes” from union to intersection as n − f goes from 1 to n.

2. It is not difficult to show that M is optimal with respect to worstcase accuracy in presence of non-accurate intervals among all interval-valued functions of n interval arguments, as pointed out already in [Lam87]: Suppose there were a function F that provides an accurate interval satisfying M(I) ⊈ F(I), then M′ = M(I)\(M(I)∩F(I)) ≠ ∅ and there must be an intersection of n − f accurate intervals A = ⋂_{i=1}^{n−f} I_{b_{i}} so that A ∩ M′ ≠ ∅. However, the (valid) assumption that t ∈ A ∩ M′ reveals that F(I) cannot be accurate, providing the required contradiction.

3. Regarding item (2) of Lemma 3, 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}^{n−f}(J) if a “new” intersection of n−f intervals comes up. Just consider shrinking or moving right the faulty interval I_{4} in Figure 4, which causes the right edge of M_{4}^{3}(I) to shrink to right(I_{3}) as soon as left(I_{4}) > right(I_{1}). This implies that M does not satisfy a Lipschitz condition with respect to moving (edges of) input intervals, as already noted in [Lam87].

4. Item (3) of Lemma 3 implies that one should always try to detect and discard faulty intervals before M is applied, since this can only improve the result.

For establishing precision results, we also require certain “pairwise” properties of M, that is, statements relating the results M_{p} and M_{q} of M computed at different nodes p and q. This is provided by the following Lemma 4, which is an advanced version of a lemma introduced in [Sch95]. It gives the number of non-faulty pairs of intervals required for tolerating a certain number of

• crash faults (f′_{c} ≤ f_{c}),

• symmetric faults (f′_{s} ≤ f_{s}),

• asymmetric faults (f′_{a} ≤ f_{a}).

The most important result of Lemma 4 is an upper bound on the nc-union M_{p}⊔M_{q}, which must lie within at least n−min{f′_{c}+f′_{s}, 2f_{c}−f′_{c}}−2f_{s}−3f_{a} ≥ 1 nc-unions I_{p}^{s}⊔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.

Lemma 4 (Precision M) Let I_{p} = {I_{p}^{1}, …, I_{p}^{n}} and I_{q} = {I_{q}^{1}, …, I_{q}^{n}} be two ordered sets of n > f_{c} + f_{s} + f_{a}, f_{c}, f_{s}, f_{a} ≥ 0, compatible (or empty) accuracy intervals representing t, where f′_{a} ≤ f_{a}, f′_{s} ≤ f_{s}, and f′_{c} ≤ f_{c} of the n pairs of intervals {I_{p}^{i}, 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 ≥ 1 nc-unions respectively intersections of pairs of non-faulty intervals, formally u^{h} = max{|U| : U ∈ U_{pq}^{h}} respectively v^{h} = max{|V | : V ∈ V_{pq}^{h}} for

U_{pq}^{h} = {U : U = ⋂_{i=1}^{h} I_{p}^{u_{i}} ⊔ I_{q}^{u_{i}} with u_{i} ≠ u_{j}, i ≠ j,

and non-faulty I_{p}^{u_{i}} ∈ I_{p}, I_{q}^{u_{i}} ∈ I_{q}}
V_{pq}^{h} = {V : V = ⋂_{i=1}^{h} I_{p}^{v_{i}} ∩ I_{q}^{v_{i}} with v_{i} ≠ v_{j}, i ≠ j,
and non-faulty I_{p}^{v_{i}} ∈ I_{p}, I_{q}^{v_{i}} ∈ I_{q}}.

Let d′_{p}, 0 ≤ d′_{p} ≤ f′_{s}, respectively e′_{p}, 0 ≤ e′_{p} ≤ f′_{a}, denote the (unknown) number of empty intervals caused by symmetric respectively asymmetric faults at node p, and J_{p} = {J_{1}, …, J_{n_{p}}} be the set of n_{p} = n − o_{p} non-empty intervals obtained from I_{p} by discarding any of the (known) o_{p} = f′_{c}+d′_{p}+e′_{p} ≤ f_{c}+f_{s}+f_{a} empty intervals caused by crash and symmetric/asymmetric faults. Using the upper bound f_{p} = f_{s} + f_{a} − max{0, o_{p} − f_{c}} on the number of intervals in J_{p} that (still) may be faulty in presence of o_{p} omissions, define M_{p} = M_{n_{p}}^{n_{p}−f_{p}}(J_{p}), and analogously M_{q} = M_{n_{q}}^{n_{q}−f_{q}}(J_{q}). Then,

(1) both M_{p} and M_{q} are accurate and

M_{p} ∩ M_{q} ⊇ ⋂_{j=1}^{n−f′_{c}−f_{s}−f_{a}} I_{p}^{v_{j}} ∩ I_{q}^{v_{j}} = V  (7)

for any subset V ∈ V_{pq}^{n−f′_{c}−f_{s}−f_{a}}, so that |M_{p} ∩ M_{q}| ≥ v^{n−f′_{c}−f_{s}−f_{a}} (distributed minimal intersection property),

(2) there are at least n − min{f′_{c} + f′_{s}, 2f_{c} − f′_{c}} − 2f_{s} − 2f_{a} − f′_{a} pairs of non-faulty intervals {I_{p}^{u_{k}}, I_{q}^{u_{k}}} with I_{p}^{u_{k}} ∈ J_{p} and I_{q}^{u_{k}} ∈ J_{q} such that

M_{p} ⊔ M_{q} ⊆ ⋂_{k=1}^{n−min{f′_{c}+f′_{s},2f_{c}−f′_{c}}−2f_{s}−2f_{a}−f′_{a}} I_{p}^{u_{k}} ⊔ I_{q}^{u_{k}}  (8)

and hence |M_{p} ⊔ M_{q}| ≤ u^{n−min{f′_{c}+f′_{s},2f_{c}−f′_{c}}−2f_{s}−2f_{a}−f′_{a}}.

Proof First of all, we note that f_{p} gives indeed an upper bound on the number of intervals in J_{p} that still may be faulty in presence of o_{p} = f′_{c} + d′_{p} + e′_{p} ≤ f′_{c} + f′_{s} + f′_{a} ≤ f_{c} + f_{s} + f_{a} omissions, since f_{p} = f_{s} + f_{a} if o_{p} ≤ f_{c}, and f_{p} = f_{s} + f_{a} − (o_{p} − f_{c}) otherwise (accounting for o_{p} − f_{c} > 0 symmetric/asymmetric faults that must have caused omissions at node p), hence

f_{p} ≤ f_{s} + f_{a}.  (9)

Evidently, at least n_{p}−f_{p} of the intervals in J_{p} must be non-faulty. Rewriting the definition

n_{p}−f_{p} = n−o_{p}−f_{s}−f_{a}+max{0, o_{p}−f_{c}} = n−f_{s}−f_{a}+max{−o_{p}, −f_{c}} (10)

and applying max{0, x} ≥ x for any x, and the simple fact that

max{−o_{p}, −f_{c}} ≤ −f′_{c}

since obviously o_{p} ≥ f′_{c} and f′_{c} ≤ f_{c}, it follows easily that

n − f_{c} − f_{s} − f_{a} ≤ n_{p} − f_{p} ≤ n − f′_{c} − f_{s} − f_{a} ≤ n − f_{s} − f_{a}.  (11)

Of course, analogous bounds hold for n_{q} − f_{q}.

Lemma 2 is applicable, and it follows that M_{p} and M_{q} are both accurate and satisfy the (local) minimal intersection property. That is, M_{p} contains any intersection of n_{p} − f_{p} ≤ n − f′_{c} − f_{s} − f_{a} non-faulty intervals present in J_{p}. If {v_{j}}_{1≤j≤n−f′_{c}−f_{s}−f_{a}} denotes any set of different indices of non-faulty pairs of intervals I_{p}^{v_{j}} ∈ I_{p}, I_{q}^{v_{j}} ∈ I_{q} (of course also present in J_{p}, J_{q}), we thus have

W_{p} = ⋂_{j=1}^{n−f′_{c}−f_{s}−f_{a}} I_{p}^{v_{j}} ⊆ ⋂_{j=1}^{n_{p}−f_{p}} I_{p}^{v_{j}} ⊆ M_{p}

and, for the same set {v_{j}}, W_{q} = ⋂_{j=1}^{n−f′_{c}−f_{s}−f_{a}} I_{q}^{v_{j}} ⊆ M_{q}. By elementary set algebra, it thus follows that V = W_{p} ∩ W_{q} ∈ V^{n−f′_{c}−f_{s}−f_{a}} satisfies (7). Finally, |M_{p} ∩M_{q}| ≥ v^{n−f′_{c}−f_{s}−f_{a}} is a simple consequence of the definition of v^{h} as the maximum length of V ∈ V_{pq}^{h}. This completes the proof of item (1).

For item (2), suppose that the left respectively right edge of M_{p} respectively M_{q} intersects with g_{p,l} respectively g_{q,r} intervals belonging to a non-faulty pair of intervals in I_{p}, I_{q}. We must have

g_{p,l} ≥ n_{p} − f_{p} − (f′_{a} − e′_{p}) − (s′_{left} − d′_{p,left})
≥ n − f_{s} − f_{a} + max{−o_{p}, −f_{c}} − f′_{a} − s′_{left} + d′_{p,left} + e′_{p}
g_{q,r} ≥ n_{q} − f_{q} − (f′_{a} − e′_{q}) − (s′_{right} − d′_{q,right})
≥ n − f_{s} − f_{a} + max{−o_{q}, −f_{c}} − f′_{a} − s′_{right} + d′_{q,right} + e′_{q}.

where s′_{left} + s′_{right} = f′_{s} ≤ f_{s} are the number of symmetrically faulty pairs of intervals lying left respectively right of t, and d′_{p,left} + d′_{p,right} = d′_{p}, d′_{q,left} + d′_{q,right} = d′_{q} denote the number of omissions among them at node p respectively q; the lower bounds follow immediately from (10).

However, we only have g = n − f′_{c} − f′_{s} − f′_{a} different non-faulty pairs of intervals. Thus, the pigeonhole principle reveals that

g_{p,l} + g_{q,r} − g ≥

≥ 2n + max{−o_{p}, −f_{c}} + max{−o_{q}, −f_{c}} − 2f_{s} − 2f_{a} − 2f′_{a} − f′_{s}
+d′_{p,left} + d′_{q,right} + e′_{p} + e′_{q} − n + f′_{c} + f′_{s} + f′_{a}
≥ n + max{−f′_{c} − d′_{p,right}, −f_{c} + d′_{p,left} + e′_{p}}
+ max{−f′_{c} − d′_{q,left}, −f_{c} + d′_{q,right} + e′_{q}} + f′_{c} − 2f_{s} − 2f_{a} − f′_{a}
≥ n + max{−2f′_{c} − f′_{s}, −2f_{c}} + f′_{c} − 2f_{s} − 2f_{a} − f′_{a}
≥ n − min{f′_{c} + f′_{s}, 2f_{c} − f′_{c}} − 2f_{s} − 2f_{a} − f′_{a}

of them must be the same. Abbreviating μ = min{f′_{c} + f′_{s}, 2f_{c} − f′_{c}}, we can conclude that there are at least n − μ − 2f_{s} − 2f_{a} − f′_{a} pairs of accurate intervals, say, I_{p}^{b_{1}} ⊔ I_{q}^{b_{1}}, …, I_{p}^{b_{n−μ−2fs−2fa−f′_{a}}} ⊔ I_{q}^{b_{n−μ−2fs−2fa−f′_{a}}} with I_{p}^{b_{i}} ∈ J_{p} and I_{q}^{b_{i}} ∈ J_{q} satisfying

M_{p} ⊔ M_{q} ⊆ ⋂_{j=1}^{n−μ−2f_{s}−2f_{a}−f′_{a}} I_{p}^{b_{j}} ⊔ I_{q}^{b_{j}} ∈ U_{pq}^{n−μ−2f_{s}−2f_{a}−f′_{a}},  (12)

which proves (8). To complete the proof of Lemma 4, it only remains to justify |M_{p} ⊔ M_{q}| ≤ u^{n−μ−2f_{s}−2f_{a}−f′_{a}}, which is a trivial consequence of (12). □

Remarks 1. Note carefully that Lemma 2 could also be used to deduce a precision-related result: Since M_{p} and M_{q} are both accurate and hence contain t, it follows from item (2) that |M_{p}∪M_{q}| ≤ 2w^{n−2f−f_{u}}, so that the same holds true for |M_{p} ⊔ M_{q}|. However, comparison with item (2) of Lemma 4 reveals that this result is roughly twice as large and hence insufficient for precision enhancement.

2. Our crash faults are more severe than the (systemwide consistently perceived) benign faults of [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 f′_{s} respectively f_{s} and f′_{c} = f_{c} = 0 (note that n_{p} − f_{p} = n − f_{s} − f_{a} in this case). After all, we already accounted for symmetric/asymmetric faults involving empty intervals in the proof of Lemma 4.

3. Interpreting the accomplishments of Lemma 4 and the previous remark in terms of the usual fault-tolerance degree notion, it turns out that n ≥ min{f′_{c} + f′_{s}, 2f_{c} − f′_{c}} + 2f_{s} + 2f_{a} + f′_{a} + 1 nodes are required to guarantee that M_{p} ⊔ 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 ≥ \{ \begin{matrix}min\{f′_{c} + f′_{s}, 2f_{c} − f′_{c}\} + 1 & for f′_{c} crash faults, \\ 2f_{s} + 1 & for f′_{s} ≤ f_{s} symmetric faults, \\ 2f_{a} + f′_{a} + 1 ≤ 3f_{a} + 1 & for f′_{a} ≤ f_{a} asymmetric faults \end{matrix}

nodes are required for tolerating faults of the given type.

4. It should be clear from the proof of Lemma 4 that the property that really pins down symmetric faults is the following one: If a symmetrically faulty interval I_{q}^{s} intersects, say, with the right edge of M_{q} (correctly accounted for in s_{right}), then its corresponding I_{p}^{s} must not intersect with the left edge of M_{p} (since it is not accounted for in s_{left}). This is the reason why I_{p}^{s} ≠ 0 being faulty and I_{q}^{s} ≠ 0 being non-faulty must be counted as an asymmetric fault in item (2) of Definition 5.

5. The proof of Lemma 4 reveals the ultimate reason for using nc-unions ⊔ instead of ∪ in the statement of item (2): It may be the case that, say, M_{q} ⊆ M_{p}, such that M_{p} would determine both left and right edge of M_{p} ∪ M_{q}. By applying Lemma 2 with n := n_{p}, f := f_{p}, and f′_{u} ≤ f′_{a} (as well as f_{u} ≤ f_{a}), we could show that there are at least n_{p} − 2f_{p} − f′_{u} ≥ n − μ − 2f_{s} − 2f_{a} − f′_{a} non-faulty intervals I_{p}^{b_{j}} in J_{p} the intersection of which majorizes M_{p}. This does not imply, however, that all of those intervals appear in 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 I_{p}^{b_{j}} ∪ I_{q}^{b_{j}} —the intersection of which would of course majorize M_{q} ∪ M_{p}— involve non-fauly intervals only. Clearly, focussing upon M_{p} ⊔ M_{q} ⊆ M_{p} ∪ M_{q} entirely avoids this difficulty.

The following lemma shows that the results of Lemma 4 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.

Lemma 5 (Precision/Graceful Degradation M) Let I_{p} = {I_{p}^{1}, …, I_{p}^{n}} and I_{q} = {I_{q}^{1}, …, I_{q}^{n}} be two ordered sets of n > f_{s} + f_{a}, f_{s}, f_{a} ≥ 0, compatible (or empty) accuracy intervals representing t, where f′_{s} ≤ f_{s} respectively f′_{a} ≤ f_{a} of the n pairs of intervals {I_{p}^{i}, I_{q}^{i}} exhibit symmetric (or weaker) respectively asymmetric (or weaker) faults, and the remaining ones are nonfaulty. As in Lemma 4, define u^{h} respectively v^{h} to be the length of the largest intersection of h ≥ 1 nc-unions (∈ U_{pq}^{h}) respectively intersections (∈ V_{pq}^{h}) of pairs of non-faulty intervals.

Let J_{p} = {J_{1}, …, J_{n_{p}}} be the set of n_{p} = n − o_{p} non-empty intervals obtained from I_{p} by discarding any of the o_{p} empty intervals caused by omissions. Using the upper bound f_{p} = f_{s} + f_{a} − o_{p} on the number of intervals in J_{p} that (still) may be faulty in presence of o_{p} omissions, define

M_{p} = M_{n_{p}}^{n_{p}−f_{p}}(J_{p}) = M_{n_{p}}^{n−f_{s}−f_{a}}(J_{p}),

and analogously M_{q} = M_{n_{q}}^{n−f_{s}−f_{a}}(J_{q}). Then:

(1) Both M_{p} and M_{q} are accurate and

M_{p} ∩ M_{q} ⊇ ⋂_{j=1}^{n−f_{s}−f_{a}} I_{p}^{v_{j}} ∩ I_{q}^{v_{j}} = V  (13)

for any possible subset V ∈ V_{pq}^{n−f_{s}−f_{a}}, so that |M_{p} ∩ M_{q}| ≥ v^{n−f_{s}−f_{a}} (distributed minimal intersection property).

(2) There are at least n − 2f_{s} − 2f_{a} − f′_{a} ≥ n − 2f_{s} − 3f_{a} pairs of non-faulty intervals {I_{p}^{u_{k}}, I_{q}^{u_{k}}} with I_{p}^{u_{k}} ∈ J_{p} and I_{q}^{u_{k}} ∈ J_{q} such that

M_{p} ⊔ M_{q} ⊆ ⋂_{k=1}^{n−2f_{s}−2f_{a}−f′_{a}} I_{p}^{u_{k}} ⊔ I_{q}^{u_{k}} ⊆ ⋂_{k=1}^{n−2f_{s}−3f_{a}} I_{p}^{u′_{k}} ⊔ I_{q}^{u′_{k}},  (14)

where {u′_{k}}_{1≤k≤n−2f_{s}−3f_{a}} is obtained from {u_{k}}_{1≤k≤n−2f_{s}−2f_{a}−f′_{a}} by discarding f_{a}−f′_{a} arbitrary elements. Hence, |M_{p}⊔M_{q}| ≤ u^{n−2f_{s}−2f_{a}−f′_{a}} ≤ u^{n−2f_{s}−3f_{a}}.

(3) Assume that the fault model is violated in the sense that f′ = f′_{s} + f′_{a} > f_{s} + f_{a} but still n ≥ 2f′ + f′_{u} + 1, where f′_{u} ≤ f′_{a} denotes the number of pairs of intervals that involve unbounded accuracy faults. If M_{p} and M_{q} exist, that is, sufficiently many intersecting input intervals exist to compute M, then there are n − 2f′ − f′_{u} non-faulty intervals I_{p}^{p_{1}}, …, I_{p}^{p_{n−2f′−f′_{u}}} in J_{p} and n − 2f′ − f′_{u} non-faulty intervals I_{q}^{q_{1}}, …, I_{q}^{q_{n−2f′−f′_{u}}} in J_{q} such that

M_{p} ∪ M_{q} ⊆ ( ⋂_{j=1}^{n−2f′−f′_{u}} I_{p}^{p_{j}} ) ∪ ( ⋂_{j=1}^{n−2f′−f′_{u}} I_{q}^{q_{j}} ) .  (15)

Hence, |M_{p} ∪ M_{q}| ≤ w_{p}^{n−2f′−f′_{u}} + w_{q}^{n−2f′−f′_{u}}, where w_{p}^{h} respectively w_{q}^{h} denote the length of the largest intersection of h accurate intervals in I_{p} respectively I_{q}.

Nevertheless, M_{p} and M_{q} are not necessarily accurate and possibly not even consistent; accurateness is guaranteed, however, if f′ ≤ f_{s} + f_{a} but all f′ faults are asymmetric ones.

Proof Since crash faults are now considered as symmetric ones and hence accounted for in f′_{s} and f_{s}, see Remark 2 on Lemma 4, items (1) and (2) follow directly from adopting the results of Lemma 4 to f′_{c} = f_{c} = 0. Note that n_{p} − f_{p} = n − f_{s} − f_{a} here. To confirm the assertions for asymmetric faults appearing as weaker ones, just consider the expressions supplied by Lemma 4 when temporarily setting f_{a} := f_{a} − 1 and f_{s} := f_{s} + 1.

To show item (3), we first note that we only have to consider the case where n_{p} = n − o_{p} ≥ n − f_{s} − f_{a}, since otherwise there would have been too many omissions to compute M_{p}. Thus,

M_{p} = M_{n_{p}}^{n−f_{s}−f_{a}}(J_{p}) ⊆ M_{n_{p}}^{n−f′}(J_{p})  (16)

according to item (1) of Lemma 3. Lemma 2 is now applicable to the righthand side of (16) and it follows by its item (2) that

M_{p} ⊆ ⋂_{j=1}^{n−2f′−f′_{u}} J_{p}^{p_{j}}.

An analogous result holds for M_{q}. Of course, the majorizing intersections for M_{p} and M_{q} involve non-faulty intervals only, hence are accurate and thus consistent. This justifies (15) and thus the condition on |M_{p} ∪ M_{q}| given in the lemma. Note carefully, however, that this does not imply that M_{p} and M_{q} are accurate or even just consistent! On the other hand, if f′ ≤ f_{s} + f_{a}, it follows from item (1) of Lemma 2 applied to the left-hand side of (16) that M_{p} (and analogously M_{q}) is accurate. □

Remarks 1. 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 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 5). Obviously, this is some form of graceful degradation of the algorithm’s performance.

2. Evidently, the worst situation with respect to the number of faults where one can hope to get a meaningful result is n ≥ 2f′ + 1. Item (3) of Lemma 5 can be used to deduce a result for this case as well: Setting f′_{u} = 0 and declaring any interval with an unbounded accuracy fault as being “nonfaulty”, we get from (15) that M_{p} ∪ M_{q} and hence M_{p} ⊔ M_{q} lies in the union of the intersection of n − 2f′ “non-faulty” intervals in J_{p} respectively J_{q}.

4 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 3. For that reason, it has already been argued in [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 5 justifies this claim: Consider a system of four nodes A, B, C, D with interval clocks having the following characteristics:

• A’s interval clock is deteriorated by ±2 units during the resynchronization period P, but actually runs at perfect rate,

• B’s interval clock is deteriorated by ±1 unit and is actually one unit ahead of real-time after one period P,

• C’s interval clock is deteriorated by ±1 unit and is actually one unit behind of real-time after one period P,

• 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.

Assuming fault-free, zero-delay communication and initially perfectly synchronized interval clocks C_{p}(0) = [0 ± 1] for p = A, B, C, we obtain the scenario depicted in Figure 5.

[figure: t = 0; t = P; t = 2P; A; B; C; D; arb. fault; arb. fault; arb. fault; t = 3P; arb. fault; t]

Figure 5: Example showing the lacking precision enhancement property of Marzullo’s function M with centerpoint setting. Since node D mimics C_{p}(t) when received at any node p, the interval computed by M_{4}^{3} at t = P, 2P, …, reconfirms the current C_{p}(t).

Each node receives the interval clocks C_{p} of the non-faulty nodes A, B, C exactly as shown at t = kP, k ≥ 1. One observes that the interval M_{p} obtained by applying M_{4}^{3} to the I_{p}^{q}’s received by node p is always exactly C_{p} —no precision enhancement will ever take place here; the reference points of C_{B} and C_{C} will drift apart perpetually.

Our algorithm will fix this problem by applying M_{4}^{3} to the associated π^{H}- precision intervals Î_{p}^{q} instead of I_{p}^{q}, recall our exposition in Subsection 2.2. In the example of Figure 5, π^{H} must satisfy |π^{H}| = 2+4 units because of the initial precision (= 2 units) plus twice the maximum deterioration during P (= 2 · 2 units). The intervals fed into M_{4}^{3} are hence trimmed to length π^{H}, and considering the resulting intervals M̂_{p} and M̂_{q} at two different nodes p and q, one finds that the reference points cannot be further apart than π^{H}/2 (centerpoint setting assumed), since M̂_{p} ⊔ M̂_{q} has length at most π^{H} by item (2) of Lemma 4.

Since the above considerations are only meaningful for maintaining precision, that is, setting the reference point of C_{p}, the optimality of M nevertheless recommends its use for determining left and right edge of 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:

• A’s interval clock is deteriorated by ±1 unit and is actually one unit ahead of real-time after one period P,

• B’s, C’s interval clocks are deteriorated by ±1 unit and are actually one unit behind real-time after period P,

• D’s clock exhibits symmetric faults.

Assuming fault-free, zero-delay communication and initially synchronized clocks satisfying C_{p}(t_{0}) = Ĉ_{p}(t_{0}) for p = A, B, C and π_{0} = [−1, 1], so that π^{H} = [−2, 2] (since maximum deterioration during P is ±1), consider the evolution of accuracy intervals during two rounds depicted in Figure 6.

[figure: t_{0} = τ_{0}; t_{1}; t_{2}; A; B; C; D; A at A,B,C; B at A,B,C; C at A,B,C; D at A; D at B,C; C_{A}(t_{1}); C_{B}(t_{1}); A at A,B,C; B at A,B,C; C at A,B,C; D at A; D at B,C; C_{A}(t_{2}); C_{C}(t_{2}); τ_{2}; τ_{1}; π^{H}; t; C_{A}(t_{0}); C_{B}(t_{0}); C_{C}(t_{0}); C_{D} faulty; C_{C}(t_{1}); C_{D} faulty; C_{B}(t_{2})]

Figure 6: Example of a reference point setting outside the accuracy interval at t_{2}. The accuracy interval C_{A}(t_{2}) computed by applying M_{4}^{3} to the received intervals does not contain the reference point computed as the centerpoint of M_{4}^{3} applied to the associated π^{H}-precision intervals.

At t_{1}, applying M_{4}^{3} to the received accuracy intervals respectively the associated π^{H}-precision intervals (which satisfy C_{q}^{p}(t_{1}) = Ĉ_{q}^{p}(t_{1}) for p, q ∈ {A, B, C} here) yields C_{A}(t_{1}) = [t_{1} ± 0] and C_{B}(t_{1}) = C_{C}(t_{1}) = [t_{1} − 2 ± 2] at the respective nodes; recall that the reference point of C_{q} is computed as the centerpoint of M applied to the Ĉ_{q}^{p}’s. In order to ensure π_{0}-correctness of clock A and B, internal global time τ_{1} must be set to t_{1} − 1 to lie in the intersection of the renewed π_{0}-precision intervals. Although τ_{1} does not lie in C_{A}(t_{1}), this situation is still feasible due to the fact that we decoupled precision and accuracy in the definition of π-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} ±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} ± 0] must be enlarged to the left by 1 to include the reference point. Note also that internal global time τ_{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 6, 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 2, viewing them as orthogonal issues. 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 2.

We should add that a similar approach was taken for the adaptive intersection algorithm of NTP ([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 π-center_{G_{S}}. It is a generalization of centerpoint setting, which partitions an interval according to the proportion of π^{−} : π^{+} while accounting for the fact that the CPU used for computing the reference point has integer arithmetic only: According to Definition 9 in Appendix B, we require all quantities manipulated by our clock synchronization algorithm to be integer multiples of the clock-setting granularity G_{S} > 0. Therefore, an integer division (rather than an exact one) is employed in π-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 O(G_{S}) in our analysis. Since we are aiming at hardware-assisted clock synchronization with worst case accuracy and precision in the μs-range and below, see [SKM^{+}00], this simplification would spoil the very accurate generic analysis of [SS97a]: Although G_{S} is smaller than clock granularity G for most adjustable clock implementations, it is nevertheless much larger than the O(·)-terms present in the results of [SS97a], see Remark 1 on Theorem 3. Therefore, we have to take the trouble of tracking the truncation errors explicitly.

Definition 7 (Discrete Reference Point Setting) Let an interval I = [a, b] with a, b being integer multiples of G_{S} > 0 and some arbitrary π = [−π^{−}, π^{+}] satisfying π = π^{−} + π^{+} > 0 be given. With ⌊x⌋_{G_{S}} denoting truncation of x to the next integer multiple of G_{S} being ≤ x, and ⌈x⌉_{G_{S}} denoting rounding up x to the next integer multiple of G_{S} being ≥ x, we define

π-center_{G_{S}}(I) = ⌊\frac{π^{−}b + π^{+}a}{π}⌋_{G_{S}}.  (17)

A few technical lemmas dealing with the properties of π-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 J, possibly extended appropriately to include the reference point. The latter is computed independently (“orthogonally”) as the π^{H}-center_{G_{S}} of the interval obtained by applying M to the associated π^{H}-precision intervals in the input set Ĵ.

Definition 8 (Convergence Function OA) Let I be a set of n compatible accuracy intervals and J ⊆ I with |J | = n′ ≤ n be the set of non-empty intervals among them. With Ĵ denoting the set of associated π^{H}-precision intervals for some given π^{H} with π^{H−}, π^{H+} being integer multiples of G_{S}, and f denoting a given fault-tolerance parameter, the orthogonal accuracy convergence function OAπ^{H}_{n−f}(J) (abbreviated by OA) is defined by

ref(OA(J)) = π^{H}-center_{G_{S}}(M_{n′}^{n−f}(Ĵ)) and  (18)
OA(J) = M_{n′}^{n−f}(J) ∪ ref(OA(J)).  (19)

In order to analyze the performance of the interval-based clock synchronization algorithm of Definition 9 employing OA, it is sufficient to evaluate the characteristic functions of OA according to Definition 11. Plugging those into the generic results of [SS97a], as done in Section 5, 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 1, whereas the more complicated derivations for accuracy-related quantities are covered by Theorem 2.

Theorem 1 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 π^{H} on the precision of all non-faulty input intervals, and [2] the maximum “difference” π_{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 1, which can be attributed to the power of our generic analysis based upon internal global time.

Theorem 1 (Precision OA) Let I_{p} = {I_{p}^{1}, …, I_{p}^{n}}, I_{q} = {I_{q}^{1}, …, I_{q}^{n}} be two ordered sets of n compatible accuracy intervals (all representing the \underline{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 1. Moreover, let the subsets of non-empty accuracy intervals among them be J_{p} ⊆ I_{p}, |J_{p}| = n_{p} ≤ n and J_{q} ⊆ I_{q}, |J_{q}| = n_{q} ≤ n and assume that

[1] any non-faulty I_{p}^{i} ∈ I_{p} as well as any non-faulty I_{q}^{i} ∈ I_{q} is π^{H}-correct for some given π^{H} with π^{H+}, π^{H−} being integer multiples of G_{S},

[2] any pair of non-faulty intervals {I_{p}^{i}, I_{q}^{i}} is π_{I}-precise for some given π_{I} ⊆ π^{H}, where π_{I} is an integer multiple of G_{S} with ζ = (π^{H} − π_{I}) min{π^{H−}, π^{H+}}/π^{H} > G_{S}.

The convergence function OAπ^{H}_{n−f_{s}−f_{a}} applied to J_{p} respectively J_{q} at node p respectively q is translation invariant and provides intervals R_{p} = OA(J_{p}) = [T′_{p} ± α′_{p}] respectively R_{q} = OA(J_{q}) = [T′_{q} ± α′_{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 π^{H−}/π^{H} remains invariant, are as follows:

(1) The precision preservation function Φ(·), which ensures that R_{p} and R_{q} are Φ(π^{H})-correct, is

Φ(π^{H}) = π^{H}.  (20)

(2) The precision enhancement function Π(·), which ensures that the set {R_{p}, R_{q}} is π_{0}-precise with π_{0} = Π(π^{H}, π_{I}) < π^{H}, evaluates to

Π(π^{H}, π_{I}) = max\{⌈π^{H+} + \frac{π^{H−}}{π^{H}} π_{I}⌉_{G_{S}}, ⌈π^{H−} + \frac{π^{H+}}{π^{H}} π_{I}⌉_{G_{S}} \}. (21)

Proof ¿From Definition 8 of OA, it is immediately apparent that OA is translation invariant since M is. Moreover, the reference point of R_{p} = OA(J_{p}) respectively R_{q} = OA(J_{q}) is determined by applying M to the π^{H}-precision intervals associated with I_{p}^{i} ∈ J_{p} respectively I_{q}^{i} ∈ J_{q}, resulting in

R̃_{p} = M_{n_{p}}^{n−f_{s}−f_{a}}(Ĵ_{p}) and R̃_{q} = M_{n_{q}}^{n−f_{s}−f_{a}}(Ĵ_{q}).

Since any non-faulty I_{p}^{i} is π^{H}-correct according to precondition [1], it is

guaranteed that Î_{p}^{i} contains internal global time τ, and that |Î_{p}^{i}| ≤ π^{H}, so that any intersection of such intervals has these properties as well. Lemma 2 applies with n := n_{p} and f := f_{s} +f_{a} −(n−n_{p}), hence it follows that τ ∈ R̃_{p} by its item (1) and |R̃_{p}| ≤ π^{H} by its item (2) since

n_{p} − 2f − f′_{u} ≥ n − 2f_{s} − 3f_{a} + n − n_{p} ≥ n − 2f_{s} − 3f_{a} ≥ 1,  (22)

recall Assumption 1. Since OA sets the reference point T′_{p} of R̃_{p} = [T′_{p} ± π_{p}] to π^{H}-center_{G_{S}}(R̃_{p}), applying Lemma 6 provided in Appendix A yields

π_{p}^{−} = ⌊\frac{π^{H−}}{π^{H}} |R̃_{p}|⌋_{G_{S}} ≤ \frac{π^{H−}}{π^{H}} |R̃_{p}| ≤ π^{H−}

and

π_{p}^{+} = ⌈\frac{π^{H+}}{π^{H}} |R̃_{p}|⌉_{G_{S}} ≤ ⌈\frac{π^{H+}}{π^{H}} π^{H}⌉_{G_{S}} = π^{H+};

recall that π^{H+} was assumed to be an integer multiple of G_{S}. Since ref(R_{p}) = ref(R̃_{p}), the asserted π^{H}-correctness of R_{p} and hence expression (20) for Φ(·) follows. The required monotonicity of Φ(π^{H}) with respect to π^{H} is immediately apparent.

Of course, exactly the same reasoning holds for R_{q}, completing the proof of item (1).

As far as item (2) is concerned, we first recall that any pair of π^{H}-correct intervals I_{p}^{i} ∈ J_{p} and I_{q}^{i} ∈ J_{q} was assumed to be π_{I}-precise in precondition

[2]. Hence it follows that |Î_{p}^{i} ⊔ Î_{q}^{i}| ≤ π^{H} + π_{I}, since |Î_{p}^{i}|, |Î_{q}^{i}| ≤ π^{H} and |ref(I_{p}^{i}) − ref(I_{q}^{i})| ≤ π_{I} by item (2) of Lemma 1. This implies |R̃_{p} ⊔ R̃_{q}| ≤

π^{H} +π_{I} due to R̃_{p}⊔R̃_{q} ⊆ ⋂_{k=1}^{n−2f_{s}−3f_{a}} Î_{p}^{i_{k}} ⊔Î_{q}^{i_{k}}, recall item (2) of Lemma 5 and (22). Now we can apply Lemma 7 provided in Appendix A with π_{p} = π_{q} = π̄_{p} = π̄_{q} := π^{H} and π := π^{H}+π_{I}, which eventually yields |ref(R_{p})−ref(R_{q})| = |ref(R̃_{p}) − ref(R̃_{q})| ≤ Π(π^{H}, π_{I}) as given by (21). This ensures π_{0}-precision for any π_{0} with |π_{0}| = π_{0} as asserted. The required relation π_{0} < π^{H} is verified via

π_{0} − G_{S} ≤ max\{π^{H+} + \frac{π^{H−}}{π^{H}} π_{I}, π^{H−} + \frac{π^{H+}}{π^{H}} π_{I}\} = π^{H} − ζ < π^{H} − G_{S},

which follows from (21) and the condition imposed on π_{I} in precondition [2] of our theorem.

Finally, the required monotonicity of Π(π^{H}, π_{I}) with respect to π^{H} and π_{I} is obvious from (21) by recalling that the potentially problematic fractions π^{H−}/π^{H} and π^{H+}/π^{H} were assumed to be invariant. This eventually completes the proof of Theorem 1. □

Remarks 1. The above theorem considers the most general case where |R̃_{p}| and |R̃_{q}| may even be zero. A smaller Π(·) could be derived if a (reasonably large) non-zero lower bound on |R̃_{p}| and |R̃_{q}| could be guaranteed.

2. Observe that Π(π^{H}, π_{I}) given in (21) is minimized when π^{H} is symmetric, that is, when π^{H+} = π^{H−}. In that case, we obtain

π_{0} = ⌈\frac{π^{H} + π_{I}}{2} ⌉_{G_{S}} ≤ \frac{π^{H} + π_{I}}{2} + \frac{G_{S}}{2} .

This gives the maximum precision enhancement of our convergence function, refer to [Sch87]. The convergence factor is 1/2, which is the same as provided by the well-known fault-tolerant midpoint (FTM) convergence function, see [LWL88].

3. The fact that R_{p} is π^{H}-correct easily provides the “accuracy” α of our convergence function in the terminology of [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 π^{H}-correct, it follows (see [SS97a, Lem. 7]) that |α| ≤ π^{H}. Hence, OA provides the same “accuracy” as FTM and most other convergence functions, however, with the notable exception of the optimal algorithms in [FC95b] and [Sch97a].

The following Theorem 2 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 1, the intersection of certain precision intervals [3], and the accuracies of all non-faulty input intervals [4]. Consult the discussion prior to Definition 11 in Appendix C for details.

Theorem 2 (Accuracy OA) Let I_{p} = {I_{p}^{1}, …, I_{p}^{n}}, I_{q} = {I_{q}^{1}, …, I_{q}^{n}} be two ordered sets of n compatible accuracy intervals (all representing the \underline{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 1. Moreover, let the subsets of non-empty accuracy intervals among them be J_{p} ⊆ I_{p}, |J_{p}| = n_{p} ≤ n and J_{q} ⊆ I_{q}, |J_{q}| = n_{q} ≤ n and assume that

[1] any non-faulty I_{p}^{i} ∈ I_{p} as well as any non-faulty I_{q}^{i} ∈ I_{q} is π^{H}-correct for some given π^{H} with π^{H+}, π^{H−} being integer multiples of G_{S},

[2] any pair of non-faulty intervals {I_{p}^{i}, I_{q}^{i}} is π_{I}-precise for some given π_{I} ⊆ π^{H}, where π_{I} is an integer multiple of G_{S} with ζ = (π^{H} − π_{I}) min{π^{H−}, π^{H+}}/π^{H} > G_{S},

[3] for any s with both I_{p}^{s} and I_{q}^{s} being non-faulty, the intersection of the

associated precision intervals Î_{p}^{s}∩Î_{q}^{s}∩Î_{p}^{min_{p}} ∩Î_{q}^{min_{q}} respectively Î_{p}^{s}∩Î_{q}^{s}∩ Î_{p}^{max_{p}} ∩ Î_{q}^{max_{q}}, where min_{x} respectively max_{x} represents that non-faulty

node that leads to the leftmost right(Î_{x}^{min_{x}}) respectively the rightmost left(Î_{x}^{max_{x}}) for x ∈ {p, q}, has length at least ι_{s}^{+} ≥ 0 respectively ι_{s}^{−} ≥ 0 (integer multiples of G_{S}),

[4] the accuracies of any non-faulty I_{p}^{i} = [T_{p}^{i} ± α_{p}^{i}] are integer multiples of G_{S} satisfying α_{p}^{i} ⊆ β_{p}^{i} ∈ B_{p} for a given set of accuracy bounds B_{p} = {β_{p}^{1}, …, β_{p}^{n}} (and analogous for I_{q}^{i} with set of accuracy bounds B_{q}).

The convergence function OAπ^{H}_{n−f_{s}−f_{a}} applied to J_{p} respectively J_{q} at node p respectively q provides accurate intervals R_{p} = OA(J_{p}) = [T′_{p} ± α′_{p}] respectively R_{q} = OA(J_{q}) = [T′_{q} ± α′_{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 π^{H−}/π^{H} remains invariant, are as follows:

(1) The conditional accuracy preservation functions ℵ^{−}(·), ℵ^{+}(·), which guarantee α′_{p} ⊆ [−ℵ^{−}(B_{p}, π^{H}, ∀s : ι_{s}^{−}), ℵ^{+}(B_{p}, π^{H}, ∀s : ι_{s}^{+})], read

ℵ^{−}(B_{p}, π^{H}, ∀s : ι_{s}^{−}) = β_{p}^{x,−} + ⌊\frac{π^{H+}}{π^{H}} (π^{H} − ι_{x}^{−})⌋_{G_{S}},  (23)
ℵ^{+}(B_{p}, π^{H}, ∀s : ι_{s}^{+}) = β_{p}^{x,+} + ⌈\frac{π^{H−}}{π^{H}} (π^{H} − ι_{x}^{+})⌉_{G_{S}},  (24)

where x denotes the node with the n−2f_{s} −3f_{a}-largest accuracy bounds among B_{p}, that is,

β_{p}^{x,−} = max_{i:n−2f_{s}−3f_{a}}{β_{p}^{i,−}} and β_{p}^{x,+} = max_{i:n−2f_{s}−3f_{a}}{β_{p}^{i,+}}

with max_{i:m} B denoting the m-th largest element of the set B = {β^{i} : 1 ≤ i ≤ n}.

(2) The conditional intersection enhancement functions ℑ^{−}(·) respectively ℑ^{+}(·), which ensure that the set {R_{p}, R_{q}} is π_{0}^{ι_{pq}^{−}}-precise respectively π_{0}^{ι_{pq}^{+}}-precise with π_{0}^{ι_{pq}^{−}} = ℑ^{−}(π^{H}, π_{I}) respectively π_{0}^{ι_{pq}^{+}} = ℑ^{+}(π^{H}, π_{I}) for worst-case settings related to negative respectively positive accuracy, evaluate to

ℑ^{−}(π^{H}, π_{I}) = ⌈\frac{π^{H−}}{π^{H}} π_{I}⌉_{G_{S}} respectively ℑ^{+}(π^{H}, π_{I}) = ⌈\frac{π^{H+}}{π^{H}} π_{I}⌉_{G_{S}}.

(25)

Proof ¿From Definition 8, it is evident that the accuracies α′_{p}^{+}, α′_{p}^{−} in R_{p} and α′_{q}^{+}, α′_{q}^{−} in R_{q} —as well as their reference points— are integer multiples of G_{S}. Finally, item (1) of Lemma 2 applied to (19) makes sure that R_{p} and R_{q} are accurate.

Therefore, it only remains to bound α′_{p} (without loss of generality, since the analogous result for 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 α′_{p}^{+} subject to the given lower bounds ∀s : ι_{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 − 2f_{s} − 3f_{a}-largest of p’s accuracy bounds by β = max_{i:n−2f_{s}−3f_{a}}{β_{p}^{i+}}, the worst-case scenario for α′_{p}^{+} is depicted in Figure 7. Note that we will provide the detailed argument for α′_{p}^{+} only; α′_{p}^{−} is derived analogously.

[figure: I_{p}^{u_{1}}; I_{p}^{u_{n−2fs−3fa}}; π^{H−}; I_{p/q}^{min}; I_{p/q}^{max}; ι_{x}; R_{p}; I_{q}^{u_{n−2fs−3fa}}; I_{q}^{u_{1}}; R_{q}; π_{I}; β′; π^{H+}; π_{0}^{−}; π_{0}^{+}; π_{0}^{−}; π_{0}^{+}; ζ′; . ; ..; β; . ; ..; π^{H−}; π^{H+}; R]

Figure 7: Worst-case scenario for α′_{p}^{+} = β′ with resulting precision ζ′. The

intersection of the leftmost non-faulty precision interval Î_{p/q}^{min} with any nonfaulty Î_{p}^{x} has length ι_{x}. The n−2f_{s}−3f_{a} nc-unions of input intervals I⃗_{p}^{u_{i}} ⊔I⃗_{q}^{u_{i}} contain the resulting R⃗_{p} ⊔ R⃗_{q}.

First, let I⃗ = [T − π^{−}, T + α^{+}] be the mixed interval of an arbitrary accuracy interval I = [T ± α] with its associated π-precision interval Î = [T ± π]. 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 right(I⃗_{p}^{s}) = right(I_{p}^{s}) respectively left(I⃗_{p}^{s}) = left(Î_{p}^{s}), it follows that right(R⃗_{p}) = right(R_{p}) respectively left(R⃗_{p}) = left(R̂_{p}) as well. Analyzing the result of M in terms of mixed intervals, however, is easy since the hybrid fault model in Assumption 1 guarantees that the sets of mixed input intervals I⃗_{p}^{s}, I⃗_{q}^{s} are in accordance with the fault model of Definition 5, which underlies the results on Marzullo’s function M derived in Section 3.

To see that Figure 7 provides a worst-case scenario for α′_{p}^{+} = β′, we first argue that |R⃗_{p}| cannot be larger than β + π^{H−}, since item (2) of Lemma 2 in conjunction with (22) reveals that R⃗_{p} lies within at least n − 2f_{s} − 3f_{a} ≥ 1 non-faulty input intervals I⃗_{p}^{b_{k}} ∈ J_{p}. Note that it is assumed in Figure 7 that I_{p}^{u_{i}} = I_{p}^{b_{i}} has the i-th largest accuracy bound β_{p}^{i+} and I⃗_{p}^{u_{i+1}} ⊆ I⃗_{p}^{u_{i}}. This implies that left(R⃗_{p}) cannot be further left. Moreover, in an attempt to maximize β′, it could not be set further right either due to the monotonicity property (56) of π-center_{G_{S}}.

Next, from item (2) of Lemma 5 it follows that there are at least n − 2f_{s} − 3f_{a} pairs of non-faulty intervals {I_{p}^{u_{k}}, I_{q}^{u_{k}}} (present in J_{p} respectively J_{q}) such that R⃗_{p} ⊔ R⃗_{q} ⊆ ⋂_{k=1}^{n−2f_{s}−3f_{a}} I⃗_{p}^{u_{k}} ⊔ I⃗_{q}^{u_{k}}. Since the reference points (and hence the left edges of the mixed intervals) of any non-faulty pair I_{p}^{s}, I_{q}^{s} can be at most π_{I} apart according to precondition [2], left(R⃗_{q}) cannot be further left than shown in Figure 7.

Finally, as far as the worst position of right(R̃_{p}) is concerned, we know from precondition [3] of our theorem that no non-faulty precision interval Î_{p}^{s}, Î_{q}^{s} can have a right edge left of R in Figure 7. Hence, from the distributed minimal intersection property of M in item (1) of Lemma 5, it follows that both R̃_{p} and R̃_{q} must have this property as well. It follows that we have to consider right(R̃_{p}) = R and right(R̃_{q}) = R for worst-case settings with respect to β′ only, since the monotonicity property (56) of π-center_{G_{S}} implies again that setting right(R̃_{p}) further right would provide a smaller β′ only. Similarly, setting right(R̃_{q}) further right could only decrease ζ′, which would enlarge ι′_{x} in the next round and hence provide a smaller β′ then, see below.

Evaluating β′ for the above situation is simple: By using (57) and −⌈x⌉ = ⌊−x⌋ (see [Knu73, Sec. 1.2.4, Ex. 4]), we find

β′ = β + π^{H−} − ⌊\frac{π^{H−}}{π^{H}} ι_{x}⌋_{G_{S}} = β + ⌈\frac{π^{H}}{π^{H}} π^{H−} − \frac{π^{H−}}{π^{H}} ι_{x}⌉_{G_{S}},  (26)

which easily yields expression (24) for ℵ^{+}(·). The required monotonicity is immediately apparent, given that π^{H+}/π^{H} and π^{H−}/π^{H} were assumed to be invariant.

Next, we have to prove the expression for ℑ^{+}(·) = ref(R_{p})−ref(R_{q}) given in item (2) of our theorem, which is bounded by ζ′ in Figure 7. Noting that left(R_{p}) − left(R_{q}) = π_{I} here, we obtain

ζ′ = π_{I} + ⌊\frac{π^{H−}}{π^{H}} ι_{x}⌋_{G_{S}} − ⌊\frac{π^{H−}}{π^{H}} (π_{I} + ι_{x})⌋_{G_{S}}
= ⌊\frac{π^{H−}}{π^{H}} ι_{x}⌋_{G_{S}} + ⌈\frac{π^{H+}}{π^{H}} π_{I} − \frac{π^{H−}}{π^{H}} ι_{x}⌉_{G_{S}}
≤ ⌈\frac{π^{H+}}{π^{H}} π_{I}⌉_{G_{S}},  (27)

where we used the “triangle inequality” ⌈x + y⌉ ≤ ⌈x⌉ + ⌈y⌉ (see [Knu73, Sec. 1.2.4, Ex. 7]). This eventually confirms the expression for ℑ^{+}(·) in (25). The required monotonicity of ℑ^{+}(·) is again immediately apparent.

The analogous expressions for ℵ^{−}(·) respectively ℑ^{−}(·) can be obtained by considering Figure 7 mirrored at the (dashed) vertical line R and exchanging π^{H+} and π^{H−} etc. Comparing (57) and (58) reveals that ℵ^{−}(·) given by (23) follows from replacing ⌊.⌋ by ⌈.⌉ in (26). Similarly, we find

ζ′ = π_{I} + ⌈\frac{π^{H+}}{π^{H}} ι_{x}⌉_{G_{S}} − ⌈\frac{π^{H+}}{π^{H}} (π_{I} + ι_{x})⌉_{G_{S}}
= ⌈\frac{π^{H−}}{π^{H}} π_{I} + \frac{π^{H+}}{π^{H}} (π_{I} + ι_{x})⌉_{G_{S}} − ⌈\frac{π^{H+}}{π^{H}} (π_{I} + ι_{x})⌉_{G_{S}}
≤ ⌈\frac{π^{H−}}{π^{H}} π_{I}⌉_{G_{S}} + ⌈\frac{π^{H+}}{π^{H}} (π_{I} + ι_{x})⌉_{G_{S}} − ⌈\frac{π^{H+}}{π^{H}} (π_{I} + ι_{x})⌉_{G_{S}}
= ⌈\frac{π^{H−}}{π^{H}} π_{I}⌉_{G_{S}},

which confirms the expression for ℑ^{−}(·) in (25).

To complete the proof of our theorem, it only remains to show that the worst-case scenario considered here is also globally valid. It is of course locally valid, in the sense that there is no scenario that provides a worse β′ for the given ι_{x}. However, the resulting ζ′ is quite small, and since ζ′ determines ι_{x} —and hence β′— in the next round^{7}, the question arises whether a locally suboptimal setting could provide a worse overall accuracy. In view of (24) and (23), it is sufficient to check whether β′ + ζ′ = right(R_{p}) − ref(R_{q}) is maximal in the scenario of Figure 7, which is of course true by construction. This eventually completes the proof of Theorem 2. □

Remarks 1. There is a straightforward modification of OA that improves accuracy by exploiting further information from reference point setting. More specifically, any interval I ∈ J satisfying Î∩M_{n′}^{n−f_{s}−f_{a}}(Ĵ) = ∅ is faulty since its associated π^{H}-precision interval does not contain internal global time τ and may thus be discarded prior to computing the accuracy interval in (19). Item (3) of Lemma 3 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.

2. Apart from clock state synchronization elaborated on in this paper, Theorems 1 and 2 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, ρ ≤ 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 [SS97a], was conducted in [Sch97c]. It shows that any convergence function suitable for interval-based clock synchronization —like OA— can be reused in the rate setting as well.

3. It is interesting to note that statements and proof of our major Theorems 1 and 2 apply literally when the Marzullo function employed for computing the reference point (18) in OA’s Definition 8 is replaced by certain other interval-based functions. For example, it is possible to recast the wellknown fault-tolerant midpoint convergence function (FTM) of [LWL88] into an equivalent interval-based version FTM-I (similar to the one employed in [Lam87]) that operates on equally-sized intervals. Recall that the input precision intervals in (18) are obtained by mounting the same interval π^{H} at the accuracy intervals’ reference points, resulting in identical length. Similar pigeonhole principle proofs as in Section 3 can then be used to show that the pivotal upper bounds of Lemma 2 and 4 for M apply to FTM-I as well.

7Note that ι_{x} does actually not depend upon x since ζ′ is uniformly valid, see Theorem 4.

5 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 5 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 ([SS97a, Def. 7]) in Definition 9; consult [SS97a, Assum. 1–4] 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 [SS97a, Thm. 2] for details.

Theorem 3 (Precision Algorithm OA) For the system model complying to [SS97a, Assum. 1–4] and the fault model in Assumption 1, the orthogonal accuracy algorithm with instantaneous clock correction, transmission delay compensation

Δ ≥ 2ε_{max} + ε_{max}^{+} + (B + 3)u_{max} + 2G + G_{S} + δ_{max}(1 + ρ_{max}^{−})
+(2P + Λ + Ω + 2Γ_{max} − 2Γ_{min} − 2δ_{min})ρ_{max}
+O(P ρ_{max}^{2} + Gρ_{max} + ε_{max}ρ_{max}),  (28)

and the (symmetric!)

π^{H} = π_{0} + 2u_{max} + \overline{G} + ε_{max} + (P + Γ_{max} − Γ_{min} − δ_{min})ρ_{max}
+O(P ρ_{max} + G + ε_{max})ρ_{max}  (29)

used in OAπ^{H}_{n−f_{s}−f_{a}} requires O(n log n) computation time to synchronize the (non-faulty) clocks of n nodes as follows:

(1) Initial worst-case precision (that is, the precision at the beginning of each round of the slowest non-faulty clock)

π_{0,max} = π_{0}+u_{max}+G+(Γ_{max}−Γ_{min})ρ_{max}+O(P ρ_{max}^{2}+Gρ_{max}+ε_{max}ρ_{max}) (30)

where π_{0} = [−π_{0}^{−}, π_{0}^{+}] is given by

π_{0}^{−} = \frac{1}{2}(ε_{max} + Bu_{max} + G + G_{S} + (Λ + Ω + Δ + Γ_{max} − δ_{min})ρ_{max})
+2u_{max}^{+} + ε_{max}^{+} + (P + Γ_{max} − Γ_{min} − δ_{min})ρ_{max}^{+}
+O(P ρ_{max}^{2} + Gρ_{max} + ε_{max}ρ_{max})  (31)
π_{0}^{+} = \frac{1}{2}(ε_{max} + Bu_{max} + G + G_{S} + (Λ + Ω + Δ + Γ_{max} − δ_{min})ρ_{max})
+2u_{max}^{−} + ε_{max}^{−} + G + (P + Γ_{max} − Γ_{min} − δ_{min})ρ_{max}^{−}
+O(P ρ_{max}^{2} + Gρ_{max} + ε_{max}ρ_{max}),  (32)

so that

π_{0} = 2ε_{max} + (B + 2)u_{max} + 2G + G_{S}  (33)
+(P + Λ + Ω + Δ + 2Γ_{max} − Γ_{min} − 2δ_{min})ρ_{max}
+O(P ρ_{max}^{2} + Gρ_{max} + ε_{max}ρ_{max}).  (34)

(2) Overall worst-case precision π_{max} satisfying

π_{max} = 2ε_{max} + (B + 3)u_{max} + 3G + G_{S}
+(2P + Λ + Ω + Δ + 2Γ_{max} − Γ_{min} − 2δ_{min})ρ_{max}
+ max{ε_{max}^{+} + 2u_{max}^{+} + (2Γ_{max} − 2Γ_{min} − δ_{min})ρ_{max}^{+},
ε_{max}^{−} + 2u_{max}^{−} + G + (2Γ_{max} − 2Γ_{min} − δ_{min})ρ_{max}^{−}, 0}
+O(P ρ_{max}^{2} + Gρ_{max} + ε_{max}ρ_{max}).  (35)

(3) Any two non-faulty nodes p, q resynchronize within real-time t_{p}^{R} − t_{q}^{R} satisfying

Γ_{p} − Γ_{q} − π_{P} ≤ t_{p}^{R} − t_{q}^{R} ≤ Γ_{p} − Γ_{q} + π_{P}

for

π_{P} = π_{0} + u_{max} + P ρ_{max} + O(P ρ_{max}^{2} + Gρ_{max} + ε_{max}ρ_{max}).  (36)

(4) Adjustments of at most Υ are applied to the local clock of any non-faulty node, which are bounded according to −π^{−} ≤ Υ ≤ π^{+} with

π^{−} = 2ε_{max} + (B + 3)u_{max} + 2G + G_{S}  (37)
+(2P + Λ + Ω + Δ + 2Γ_{max} − Γ_{min} − 2δ_{min})ρ_{max} + ε_{max}^{+} + u_{max}^{+}
+(Γ_{max} − Γ_{min} − δ_{min})ρ_{max}^{+} + O(P ρ_{max}^{2} + Gρ_{max} + ε_{max}ρ_{max}),

π^{+} = 2ε_{max} + (B + 3)u_{max} + 3G + G_{S}  (38)
+(2P + Λ + Ω + Δ + 2Γ_{max} − Γ_{min} − 2δ_{min})ρ_{max} + ε_{max}^{−} + u_{max}^{−}
+(Γ_{max} − Γ_{min} − δ_{min})ρ_{max}^{−} + O(P ρ_{max}^{2} + Gρ_{max} + ε_{max}ρ_{max}).

Proof The computational complexity of the orthogonal accuracy algorithm is primarily determined by the complexity of computing the convergence function OA, which is O(n log n) due to the two evaluations of M employed in OA, recall Definition 8 and 6.

By item (1) of Theorem 5, π_{0} is the solution of the equation |π_{0}| = Π(π^{H}, π_{I}) involving OA’s precision enhancement function Π(·) given by (21). Precision enhancement is optimal if π^{H} given by (78) is a symmetric interval, recall the remarks following Theorem 1. Note that the condition imposed on π_{I} in precondition [2] of Theorem 1 is also amply fulfilled in this case, just compare (79) and (29). Hence, writing π^{H} = π_{0} + π_{1} with

π_{1} = 2u_{max} + \overline{G} + ε_{max} + (P + Γ_{max} − Γ_{min} − δ_{min})ρ_{max}  (39)
+O(P ρ_{max} + G + ε_{max})ρ_{max},

we exploit the freedom of choosing an arbitrary reference point of π_{0} to enforce this symmetry: Setting

π_{0} = [−(⌈π_{I}/2⌉_{G_{S}} + π_{1}^{+}), ⌈π_{I}/2⌉_{G_{S}} + π_{1}^{−}]  (40)

such that π_{0} = 2⌈π_{I}/2⌉_{G_{S}} + π_{1} provides a symmetric interval

π^{H} = π_{0} + π_{1} = [−(⌈π_{I}/2⌉_{G_{S}} + π_{1}), ⌈π_{I}/2⌉_{G_{S}} + π_{1}]  (41)

with π^{H} = 2⌈π_{I}/2⌉_{G_{S}} + 2π_{1}. Evaluating Π(π^{H}, π_{I}) given by (21) yields

max\{⌈π^{H+} + \frac{π^{H−}}{π^{H}} π_{I}⌉_{G_{S}}, ⌈π^{H−} + \frac{π^{H+}}{π^{H}} π_{I}⌉_{G_{S}} \} =

= ⌈\frac{π^{H} + π_{I}}{2} ⌉_{G_{S}} = ⌈⌈π_{I}/2⌉_{G_{S}} + π_{1} + π_{I}/2⌉_{G_{S}}
= 2⌈π_{I}/2⌉_{G_{S}} + π_{1} = π_{0}  (42)

as required; recall that π_{1} and all other precision values are integer multiples of G_{S} since its constituting parameters have this property, see Definition 9.

Plugging in π_{1}^{+}, π_{1}^{−} resulting from (39) and ⌈π_{I}/2⌉_{G_{S}} ≤ π_{I}/2 + G_{S}/2 with π_{I} = |π_{I}| from (79) into (40) confirms the values of π_{0}^{−}, π_{0}^{+} given in (31) and (32). Addition or, alternatively, substitution in (42) provides the value of π_{0} stated in (34). Last but not least, (30) providing π_{0,max} is only a restatement of (74).

Next, the value π_{P} given in (36) is obtained by plugging in (conservative) maximum bounds for u_{p/q} and ρ_{p/q} in (82). Plugging in the swapped \overline{Φ}(π^{H}) = \overline{π}^{H} according to item (1) of Theorem 1 and the definition (29) of π^{H} into (81) provides

π = \overline{π}_{0} + 2\overline{u}_{max} + G + \overline{ε}_{max} + (P + Γ_{max} − Γ_{min} − δ_{min}
+O(P ρ_{max} + G + ε_{max}))\overline{ρ}_{max}
+π_{0} + u_{max} + (P + O(P ρ_{max} + G + ε_{max}))ρ_{max},

from where the values of π^{−}, π^{+} given in (37) and (38) follow easily. Now it is possible to evaluate (80) in Theorem 5, which confirms the value of π_{max} stated in (35).

The proof of Theorem 3 is almost completed; we only have to justify the value of Δ given in (28). Plugging in the expressions for π_{0} and π = O(ε_{max} + G + P ρ_{max}) into the definition of Δ in (65), we easily obtain

Δ ≥ \frac{1}{1 + ρ_{max}^{+}} (2ε_{max} + (B + 3)u_{max} + 2G + G_{S} + δ_{max} + ε_{max}^{+}
+(2P + Λ + Ω + Δ + 2Γ_{max} − 2Γ_{min} − 2δ_{min})ρ_{max}
+O(P ρ_{max}^{2} + Gρ_{max} + ε_{max}ρ_{max}))
= \frac{Z + Δρ_{max}}{1 + ρ_{max}^{+}} .

Solving this for Δ yields

Δ ≥ \frac{Z}{1 − ρ_{max}^{−}} = Z(1 + ρ_{max}^{−} + O((ρ_{max}^{−})^{2}))
= 2ε_{max} + ε_{max}^{+} + (B + 3)u_{max} + 2G + G_{S} + δ_{max}
+(2P + Λ + Ω + 2Γ_{max} − 2Γ_{min} − 2δ_{min})ρ_{max}
+δ_{max}ρ_{max}^{−} + O(P ρ_{max}^{2} + Gρ_{max} + ε_{max}ρ_{max}).

This eventually completes the proof of Theorem 3. □

Remarks 1. For usual settings, the O(·)-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.

2. The precision results above are valid for \underline{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 ρ_{p} = ρ_{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 π^{H}!

3. With respect to worst-case precision, our orthogonal accuracy algorithm is equivalent to the well-known fault tolerant midpoint algorithm (FTM) of [LWL88], see Remark 3 following Theorem 2. FTM has the same computational complexity O(n log n) and the same worst-case precision

π_{max} ≈ 5ε + 4P ρ

(in a comparable setting); our terminology relates to the one of [LWL88] by π_{max} = γ, ε_{max} = 2ε and ρ_{max} = 2ρ. Both algorithms require initially synchronized clocks as well. Our algorithm is hence slightly suboptimal with respect to worst-case precision: π_{max} exceeds the provably necessary and tight lower bound 4ε + 4P ρ (see [FC95a], [FC95b]) by ε. The maximum correction Υ ≈ 5ε + 4P ρ applied to the clock of a non-faulty node exceeds the tight lower bound of 2P ρ considerably.

The next theorem provides algorithm OA’s worst-case behavior with respect to accuracy.

Theorem 4 (Accuracy Algorithm OA) For the system model complying to [SS97a, Assum. 1–4] and the fault model in Assumption 1, the accuracies α_{q}^{k+1,−}, α_{q}^{k+1,+} of a non-faulty node q’s accuracy interval A_{q}^{k+1}(t_{q}^{k+1}) = [T_{q}^{k+1} ± α_{q}^{k+1}] at the beginning of round k + 1, k ≥ 0, as computed by the orthogonal accuracy algorithm OA with transmission delay compensation Δ given by (28) and π^{H} given by (29), are integer multiples of G_{S} satisfying the following properties:

(1) The interval of accuracy satisfies α_{q}^{k+1} ⊆ β_{q}^{k+1} with

β_{q}^{k+1,−} = max_{p:n−2f_{s}−3f_{a}}{{β_{p}^{k,−} + u_{p}^{−} + u_{q}^{−} + G + G_{A} + ε_{pq}^{−} + (P − Δ − Γ_{p})ρ_{p}^{−}

+(Γ_{q} + Δ − δ_{pq})ρ_{q}^{−} + (Λ + Ω) max{ρ_{q}^{−} − ρ_{p}^{−}, 0}}_{p≠q}

∪{β_{q}^{k,−} + u_{q}^{−} + P ρ_{q}^{−}}}

+⌊π^{H}/4⌋_{G_{S}} + O(P ρ_{max}^{2} + Gρ_{max} + ε_{max}ρ_{max})  (43)
≤ max_{p:n−2f_{s}−3f_{a}}{β_{p}^{k,−}} + u_{max}^{−} + G + G_{A} + ε_{max}^{−}

+(P − Δ − Γ_{min})ρ_{max}^{−} + u_{q}^{−} + (Γ_{q} + Δ − δ_{min})ρ_{q}^{−}

+⌊π^{H}/4⌋_{G_{S}} + O(P ρ_{max}^{2} + Gρ_{max} + ε_{max}ρ_{max}),  (44)
β_{q}^{0,−} = α_{q}^{0,−} + ⌈π^{H}/4⌉_{G_{S}},  (45)
β_{q}^{k+1,+} = max_{p:n−2f_{s}−3f_{a}}{{β_{p}^{k,+} + u_{p}^{+} + u_{q}^{+} + G_{A} + ε_{pq}^{+} + (P − Δ − Γ_{p})ρ_{p}^{+}

+(Γ_{q} + Δ − δ_{pq})ρ_{q}^{+} + (Λ + Ω) max{ρ_{q}^{+} − ρ_{p}^{+}, 0}}_{p≠q}

∪{β_{q}^{k,+} + u_{q}^{+} + P ρ_{q}^{+}}}

+⌈π^{H}/4⌉_{G_{S}} + O(P ρ_{max}^{2} + Gρ_{max} + ε_{max}ρ_{max})  (46)
≤ max_{p:n−2f_{s}−3f_{a}}{β_{p}^{k,+}} + u_{max}^{+} + G_{A} + ε_{max}^{+} + (P − Δ − Γ_{min})ρ_{max}^{+}

+u_{q}^{+} + (Γ_{q} + Δ − δ_{min})ρ_{q}^{+}

+⌈π^{H}/4⌉_{G_{S}} + O(P ρ_{max}^{2} + Gρ_{max} + ε_{max}ρ_{max}),  (47)
β_{q}^{0,+} = α_{q}^{0,+} + ⌊π^{H}/4⌋_{G_{S}},  (48)

where max_{p:m} B denotes the m-th largest element of the set B = {β_{p} : 1 ≤ p ≤ n}, α_{q}^{0} ⊆ π_{0} is the initial interval of accuracies, and

π^{H} = 3ε_{max} + (B + 4)u_{max} + 3G + G_{S}
+(2P + Λ + Ω + Δ + 3Γ_{max} − 2Γ_{min} − 3δ_{min})ρ_{max}
+O(P ρ_{max}^{2} + Gρ_{max} + ε_{max}ρ_{max}),  (49)

note that ⌊π^{H}/4⌋_{G_{S}} ≤ π^{H}/4 and ⌈π^{H}/4⌉_{G_{S}} ≤ π^{H}/4 + G_{S}/2.

(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 ≥ 0, reads

T_{q}^{k+1} − t_{q}^{R,k} ≤ π_{0}^{−} + (k + 1)(2u_{max}^{−} + G + ε_{max}^{−}
+(P + Γ_{max} − Γ_{min} − δ_{min})ρ_{max}^{−}
+O(P ρ_{max}^{2} + Gρ_{max} + ε_{max}ρ_{max})),  (50)

T_{q}^{k+1} − t_{q}^{R,k} ≥ −π_{0}^{+} − (k + 1)(2u_{max}^{+} + ε_{max}^{+}
+(P + Γ_{max} − Γ_{min} − δ_{min})ρ_{max}^{+}
+O(P ρ_{max}^{2} + Gρ_{max} + ε_{max}ρ_{max})),  (51)

where π_{0}^{−} and π_{0}^{+} are given by (31) and (32), respectively.

(3) The inverse rate r_{q} = lim_{k→∞} \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

[1 ± (ρ_{max} + \frac{2u_{max} + \overline{G} + ε_{max} + (Γ_{max} − Γ_{min} − δ_{min})ρ_{max}}{P}

+O(P ρ_{max} + G + ε_{max})ρ_{max})].  (52)

Proof We showed in the proof of Theorem 3 that π^{H} given by (29), which immediately leads to (49), is a symmetric interval, hence π^{H+}/π^{H} = π^{H−}/π^{H} = 1/2. Since both π^{H−} and π^{H+} are integer multiples of G_{S}, it follows that the error in estimating ⌈π^{H}/4⌉_{G_{S}} by π^{H}/4 is at most G_{S}/2 as asserted.

According to item (0) of Theorem 5, the bounds β_{q}^{k+1,−} respectively β_{q}^{k+1,+} are just OA’s accuracy preservation functions ℵ^{−}(·) respectively ℵ^{+}(·) derived in item (1) of Theorem 2: For round k = 0, evaluating (73) according to the initial synchronization assumption in item (0) of Definition 9 forces us to assume a zero-length common intersection ι_{s}^{0,−} = ι_{s}^{0,+} = 0 for any node s. Plugging this into (23) respectively (24) governed by (66) and using (67) provides

ℵ^{−}(B_{q}^{1}, π^{H}, ∀s : 0) = max_{i:n−2f_{s}−3f_{a}}{β_{i}^{0,−} + ω_{q}^{i,−}} + π^{H+}
= max_{i:n−2f_{s}−3f_{a}}{α_{i}^{0,−} + ω_{q}^{i,−}} + ⌈π^{H}/4⌉_{G_{S}} + ⌊π^{H}/4⌋_{G_{S}}
ℵ^{+}(B_{q}^{1}, π^{H}, ∀s : 0) = max_{i:n−2f_{s}−3f_{a}}{β_{i}^{0,+} + ω_{q}^{i,+}} + π^{H−}
= max_{i:n−2f_{s}−3f_{a}}{α_{i}^{0,+} + ω_{q}^{i,+}}
+⌈π^{H}/4⌉_{G_{S}} + ⌊π^{H}/4⌋_{G_{S}}  (53)

where we used π^{H}/2 − ⌈π^{H}/4⌉_{G_{S}} = ⌊π^{H}/4⌋_{G_{S}}. For round k ≥ 1, we have ι_{s}^{k} = ι_{s}^{k,−} = ι_{s}^{k,+} = π_{0} − ⌈π_{I}/2⌉_{G_{S}} uniformly for any node s due to (71) respectively (72) in conjunction with (25). Therefore,

\frac{1}{2}(π^{H} − ι_{s}^{k}) = \frac{π^{H} − π_{0} + ⌈π_{I}/2⌉_{G_{S}}}{2} = \frac{π_{1} + ⌈π_{I}/2⌉_{G_{S}}}{2} = π^{H}/4,

where we used (41). Plugging this into (23) respectively (24) and using (66) and (67) again provides

ℵ^{−}(B_{q}^{k+1}, π^{H}, ∀s : ι_{s}^{k,−}) = max_{i:n−2f_{s}−3f_{a}}{β_{i}^{k,−} + ω_{q}^{i,−}} + ⌊π^{H}/4⌋_{G_{S}}
ℵ^{+}(B_{q}^{k+1}, π^{H}, ∀s : ι_{s}^{k,+}) = max_{i:n−2f_{s}−3f_{a}}{β_{i}^{k,+} + ω_{q}^{i,+}} + ⌈π^{H}/4⌉_{G_{S}}. (54)

Replacing i by p and plugging in the definition of ω_{q}^{p} given in (67) and (68), expressions (43) and (46) follow. Uniformly bounding the terms that depend on p by their maximum values and applying Lemma 8 readily confirms (44) and (47); note that a certain technical condition in [SS97a, (16)], namely, δ_{min}ρ_{max} ⊆ ε_{max}, ensures that the derived bound is valid for p = q as well. To justify the initial values (45) and (48), we just note that (53) and (54) differ only by ⌊π^{H}/4⌋_{G_{S}}, which can conveniently be put into β_{q}^{0,+} and β_{q}^{0,−}.

Turning our attention to traditional accuracy, we first plug in OA’s precision preservation function Φ(π^{H}) = π^{H} into (84) to obtain

T_{q}^{k+1} − t_{q}^{R,k} ∈ \overline{π}_{0} + (k + 1)(\overline{π}^{H} − \overline{π}_{0});  (55)

inserting the swapped expression for π^{H} −π_{0} obtained from (29) easily yields (50) and (51). Finally, plugging in π^{H} − π_{0} into (85) also justifies expression (52) for the inverse rate of the synchronized clock, completing the proof of Theorem 4. □

Remarks 1. OA provides the same, slightly suboptimal worst-case traditional accuracy and drift as the FTM algorithm of [LWL88]: The synchronized clocks drift away from real-time by at most the maximum drift ρ_{max} of the (worst) physical clock plus some smaller terms. Note that it has been proved in [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 [ST87], [FC95b], and [Sch97a].

2. 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 4 for the simplified worst-case parameter setting ρ_{p} = ρ_{max} := [−ρ, ρ], ε_{pq} = ε_{max} := [−ε, ε], u_{max} := [−u, u], it is obvious that β_{q}^{k} = β^{k} is the same for any q. Plugging in those settings into expression (49) for π^{H}, we find

π^{H}/4 = 3ε/2 + (B + 4)u/2 + 3G/4 + G_{S}/4
+(P + \frac{Λ + Ω + Δ + 3Γ_{max} − 2Γ_{min} − 3δ_{min}}{2} )ρ
+O(P ρ^{2} + Gρ + ερ),

and feeding everything into the formulas for negative accuracy (44) and positive accuracy (47) yields

β^{k+1,−} ≤ β^{k,−} + 5ε/2 + (B + 8)u/2 + 7G/4 + G_{A} + G_{S}/4

+(2P + Λ/2 + Ω/2 + Δ/2 + 5Γ_{max}/2 − 2Γ_{min} − 5δ_{min}/2)ρ

+O(P ρ^{2} + Gρ + ερ)
β^{k+1,+} ≤ β^{k,+} + 5ε/2 + (B + 8)u/2 + 3G/4 + G_{A} + 3G_{S}/4

+(2P + Λ/2 + Ω/2 + Δ/2 + 5Γ_{max}/2 − 2Γ_{min} − 5δ_{min}/2)ρ

+O(P ρ^{2} + Gρ + ερ).

Ignoring smaller order terms, this means that both positive and negative accuracy could possibly grow as much as 2P ρ + 5ε/2 during each round.

Plugging in the above parameter settings in (50) respectively (51), it turns out that traditional accuracy can increase respectively decrease essentially by P ρ + ε 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.

3. There are several directions one can follow in order to devise convergence functions that behave better with respect to the accuracy bounds:

• One should consider algorithms that maintain precision and accuracy not orthogonally but rather in an integrated way.

• 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 Υ, see Remark 3 following Theorem 3) that are incompatible with the progress of real-time. The optimal precision convergence function OP analyzed in [Sch97a] shows how far one can get with this approach.

• There might be ways of limiting the adverse effects of faulty clocks.

6 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 [SS97a], 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 [SS97a]. Based upon a thorough investigation of the worst-case performance of M, we provided accurate expressions for all worstcase 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 fault-tolerant midpoint (FTM) algorithm of [LWL88]: Maximum precision 5ε + 4P ρ, maximum clock correction 5ε+4P ρ, and global drift ρ + 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 ρ + 5ε/2 during each round, which is more than twice the worst-case growth P ρ + ε 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 12u + 4G) upon achievable worst-case precision and accuracy. This makes clear that any attempt to approach 1 μs worst-case precision —as targeted by our SynUTC-project, see [SKM^{+}00]— must utilize clocks with G, u ≪ 1μ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.

Appendix A: Technical Lemmas

Lemma 6 (Properties of Discrete Reference Point Setting) Let I = [a, b] with 0 ≤ a ≤ b being integer multiples of G_{S} > 0 and an arbitrary interval π = [−π^{−}, π^{+}] with π = π^{−} + π^{+} > 0 be given. Then,

π-center_{G_{S}}([a, b]) ≤ π-center_{G_{S}}([a + x, b + y])  (56)

for any x, y ≥ 0 being integer multiples of G_{S}, and the accuracies in the interval [r±α] obtained from I by setting the reference point to r = π-center_{G_{S}}(I) satisfy

α^{−} = ⌊\frac{π^{−}}{π} |I|⌋_{G_{S}},  (57)
α^{+} = ⌈\frac{π^{+}}{π} |I|⌉_{G_{S}}.  (58)

Proof Monotonicity (56) follows immediately from the definition (17) of π-center_{G_{S}} and monotonicity of ⌊x⌋. The expressions for positive and negative accuracy yield

α^{−} = ⌊\frac{π^{−}b + π^{+}a}{π}⌋_{G_{S}} − a = ⌊\frac{π^{−}b + π^{+}a − πa}{π}⌋_{G_{S}} = ⌊\frac{π^{−}}{π} |I|⌋_{G_{S}}

and

α^{+} = b − ⌊\frac{π^{−}b + π^{+}a}{π}⌋_{G_{S}} = b + ⌈−\frac{π^{−}b + π^{+}a}{π}⌉_{G_{S}} = ⌈\frac{π^{+}}{π} |I|⌉_{G_{S}},

where we used the well-known fact −⌈x⌉ = ⌊−x⌋ (see, for example [Knu73, Sec. 1.2.4, Ex. 4]). □

Lemma 7 (Precision Enhancement) Let I_{p}, I_{q} be two consistent intervals with length 0 ≤ |I_{p}| ≤ π̄_{p}, 0 ≤ |I_{q}| ≤ π̄_{q} being integer multiples of G_{S}, and ref(I_{p}) = π_{p}-center_{G_{S}}(I_{p}), ref(I_{q}) = π_{q}-center_{G_{S}}(I_{q}) for some π_{p} = [−π_{p}^{−}, π_{p}^{+}] and π_{q} = [−π_{q}^{−}, π_{q}^{+}]. If |I_{p} ⊔ I_{q}| ≤ π with max{π̄_{p}, π̄_{q}} ≤ π ≤ π̄_{p} + π̄_{q}, then

|ref(I_{p}) − ref(I_{q})| ≤

≤ \{ \begin{matrix}max\{⌈\frac{π_{q}^{−}}{π_{q}} π̄_{q} + \frac{π_{p}^{+}}{π_{p}} (π − π̄_{q})⌉_{G_{S}}, ⌈\frac{π_{p}^{−}}{π_{p}} π̄_{p} + \frac{π_{q}^{+}}{π_{q}} (π − π̄_{p})⌉_{G_{S}} \} & if \frac{π_{q}^{−}}{π_{q}} ≥ \frac{π_{p}^{+}}{π_{p}}, \\ max\{⌈\frac{π_{p}^{+}}{π_{p}} π̄_{p} + \frac{π_{q}^{−}}{π_{q}} (π − π̄_{p})⌉_{G_{S}}, ⌈\frac{π_{q}^{+}}{π_{q}} π̄_{q} + \frac{π_{p}^{−}}{π_{p}} (π − π̄_{q})⌉_{G_{S}} \} & otherwise. \end{matrix}

Proof Apart from discreteness of π_{p}-center_{G_{S}}, this is a straightforward linear programming problem. One has to look out for an arrangement of the consistent intervals I_{p} = [a, b] and I_{q} = [c, d] that maximizes the distance of their reference points. More specifically, recalling the definition of π-center_{G_{S}} (Definition 7), we are interested in

u = min\{⌊\frac{π_{p}^{+}a + π_{p}^{−}b}{π_{p}}⌋_{G_{S}} − ⌊\frac{π_{q}^{+}c + π_{q}^{−}d}{π_{q}}⌋_{G_{S}} \}  (59)

subject to b − a ≤ π̄_{p}, a − b ≤ 0, d − c ≤ π̄_{q}, c − d ≤ 0, b ≤ π, d ≤ π, c ≤ b, a ≤ d, where a, b, c, d ≥ 0 are integer multiples of G_{S}. Note that (59) covers arrangements where ref(I_{p}) ≤ ref(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

\frac{π_{q}^{−}}{π_{q}} ≥ \frac{π_{p}^{+}}{π_{p}} ,  (60)

the maximum distance of the reference points occurs when I_{q} is made as large as possible, that is, |I_{q}| = π̄_{q}, leaving at most |I_{p}| = π − π̄_{q} for I_{p}; recall that we assumed π ≤ π̄_{p} + π̄_{q}.

Returning to the discrete case, this suggests that the minimum value of (59) satisfies

−u = ⌈\frac{π_{p}^{+}}{π_{p}} ⌊π − π̄_{q}⌋_{G_{S}} ⌉_{G_{S}} + ⌊\frac{π_{q}^{−}}{π_{q}} π̄_{q}⌋_{G_{S}} ≤ ⌈\frac{π_{p}^{+}}{π_{p}} (π − π̄_{q}) + \frac{π_{q}^{−}}{π_{q}} π̄_{q}⌉_{G_{S}}, (61)

recall Lemma 6; the upper bound follows easily from moving the second term into the first one and then omitting ⌊·⌋_{G_{S}}.

However, we have to confirm that discreteness of π-center_{G_{S}} does not impose a different maximum value. More specifically, we have to show that —starting from (61)— shrinking |I_{q}| = π̄_{q} by kG_{S} for some integer k ≥ 0 and simultaneously enlarging |I_{p}| = ⌊π−π̄_{q}⌋_{G_{S}} ≤ π−π̄_{q} by the same amount does not lead to a larger value of −u. For any k ≥ 0, we find

−u(k) = ⌈\frac{π_{p}^{+}}{π_{p}} (⌊π − π̄_{q}⌋_{G_{S}} + kG_{S})⌉_{G_{S}} + ⌊\frac{π_{q}^{−}}{π_{q}} (π̄_{q} − kG_{S})⌋_{G_{S}}
≤ ⌈\frac{π_{p}^{+}}{π_{p}} (⌊π − π̄_{q}⌋_{G_{S}} + kG_{S}) + \frac{π_{q}^{−}}{π_{q}} (π̄_{q} − kG_{S})⌉_{G_{S}}
≤ ⌈\frac{π_{p}^{+}}{π_{p}} ⌊π − π̄_{q}⌋_{G_{S}} + \frac{π_{q}^{−}}{π_{q}} π̄_{q}⌉_{G_{S}},  (62)

by virtue of condition (60), thus confirming our conjecture (61).

If, on the other hand, condition (60) is not true, the minimum (considering G_{S} = 0 first) occurs when I_{p} is made as large as possible, providing the value

−u′ = \frac{π_{p}^{+}}{π_{p}} π̄_{p} + \frac{π_{q}^{−}}{π_{q}} (π − π̄_{p}).  (63)

As before, this suggests the minimum value

−u′ = ⌈\frac{π_{p}^{+}}{π_{p}} π̄_{p}⌉_{G_{S}} + ⌊\frac{π_{q}^{−}}{π_{q}} ⌊π − π̄_{p}⌋_{G_{S}} ⌋_{G_{S}} ≤ ⌈\frac{π_{p}^{+}}{π_{p}} π̄_{p} + \frac{π_{q}^{−}}{π_{q}} (π − π̄_{p})⌉_{G_{S}} (64)

for the discrete case. For any k ≥ 0, we find

−u′(k) = ⌈\frac{π_{p}^{+}}{π_{p}} (π̄_{p} − kG_{S})⌉_{G_{S}} + ⌊\frac{π_{q}^{−}}{π_{q}} (⌊π − π̄_{p}⌋_{G_{S}} + kG_{S})⌋_{G_{S}}
≤ ⌈\frac{π_{p}^{+}}{π_{p}} (π̄_{p} − kG_{S}) + \frac{π_{q}^{−}}{π_{q}} (⌊π − π̄_{p}⌋_{G_{S}} + kG_{S})⌉_{G_{S}}
≤ ⌈\frac{π_{p}^{+}}{π_{p}} π̄_{p} + \frac{π_{q}^{−}}{π_{q}} ⌊π − π̄_{p}⌋_{G_{S}} ⌉_{G_{S}},

which also confirms (64) and completes the case of arrangements ref(I_{p}) ≤ ref(I_{q}).

To establish the result for reverse arrangements, we only have to exchange p and q. Rewriting condition (60) appropriately reads

\frac{π_{p}^{−}}{π_{p}} = 1 − \frac{π_{p}^{+}}{π_{p}} ≥ 1 − \frac{π_{q}^{−}}{π_{q}} = \frac{π_{q}^{+}}{π_{q}} ,

which is fulfilled if and only if (60) is satisfied. Exchanging p and q in (61) and (64) and taking the maximum of the appropriate values eventually completes the proof of the lemma. □

Lemma 8 (Uniform Bounds m-Maxima) Let S = {z_{i}}_{1≤i≤n} with z_{i} = x_{i} +y_{i} and y be given, such that x_{i} ≤ x_{j} for i < j and y_{i} ≤ y for 1 ≤ i, j ≤ n. If \overline{S} = \{w_{i}\}_{1≤i≤n} with w_{i} = x_{i} + y for 1 ≤ i ≤ n, then the respective m-th largest elements satisfy max_{m} S ≤ max_{m} \overline{S}.

Proof If max_{m} S = z_{v} for some 1 ≤ v ≤ n, we claim that there exists some index p ≤ n − m + 1 such that z_{v} ≤ z_{p}, since otherwise z_{1} < z_{v}, z_{2} < z_{v}, …, z_{n−m+1} < z_{v}. However, z_{v} is the m-largest element in S, which means that there are only n − m z_{i}’s that could possible satisfy z_{i} < z_{v}, providing the required contradiction. Since of course w_{i} ≤ w_{j} for i < j, we have max_{m} S = z_{v} ≤ z_{p} ≤ w_{p} ≤ w_{n−m+1} = max_{m} \overline{S}. □

Appendix B: Generic Algorithm

This appendix contains a restatement of the generic interval-based clock synchronization algorithm of [SS97a], along with a brief mentioning of the many parameters found in our system model. It is provided for the ease of reference only; please consult the original paper for details.

Definition 9 (Generic Algorithm [SS97a, Def. 7]) The parameters required for the instance of the algorithm running at node q,

• node q’s intrinsic inverse rate deviation bound ρ_{q} and uniform bound ρ_{max} ⊇ ⋃_{p} ρ_{p} with ρ_{max} = |ρ_{max}| = ρ_{max}^{−} + ρ_{max}^{+} ([SS97a, Assum. 2]),

• clock granularity G, clock setting granularity G_{S}, node q’s maximum rate adjustment uncertainty u_{q} = [−u_{q}^{−}, u_{q}^{+}], and uniform maximum rate adjustment uncertainty u_{max} ⊇ ⋃_{p} u_{p} with u_{max} = u_{max}^{−} + u_{max}^{+} ([SS97a, Assum. 2]), • transmission delay characteristics δ_{sq}, ε_{sq} for all nodes s ≠ q, uniform

bounds 0 ≤ δ_{min} ≤ min_{p,q}{δ_{pq}}, δ_{max} ≥ max_{p,q}{δ_{pq}}, ε_{max} ⊇ ⋃_{p,q} ε_{pq} with ε_{max} = |ε_{max}| = ε_{max}^{−}+ε_{max}^{+} satisfying ε_{max} ⊃ δ_{min}ρ_{max}, “indicator” of broadcast network B ∈ {1, 2}, and accuracy transmission loss G_{A} ([SS97a, Assum. 4]),

• computation delay compensation Γ_{q} (integer multiple of G) guaranteeing node q’s maximum computation time γ_{q} ([SS97a, Assum. 1]), chosen according to

Γ_{q} ≥ \frac{γ_{q} + u_{q}^{−}}{1 − ρ_{q}^{−}} ,

and uniform bounds Γ_{max} ≥ max_{p}{Γ_{p}} and 0 ≤ Γ_{min} ≤ min_{p}{Γ_{p}}; usually Γ_{p} = Γ_{max} = Γ_{min} is the same for all nodes p,

• broadcast delay compensation Λ + Ω (integer multiple of G), chosen to satisfy

Λ + Ω ≥ \frac{λ_{max} + ω_{max} + u_{max}^{−}}{1 − ρ_{max}^{−}};

in conjunction with Δ below, it ensures that resynchronization starts only after all CSMs broadcast by non-faulty nodes during an FME have arrived ([SS97a, Assum. 4]),

• transmission delay compensation Δ (integer multiple of G) chosen according to

Δ ≥ \frac{π_{0} + u_{max} + δ_{max} + (P − Γ_{min} + π^{−})ρ_{max} + ε_{max}^{+}}{1 + ρ_{max}^{+}} , (65)

where π_{0} and π^{−} depend on the particular convergence function employed (provided by the appropriate analysis),

• round period P ≥ Λ + Ω + Δ + Γ_{max} (integer multiple of G),

where all parameters are integer multiples of G_{S} unless otherwise specified. Our generic algorithm is defined as follows:

(0) Initial Synchronization: At each node q, the local interval clock C_{q} has to be initialized to the accuracy interval A_{q}^{0} = [T_{q}^{0} − α_{q}^{0−}, T_{q}^{0} + α_{q}^{0+}] at some synchronous real-time t_{q}^{0} by some external means. This initialization must ensure • t_{q}^{0} ∈ A_{q}^{0},

• T_{q}^{0} ∈ [Λ + Ω + Δ + Γ_{q} ± π],

• α_{q}^{0} ⊆ π_{0},

where π and π_{0} depend on the particular convergence function employed (provided by the appropriate analysis).

(1) Periodic Synchronization: Close to the end of each round k ≥ 0, every node q in the system performs the following operations (the dependency of T^{I}, t_{q}^{I}, etc. upon round k is suppressed for brevity):

\underline{(S) CSM Send}: Periodically at times C_{q}(t_{q}^{I}) = T^{I} = (k + 1)P, node q initiates a broadcast. The message M_{qp} sent to node p at some real-time t_{qp}^{A} during that broadcast operation contains the accuracy interval A_{qp} = [T_{qp}^{A} ± α_{qp}^{A}] = C_{q}(t_{qp}^{A}). For the zero-delay “loop-back transmission” to the own node q, t_{qq}^{A} = t_{q}^{I} so that T_{qq}^{A} = T^{I} = (k + 1)P.

\underline{(R) CSM Reception}: If a clock synchronization message M_{pq} from node p arrives at node q at real-time t_{q}^{p}, when C_{q}(t_{q}^{p}) = T_{q}^{p}, the interval

I_{q}^{p} = \{ \begin{matrix}A_{pq} + [T_{q}^{R} − T_{q}^{p} + δ_{pq} ± 2G_{A} + ε_{pq}] + (T_{q}^{R} − T_{q}^{p})ρ_{q} + u_{q} + \overline{G} \\ A_{qq} + T_{q}^{R} − T_{qq}^{A} + (T_{q}^{R} − T_{qq}^{A})ρ_{q} for p = q \end{matrix}

is computed and stored in a set I_{q}. For the definition of the resynchronization time T_{q}^{R}, see Step (T).

\underline{(C) Computation}: At real-time t_{q}^{Λ+Ω+Δ} defined by

C_{q}(t_{q}^{Λ+Ω+Δ}) = T^{Λ+Ω+Δ} = (k + 1)P + Λ + Ω + Δ,

the convergence function CV is applied to the compatible intervals stored in I_{q}, yielding the interval R_{q}. In addition, I_{q} is re-initialized to the empty set for the next round.

\underline{(T) Termination and Resynchronization}: At real-time t_{q}^{R} defined by

C_{q}(t_{q}^{R}) = T_{q}^{R} = (k + 1)P + Λ + Ω + Δ + Γ_{q},

node q’s interval clock C_{q} is set to R_{q} (instantaneously or by continuous amortization).

Appendix C: Generic Analysis

This appendix provides an extension of the definition of the generic convergence function ([SS97a, Def. 7]) and the major theorem ([SS97a, Thm. 1]), which considerably improve (and hence replace) the original versions. They have been developed in the technical report [SS97b] and are restated here, along with their justification and proofs, for further referencing.

We mentioned already that all results obtained in [SS97a] are generic in the sense that they are expressed in terms of a few characteristic parameters of the convergence function defined in [SS97a, Def. 11], namely,

• accuracy preservation function ℵ(·), giving bounds on the provided interval of accuracies,

• precision preservation function Φ(·), giving the precision of the provided accuracy interval with respect to τ^{k},

• precision enhancement function Π(·), giving the precision of the provided accuracy interval with respect to τ^{k+1}.

In our original Definition [SS97a, Def. 11], we required CV to be both translation invariant and weakly monotonic according to the following definition ([SS97a, Def. 10]).

Definition 10 (Transl. Invariance & Weak Monotonicity) Given two sets I = {I_{1}, …, I_{n}} and J = {J_{1}, …, J_{n}} of n ≥ 1 accuracy intervals, an interval-valued function f() of n ≥ 1 interval arguments is called

(1) weakly monotonic if and only if I_{j} ⊆ J_{j} with ref(I_{j}) = ref(J_{j}) for all 1 ≤ j ≤ n implies f(I) ⊆ f(J),

(2) translation invariant if and only if

f(I_{1} + Δ, …, I_{n} + Δ) = f(I_{1}, …, I_{n}) + Δ

for any real Δ.

However, we recognized that there is no need to require weak monotonicity for CV itself: Monotonicity is used in [SS97a] to justify that bounds on input intervals carry over to bounds on the result. Still, there is no need to establish this property for CV, since it suffices to show that all characteristic functions are monotonic with respect to their interval arguments. The modified definition of the generic convergence function in Definition 11 now accounts for this fact.

More importantly, in the course of analyzing particular convergence functions, we eventually recognized that applying the generic framework in [SS97a] literally provides overly conservative^{8} worst-case accuracy bounds. Intuitively, this is due to the fact that we simply added up the worst-case enlargement of, say, α_{p}^{+} —provided by the convergence function’s accuracy preservation function ℵ^{+}(·)— in every round. The worst-case enlargement of α_{p}^{+}, however, cannot occur successively in consecutive rounds. This is due to the fact that the occurrence of the worst-case setting usually yields an initial precision (that is, after resynchronization) that is better than the worst-case one. This means that the initial precision in the next round is smaller than the worst-case one assumed for the previous round, which in turn prohibits the occurrence of the worst-case enlargement of α_{p}^{+} then.

The key idea used for improving our analysis is to take into account the common intersection of those π-precision intervals associated with the convergence function’s input intervals that eventually determine the worst-case setting for, say, α_{p}^{+}. By feeding its length ι as an additional parameter into the accuracy preservation function ℵ^{+}(·), the worst-case enlargement of α_{p}^{+} can be conditioned on the common intersection actually present. Note that a lower bound was found to be sufficient for this purpose, since excessive adjustments happen for small intersections only.^{9} An additional characteristic function ℑ^{+}(·) respectively ℑ^{−}(·) is introduced for keeping track of how the convergence function affects ι in worst-case scenarios with respect to positive respectively negative accuracy. This (conditional) intersection enhancement function effectively determines ι for the next round, that is, propagates the required information over multiple rounds.

Making this idea working in practice, however, is tricky for several reasons: First of all, it is the particular convergence function that determines how many/which input intervals are involved in the worst case accuracy setting. Leaving CV unspecified in our generic framework thus makes it necessary to supply all the information required for constructing the particular ι from our general expressions. Moreover, different ι^{−} respectively ι^{+} are usually required for computing the worst-case bound for α_{p}^{−} respectively α_{p}^{+}. In fact, it may even be the case that some ι depending upon p is required for determining the worst case accuracy at node p, see [Sch97a] for an example. It is worth noting, however, that something like ι^{p} < ι^{q} implies that the computed worst-case accuracy bounds for nodes p and q cannot both be tight.

8We do not mean the obvious lacking of a good worst-case bound on α_{p} = α_{p}^{−} + α_{p}^{+} here. In fact, since the worst-case scenario for negative and positive accuracy cannot occur simultaneously, simply adding the bounds on α_{p}^{+} and α_{p}^{−} provides an overly conservative bound on α_{p} only.

9At least for any particular convergence function considered up to now.

To cope with those problems, we actually utilize individual lower bounds ι_{s}^{+} and ι_{s}^{−}, 1 ≤ s ≤ n, on the length of the intersection Î_{p}^{s} ∩ Î_{q}^{s} ∩ Î_{p}^{min_{p}} ∩ Î_{q}^{min_{q}} and Î_{p}^{s} ∩Î_{q}^{s} ∩Î_{p}^{max_{p}} ∩Î_{q}^{max_{q}}, respectively, where min_{x} and max_{x} represent that

non-faulty node that leads to the leftmost right(Î_{x}^{min_{x}}) and the rightmost left(Î_{x}^{max_{x}}), respectively, for x ∈ {p, q}. Clearly, ι_{s}^{+} and ι_{s}^{−} are meant for the worst-case accuracy setting for α_{p}^{+} and α_{p}^{−}, respectively, so ∀s : ι_{s}^{+} and ∀s : ι_{s}^{−} are supplied as parameters to ℵ^{+}(·), ℑ^{+}(·) and ℵ^{−}(·), ℑ^{−}(·), respectively, in Definition 11.

In order to be able to inductively compute an expression for, say, ι_{p}^{+}, the conditional intersection enhancement function ℑ^{+}(·) provides an upper bound π_{0}^{ι_{pq}^{+}} on the mutual precision of the CV’s results {R_{p}, R_{q}} computed at node p, q under the worst-case accuracy setting for α_{p}^{+}. Since R_{p} and R_{q} are both π_{0}-correct, this implies that the mutual intersection R̂_{p} ∩ R̂_{q} for any q (including q = min_{x}) has length at least \overline{ι}_{p}^{+} = π_{0} − max_{q} π_{0}^{ι_{pq}^{+}}. Now, since the drift and delay compensation operations applied for computing the input intervals fed into the convergence function are accuracy preserving, it follows that any initial intersection is necessarily preserved during a round. Thus, any intersection of source intervals like Î_{p}^{s}∩Î_{q}^{min_{q}} must also have length at least \overline{ι}_{s}^{+}, which implies that we can simply use ι_{s}^{+} = \overline{ι}_{s}^{+}.

The above considerations lead to the following modified definition of the generic convergence function from [SS97a].

Definition 11 (Generic Converg. Function CV) Let I_{p} = {I_{p}^{1}, …, I_{p}^{n}} respectively I_{q} = {I_{q}^{1}, …, I_{q}^{n}}, q ≠ p, be two ordered sets of n compatible intervals (all representing the \underline{same} real-time t) obtained at nodes p respectively q at the end of a round, which are in accordance with a given fault model F. Assuming that

[1] any non-faulty I_{p}^{i} is π_{p}^{i}-correct for π_{p}^{i} ∈ P_{p} = {π_{p}^{1}, …, π_{p}^{n}} denoting a given set of precision bounds (and analogously for I_{q}^{i} with set of precision bounds P_{q} = {π_{q}^{1}, …, π_{q}^{n}}),

[1’] P = {π^{1}, …, π^{n}} with π_{p}^{i} ∪ π_{q}^{i} ⊆ π^{i} ⊆ π^{H}, for some suitable π^{H}, denotes a set of uniform precision bounds ensuring π^{i}-correctness of both I_{p}^{i} and I_{q}^{i} (if non-faulty),

[2] any pair of non-faulty intervals {I_{p}^{i}, I_{q}^{i}} is π_{I}-precise for some π_{I} ⊆ π^{H},

[3] for any s with both I_{p}^{s} and I_{q}^{s} being non-faulty, the intersection of the

associated precision intervals Î_{p}^{s}∩Î_{q}^{s}∩Î_{p}^{min_{p}} ∩Î_{q}^{min_{q}} respectively Î_{p}^{s}∩Î_{q}^{s}∩ Î_{p}^{max_{p}} ∩ Î_{q}^{max_{q}}, where min_{x} respectively max_{x} represents that non-faulty

node that leads to the leftmost right(Î_{x}^{min_{x}}) respectively the rightmost left(Î_{x}^{max_{x}}) for x ∈ {p, q}, has length at least ι_{s}^{+} ≥ 0 respectively ι_{s}^{−} ≥ 0 (integer multiples of G_{S}),

[4] the accuracies of any non-faulty I_{p}^{i} = [T_{p}^{i} ± α_{p}^{i}] are integer multiples of G_{S} satisfying α_{p}^{i} ⊆ β_{p}^{i} ∈ B_{p} for a given set of accuracy bounds B_{p} = {β_{p}^{1}, …, β_{p}^{n}} (and analogously for I_{q}^{i} with set of accuracy bounds B_{q}); let R_{p} = CV(I_{p}) = [T′_{p} ± α′_{p}], and R_{q} = CV(I_{q}) = [T′_{q} ± α′_{q}].

The generic convergence function CV must be translation invariant and should provide accurate intervals with reference point and accuracies being integer multiples of G_{S}. Its behavior is characterized by the following functions, which must be monotonic with respect to any interval argument:

(1) Precision preservation function Φ(·), so that R_{p} is Φ(P_{p}, π^{H}, π_{I})- correct and R_{q} is Φ(P_{q}, π^{H}, π_{I})-correct, with |Φ(P, π^{H}, π_{I})| = O(π^{H}) for π^{H} = |π^{H}|.

(2) Precision enhancement function Π(·), so that the set {R_{p}, R_{q}} is π_{0}- precise for any π_{0} satisfying |π_{0}| = π_{0} = Π(P, π^{H}, π_{I}), with Π(P, π^{H}, π_{I}) < π^{H} = |π^{H}|.

(3) Conditional intersection enhancement functions ℑ^{−}(·) and ℑ^{+}(·), so that the set {R_{p}, R_{q}} is π_{0}^{ι_{pq}^{−}}-precise respectively π_{0}^{ι_{pq}^{+}}-precise with

π_{0}^{ι_{pq}^{−}} = ℑ^{−}(B_{p}, B_{q}, P_{p}, P_{q}, π^{H}, π_{I}, ∀s : ι_{s}^{−})
π_{0}^{ι_{pq}^{+}} = ℑ^{+}(B_{p}, B_{q}, P_{p}, P_{q}, π^{H}, π_{I}, ∀s : ι_{s}^{+})

for worst-case accuracy settings with respect to α_{p}^{−} respectively α_{p}^{+}.

(4) Conditional accuracy preservation functions ℵ^{−}(·), ℵ^{+}(·), so that

α′_{p} ⊆ [−ℵ^{−}(B_{p}, P_{p}, π^{H}, π_{I}, ∀s : ι_{s}^{−}), ℵ^{+}(B_{p}, P_{p}, π^{H}, π_{I}, ∀s : ι_{s}^{+})].

Note that both the precision enhancement function Π(·) and the intersection enhancement functions ℑ^{−}(·), ℑ^{+}(·) provide a worst-case precision, although for different classes of input scenarios: Whereas Π(·) provides the precision for any input scenario, ℑ^{−}(·) respectively ℑ^{+}(·) is valid for scenarios leading to worst-case α_{p}^{−} respectively α_{p}^{+} according to item (4) only.

Another issue that was left open by the analysis of [SS97a] is the determination of traditional accuracy, which gives the amount local time may drift from real-time during a given time interval Δt. Although worst-case bounds on accuracy intervals obviously provide an upper bound on traditional accuracy as well, this usually leads to overly conservative estimates. Therefore, an explicit expression for traditional accuracy is added to our major theorem. Moreover, taking the limit Δt → ∞, traditional accuracy leads to the rate (and hence drift) of the synchronized clocks, which is more convenient for comparison. Note that appropriate worst-case bounds for are available for most existing internal synchronization algorithms, see, for example [LWL88], [MS85], [Sch87], [ST87], [VR92], [DB93], [FC95b], [VRC97].

Our notion of internal global time makes it easy to deal with traditional accuracy. We only have to bound the maximum “jump” internal global time can experience when switching from one round to the next. This is sufficient since internal global time progresses as real-time does during a round, so that no additional deviation from real-time occurs in between synchronization instants.

The appropriately modified and extended major result of the generic analysis in [SS97a] for the case of instantaneous adjustment^{10} of the local clocks in step (T) of the algorithm in Definition 9 reads as follows.

Theorem 5 (Instantaneous Correction [SS97a, Thm. 1]) Running in a system complying to [SS97a, Assum. 1–4], the clock synchronization algorithm of Definition 9 using the generic convergence function CV characterized by accuracy preservation ℵ^{±}(·), precision preservation Φ(·), precision enhancement Π(·), and intersection enhancement ℑ^{±}(·) subject to a given fault model F, guarantees accuracy and precision for all rounds k ≥ 0 as follows:

10Consult [SS97a] for how to carry over this result to clock adjustment via continuous amortization.

(0) The accuracy interval A_{q}^{k+1} = A_{q}^{k+1}(t_{q}^{R,k}) = [T_{q}^{k+1} ± α_{q}^{k+1}] provided by the local interval clock of a non-faulty node q at the beginning of round k + 1, k ≥ 0, satisfies α_{q}^{k+1} ⊆ β_{q}^{k+1} with

β_{q}^{k+1} =  (66)

= [−ℵ^{−}(B_{q}^{k+1}, P_{q}, π^{H}, π_{I}, ∀s : ι_{s}^{k,−}), ℵ^{+}(B_{q}^{k+1}, P_{q}, π^{H}, π_{I}, ∀s : ι_{s}^{k,+})],

β_{q}^{0} = α_{q}^{0},

where B_{q}^{k+1} = {β_{q}^{1,k+1}, …, β_{q}^{n,k+1}} is defined by β_{q}^{p,k+1} = β_{p}^{k} + ω_{q}^{p} with

ω_{q}^{p} = u_{p} + u_{q} + \overline{G} + 2G_{A} + ε_{pq}
+(P − Δ − Γ_{p})ρ_{p} + (Γ_{q} + Δ − δ_{pq})ρ_{q}
+(Λ + Ω)[− max{ρ_{q}^{−} − ρ_{p}^{−}, 0}, max{ρ_{q}^{+} − ρ_{p}^{+}, 0}]
+O(P ρ_{max} + G + ε_{max})ρ_{max} for p ≠ q,  (67)
ω_{q}^{q} = u_{q} + P ρ_{q} + O(P ρ_{max} + G + ε_{max})ρ_{q},  (68)

the set P_{q} = {π_{q}^{1}, …, π_{q}^{n}} of node q’s precision bounds π_{q}^{p} ⊆ π^{p} ⊆ π^{H} (see item (1)) is defined by

π_{q}^{p} = π_{0} + u_{p} + u_{q} + \overline{G} + ε_{pq} + (P − Δ − Γ_{p})ρ_{p}
+(Γ_{q} + Δ − δ_{pq})ρ_{q}
+(Λ + Ω)[− max{ρ_{q}^{−} − ρ_{p}^{−}, 0}, max{ρ_{q}^{+} − ρ_{p}^{+}, 0}]
+O(P ρ_{max} + G + ε_{max})ρ_{max} for p ≠ q,  (69)
π_{q}^{q} = π_{0} + u_{q} + P ρ_{q} + O(P ρ_{max} + G + ε_{max})ρ_{q},  (70)

and

ι_{q}^{k+1,−} = π_{0} − max_{j} ℑ^{−}(B_{q}^{k+1}, B_{j}^{k+1}, P_{q}, P_{j}, π^{H}, π_{I}, ∀s : ι_{s}^{k,−}) ≥ 0, (71)
ι_{q}^{k+1,+} = π_{0} − max_{j} ℑ^{+}(B_{q}^{k+1}, B_{j}^{k+1}, P_{q}, P_{j}, π^{H}, π_{I}, ∀s : ι_{s}^{k,+}) ≥ 0, (72)
ι_{q}^{0,−} = ι_{q}^{0,+} = π_{0} − max_{j}{α_{j}^{0}} ≥ 0.  (73)

(1) The interval clocks of non-faulty nodes are synchronized to the (observable) initial worst-case precision (that is, the precision at the beginning of each round of the slowest non-faulty clock)

π_{0,max} = π_{0} + u_{max} + G + (Γ_{max} − Γ_{min})ρ_{max}
+O(P ρ_{max}^{2} + Gρ_{max} + ε_{max}ρ_{max})  (74)

with π_{0} = |π_{0}|, where π_{0} is a solution of the equation

|π_{0}| = Π(P, π^{H}, π_{I})  (75)

for the set P = {π^{1}, …, π^{n}} of uniform precision bounds π^{p} ⊆ π^{H} defined by

π^{p} = π_{0} + u_{p} + u_{max} + \overline{G} + ε_{max}
+(P − Δ − Γ_{p})ρ_{p} + (Γ_{max} + Δ − δ_{min})ρ_{max}
+(Λ + Ω)[−(ρ_{max}^{−} − ρ_{p}^{−}), ρ_{max}^{+} − ρ_{p}^{+}]
+O(P ρ_{max} + G + ε_{max})ρ_{max},  (76)
π\overline{q} = π_{0} + u_{q} + P ρ_{q} + O(P ρ_{max} + G + ε_{max})ρ_{q}  (77)
π^{H} = π_{0} + 2u_{max} + \overline{G} + ε_{max} + (P + Γ_{max} − Γ_{min} − δ_{min})ρ_{max}
+O(P ρ_{max} + G + ε_{max})ρ_{max},  (78)
π_{I} = ε_{max} + Bu_{max} + \overline{G} + (Λ + Ω + Δ + Γ_{max} − δ_{min})ρ_{max}
+O(P ρ_{max} + G + ε_{max})ρ_{max},  (79)

where π\overline{q} ⊆ π^{q} denotes node q’s own (that is, non-remote) precision bound.

(2) The (observable) worst-case precision π_{max} satisfies

π_{max} = max{π^{−} + u_{max}^{+} + (Γ_{max} − Γ_{min})ρ_{max}^{+},
π^{+} + u_{max}^{−} + (Γ_{max} − Γ_{min})ρ_{max}^{−}, π_{0} + u_{max} + P ρ_{max}}
+G + O(P ρ_{max}^{2} + Gρ_{max} + ε_{max}ρ_{max})  (80)

with

π = \overline{Φ}(P, π^{H}, π_{I}) + π_{0} + u_{max} + P ρ_{max}
+O(P ρ_{max} + G + ε_{max})ρ_{max},  (81)

where \overline{Φ}(·) denotes the result of Φ(·) with swapped positive and negative accuracy.

(3) Resynchronization of any two non-faulty nodes p, q occurs within realtime t_{p}^{R} − t_{q}^{R} satisfying

t_{p}^{R} − t_{q}^{R} ⊆ Γ_{p} − Γ_{q} + [−π_{0}, π_{0}] + u_{p} + \overline{u}_{q} + P (ρ_{p} + \overline{ρ}_{q})
+O(P ρ_{max} + G + ε_{max})[−ρ_{max}, ρ_{max}],  (82)

where clock adjustments Υ_{q} of at most Υ_{q} ∈ π_{q} ⊆ π defined by

π_{q} = \overline{Φ}(P_{q}, π^{H}, π_{I})+π_{0} +u_{q} +P ρ_{q} +O(P ρ_{max} +G+ε_{max})ρ_{max} (83)

are applied to the clock of a non-faulty node q.

(4) Let Φ = ⋃_{q} Φ(P_{q}, π^{H}, π_{I}) ⊆ Φ(P, π^{H}, π_{I}). For any round k ≥ 0, τ^{k+1}(t) − τ^{k}(t) ∈ \overline{Φ} − \overline{π}_{0}, and the traditional accuracy at the beginning of round k + 1 satisfies

T_{q}^{k+1} − t_{q}^{R,k} ∈ \overline{π}_{0} + (k + 1)(\overline{Φ} − \overline{π}_{0}).  (84)

The inverse rate r_{q,syn}^{−1} of the synchronized clock at any node q evaluates to

r_{q,syn}^{−1} = lim_{k→∞} \frac{t_{q}^{R,k} − t_{q}^{0}}{T_{q}^{k+1} − T_{q}^{0}} ∈ [1 ± \frac{Φ − π_{0}}{P} ],  (85)

where T_{q}^{0} = C_{q}(t_{q}^{0}) is node q’s local time at the beginning of round k = 0.

Proof With the exception of item (0) and item (4), the proof of Theorem 1 in [SS97a] applies without modification. We just replaced π in certain remainder terms like (76) by the coarse bound π = O(P ρ_{max} + G + ε_{max}) established in the proof of [SS97a, Lem. 12], and added (77) according to [SS97a, Eq. (58)], which gives the precision bound π\overline{q} that applies for local (non-remote) intervals I_{q}^{q}.

As far as item (0) is concerned, we found it convenient to introduce the additional abbreviation ω_{q}^{p} in (67)/(68). Moreover, according to the modified Definition 11 of the generic convergence function, we split up ℵ(·) in ℵ^{−}(·) respectively ℵ^{+}(·) and extended the list of parameters to include ∀s : ι_{s}^{k,−} respectively ∀s : ι_{s}^{k,+}. The justification of the appropriate definitions (71)– (73) follows the line of reasoning outlined prior to Definition 11: An upper

bound π_{0}^{ι_{qj}^{+}} on the precision of the set shift_{t′}({A_{q}^{k}, A_{j}^{k}}) (shifting the intervals to some common point in time t′ just makes them compatible) at the begin-

ning of a round k implies a lower bound ι_{qj}^{+} = π_{0} − π_{0}^{ι_{qj}^{+}} on the length of the mutual intersection of the associated π_{0}-precision intervals Â_{q}^{k} ∩ Â_{j}^{k}. Taking

the minimum over all j gives a lower bound ι_{q}^{+} = π_{0} − max_{j} π_{0}^{ι_{qj}^{+}} on that mutual intersection for arbitrary nodes j, including j = min_{x}. The required

π_{0}^{ι_{qj}^{+}}, however, is given by the conditional intersection enhancement function ℑ^{+}(·) for rounds k > 0, and by the initial synchronization assumption in Definition 9 for round k = 0.

It only remains to confirm that the precision intervals associated with any (non-faulty) I_{p}^{s} and I_{q}^{s} —fed into the convergence function at node p and q— have a mutual intersection with either I_{p}^{min_{p}} and I_{q}^{min_{q}} of length at least ι_{s}^{+} as well. However, the drift and delay compensation operations used to obtain round k’s I_{x}^{s} from A_{s}^{k} have been explicitly designed to preserve accurateness, so they must preserve any initial mutual intersection. Hence, choosing ι_{q}^{k+1,+} and ι_{q}^{k+1,−} according to (71)–(73) is legitimate.

Turning our attention to item (4), we know that A_{q}^{k+1} is Φ(P_{q}, π^{H}, π_{I})- correct with respect to τ^{k} by virtue of item (2) of Definition 11 and hence Φ-correct. Note that Φ ⊆ Φ(P, π^{H}, π_{I}) is a simple consequence of monotonicity of Φ(·). Moreover, from item (3) of Definition 11, it follows that all A_{p}^{k+1} are π_{0}-precise. Hence it is possible to choose τ^{k+1} ∈ ⋂_{p} Â_{p}^{k+1}, as justified by Definition 2, and we claim that we may in fact choose τ^{k+1} so that

−(Φ^{+} − π_{0}^{+}) ≤ τ^{k+1} − τ^{k} ≤ Φ^{−} − π_{0}^{−}.

If this was not feasible, there would exist an interval Â_{r}^{k+1} of length π_{0} with τ^{k+1} = left(Â_{r}^{k+1}) or else τ^{k+1} = right(Â_{r}^{k+1}) that satisfies τ^{k} ∉ Â_{r}^{k+1} + (Φ − π_{0}) = Φ. This, however, would contradict Φ-correctness of A_{r}^{k+1}.

The bound (84) 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 τ^{0}(t) = t is legitimate due to the initial synchronization assumption in Definition 9. Hence, to complete the proof of (84), it only remains to add the maximum deviation between τ^{k+1} and the reference point T_{q}^{k+1} of A_{q}^{k+1}, which is trivial since the latter is π_{0}-correct.

To derive expression (85) for the rate of the synchronized clocks, we multiply (84) by -1 to arrive at

t_{q}^{R,k} − t_{q}^{0} ∈ T_{q}^{k+1} − T_{q}^{0} − (t_{q}^{0} − T_{q}^{0}) + π_{0} + (k + 1)(Φ − π_{0}).  (86)

¿From the initial synchronization assumptions in item (0) of Definition 9, we gather t_{q}^{0} − T_{q}^{0} ∈ α_{q}^{0} ⊆ π_{0}. Moreover, from step (T) of the algorithm in conjunction with the fact that the maximum clock adjustment was shown to satisfy Υ_{q} ∈ π in item (3) of this theorem, we obtain T_{q}^{k+1} − T_{q}^{0} = (k + 1)P + O(π). Plugging this into (86), we find

\frac{t_{q}^{R,k} − t_{q}^{0}}{T_{q}^{k+1} − T_{q}^{0}} ∈ 1 + \frac{[−π_{0}, π_{0}] + (k + 1)(Φ − π_{0})}{(k + 1)P + O(π)}.

Taking the limit for k → ∞ eventually provides (85) and completes the proof of our theorem. □

[figure: Basics (Sec. 2); Def. 1 (p. 9): Interval relations; Def. 2 (p. 9): Precision intervals; Def. 3 (p. 10): π-correctness; Lem. 1 (p. 10): π-prec. vs. prec.; Fault Model (Sec. 2.3); Def. 4 (p. 14): Single faults; Def. 5 (p. 15): Pairwise faults; Asum. 1 (p. 17): Hybrid fault model; Marzullo’s Function (Sec. 3); Def. 6 (p. 18): Marzullo function; Lem. 2 (p. 20): Accuracy M; Lem. 3 (p. 22): Monotonicity M; Lem. 4 (p. 24): Precision M; Lem. 5 (p. 28): Graceful degrad.; OA Conv. Function (Sec. 4, App. C); Def. 7 (p. 35): π-center; Def. 8 (p. 35): Conv. function OA; Lem. 6 (p. 55): Properties π-center; Lem. 7 (p. 56): Precision enhancement; Thm. 1 (p. 36): Precision properties OA; Thm. 2 (p. 39): Accuracy properties OA; Generic Conv. Function (App. C); Def. 11 (p. 63): Generic CV; Generic Alg. & Analysis (App. B & C); Def. 9 (p. 58): Generic algorithm; Thm. 5 (p. 65): Instant. correct.; OA Algorithm & Analysis (Sec. 5); Thm. 3 (p. 45): Precision OA; Thm. 4 (p. 49): Accuracy OA; System Model ([SS97a], App. B); [SS97a, Assum. 1]: Exec. times; [SS97a, Assum. 2]: Local clocks; [SS97a, Assum. 3]: Interval clocks; [SS97a, Assum. 4]: Transm. char.; Generic Analysis ([SS97a]); Orthogonal Accuracy Analysis; Overview of the Analysis]

71

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.

Acknowledgment of support

This research is part of our project SynUTC (http://www.auto.tuwien.ac.at/ Projects/SynUTC/ ), which has been supported by the Austrian Science Foundation (FWF) under grant no. P10244-ÖMA and the Austrian START programme Y41-MAT.

References

[AK96] M. H. Azadmanesh and R. M. Kieckhafer. New hybrid fault models for asynchronous approximate agreement. IEEE Transactions on Computers, 45(4):439–449, 1996.

[BI96] R. R. Brooks and S. S. Iyengar. Robust distributed computing and sensing algorithms. IEEE Computer, pages 53–60, June 1996.

[Dan97] P. H. Dana. Global Positioning System (GPS) time dissemination for real-time applications. Real-Time Systems, 12(1):9–40, January 1997.

[DB93] R. Drummond and Ö. Babaoğlu. Low-cost clock synchronization. Distributed Computing, 6:193–203, 1993.

[DHS86] D. Dolev, J. Y. Halpern, and H. R. Strong. On the possibility and impossibility of achieving clock synchronization. Journal of Computer and System Sciences, 32:230–250, 1986.

[FC95a] C. Fetzer and F. Cristian. Lower bounds for function based clock synchronization. In Proceedings 14th ACM Symposium on Principles of Distributed Computing, Ottawa, CA, August 1995.

[FC95b] C. Fetzer and F. Cristian. An optimal internal clock synchronization algorithm. In Proceedings 10th Annual IEEE Conference on Computer Assurance, Gaithersburg, MD, June 1995.

[HS97] D. Höchtl and U. Schmid. Long-term evaluation of GPS timing receiver failures. In Proceedings of the 29th IEEE Precise Time and Time Interval Systems and Application Meeting (PTTI’97), pages 165–180, Long Beach, California, December 1997.

[Knu73] D. E. Knuth. Fundamental Algorithms, volume 1 of The Art of Computer Programming. Addison-Wesley, Reading, Massachusetts, 2nd edition, 1973.

[Lam87] L. Lamport. Synchronizing time servers. Technical Report 18, Digital System Research Center, 1987.

[Lis93] B. Liskov. Practical uses of synchronized clocks in distributed systems. Distributed Computing, 6:211–219, 1993.

[LWL88] J. Lundelius-Welch and N. A. Lynch. A new fault-tolerant algorithm for clock synchronization. Information and Computation, 77(1):1–36, 1988.

[Mar84] K. A. Marzullo. Maintaining the Time in a Distributed System: An Example of a Loosely-Coupled Distributed Service. Ph.D. dissertation, Stanford University, Department of Electrical Engineering, February 1984.

[Mar90] K. A. Marzullo. Tolerating failures of continuous-valued sensors. ACM Transactions on Computer Systems, 8(4):284–304, 1990.

[Mil95] D. L. Mills. Improved algorithms for synchronizing computer network clocks. IEEE Transactions on Networks, pages 245–254, June 1995.

[MS85] S. R. Mahaney and F. B. Schneider. Inexact agreement: Accuracy, precision, and graceful degradation. In Proceedings 4th ACM Symposium on Principles of Distributed Computing, pages 237–249, Minaki, Canada, August 1985.

[OSF92] OSF. Introduction to OSF DCE. Prentice Hall, Englewood Cliffs, NJ, 1992.

[Sch86] F. B. Schneider. A paradigm for reliable clock synchronization. In Proceedings Advanced Seminar of Local Area Networks, pages 85–104, Bandol, France, April 1986.

[Sch87] F. B. Schneider. Understanding protocols for byzantine clock synchronization. Technical Report 87-859, Cornell University, Department of Computer Science, August 1987.

[Sch95] U. Schmid. Synchronized Universal Time Coordinated for distributed real-time systems. Control Engineering Practice, 3(6):877–884, 1995. (Reprint from Proceedings 19th IFAC/IFIP Workshop on Real-Time Programming (WRTP’94), Lake Reichenau/Germany, 1994, pages 101–107.).

[Sch97a] U. Schmid. Interval-based clock synchronization with optimal precision. Technical Report 183/1-78, Vienna University of Technology, Department of Automation, July 1997. (submitted to Information and Computation).

[Sch97b] U. Schmid, editor. Special Issue on The Challenge of Global Time in Large-Scale Distributed Real-Time Systems, J. Real-Time Systems 12(1–3), 1997.

[Sch97c] K. Schossmaier. An interval-based framework for clock rate synchronization algorithms. In Proceedings 16th ACM Symposium on Principles of Distributed Computing, pages 169–178, St. Barbara, USA, August 21–24, 1997.

[SKM^{+}00] U. Schmid, J. Klasek, T. Mandl, H. Nachtnebel, G. R. Cadek, and N. Kerö. A Network Time Interface M-Module for distributing GPS-time over LANs. J. Real-Time Systems, 18(1):24–57, January 2000.

[SS97a] U. Schmid and K. Schossmaier. Interval-based clock synchronization. J. Real-Time Systems, 12(2):173–228, March 1997.

[SS97b] U. Schmid and K. Schossmaier. Interval-based clock synchronization revisited. Technical Report 183/1-80, Vienna University of Technology, Department of Automation, July 1997.

[ST87] T. K. Srikanth and S. Toueg. Optimal clock synchronization. Journal of the ACM, 34(3):626–645, July 1987.

[VR92] P. Veríssimo and L. Rodrigues. A posteriori agreement for faulttolerant clock synchronization on broadcast networks. In Proceedings 22nd International Symosium on Fault-Tolerant Computing, Boston, Massachusetts, July 1992.

[VRC97] P. Veríssimo, L. Rodrigues, and A. Casimiro. CesiumSpray: a precise and accurate global clock service for large-scale systems. J. Real-Time Systems, 12(3):243–294, 1997.

[WS00] C. J. Walter and N. Suri. The customizable fault/error model for dependable distributed systems. Theoretical Computer Science, 2000. (Special issue on Dependable Computing, to appear).

[YM93] Z. Yang and T. A. Marsland. Annotated bibliography on global states and times in distributed systems. ACM SIGOPS Operating Systems Review, pages 55–72, June 1993.

Glossary

Name  Meaning  Page
ℵ^{+}(·), ℵ^{−}(·)  accuracy preservation function  63
α = [−α^{−}, α^{+}]  interval of accuracies of I = [r ± α]  8
α = α^{−} + α^{+}  length of α  8
α_{p}^{0} = [−α_{p}^{0−}, α_{p}^{0+}]  initial accuracies at node p  58
C(t), C_{p}(t)  ordinary clock (node p)  3
C_{p}(t) = [C_{p}(t)±α_{p}(t)] local interval clock of node p  3

δ_{max}, δ_{min} uniform bounds on transmission delay characteristics

58

Δ  transmission delay compensation  58
ε_{max}  maximum transmission delay uncertainty  58

f_{a} number of asymmetric respectively arbitrary faults

17

f_{c}  number of crash faults  24

f_{s} number of symmetric respectively simple faults

17

f_{u}  number of unbounded accuracy faults  20
G  clock granularity  58
G_{S}  clock setting granularity  58

Γ_{max}, Γ_{min} uniform bounds on computational delay characteristics

58

ℑ_{−}(·), ℑ_{+}(·)  intersection enhancement function  63
I, A  (accuracy) intervals  9
\overline{I}  swapped interval [r ∓ α]  9
Î  π-precision interval associated with I  9
I_{p}  ordered set received intervals at p  58
Λ_{max}  logical time maximum broadcast latency  58
M  Marzullo’s function  18
max_{i:m}{s_{i}}  m-th largest element among {s_{i}}  39
n  number of nodes  4
ω_{max}  logical time maximum broadcast oper. delay  58
OA  orthogonal accuracy convergence function  35
P  round period  58
Φ(·)  precision preservation function  63
π = [−π^{−}, π^{+}]  (generic) interval of precision  9
π = π^{−} + π^{+}  length of π  9
π_{0} = [−π_{0}^{−}, π_{0}^{+}]  ideal initial precision  65
π^{H} = [−π^{H−}, π^{H+}]  uniform precision exchanged intervals  65

π_{I}  uniform precision of perceptions  65
π-accurate  correct with respect to t and π-precise  9
π-center  asymmetric reference point setting  35
π-correct  correct with respect to both t and τ  10
π-precise  precise interval set  9
Π(·)  precision enhancement function  63
ref(I)  reference point of interval I  8
τ, τ^{k}  internal global time (of round k)  10