Internal vs. External Time
Internal vs. External Time
Abstract.
We propose a fault-tolerant algorithm for synchronizing both state
and rate of clocks in a distributed system. This algorithm is based
on rounds, uses our fault-tolerant Optimal Precision (OP) convergence function
as the means of synchronization, and maintains a collection of intervals
to keep track of real-time, internal global time, and clock rates. The
analysis shows that the interlocking between state and rate synchronization
can be easily solved, and that oscillator stabilities together with the
transmission delay uncertainties of packets predominate the internal
synchronization. In addition, average case results gathered from simulation
experiments with our SimUTC toolkit prove to be about one order of magnitude
better than the worst case ones from the analysis of our state&rate algorithm.
Abstract.
Local time can be observed at nodes in a distributed system by using their
clocks, whose state and rate are required to be in sync with each other
(internal clock synchronization) and related to real-time (external clock
synchronization) as well. The synchrony is accomplished by running distributed
algorithms, which have to cope with uncertainties arising from varying
packet transmission delays, clock drifts, non-zero granularities, and above
all a whole range of system faults.
Our research within the scope of project SynUTC is driven by the challenging
goal to achieve a worst case synchronization tightness in the 1 µs-range
with commercial-off-the-shelf technology. This means that apart from
advanced algorithmic matters some hardware support for exact timestamping
of packets containing time information is required here, in conjuction with
a high-resolution clock device with fine-grained state and rate adjustment
capabilities. Additionally, an interface for GPS receivers is needed to
obtain external time information. All those features are provided by an
M-Module (called NTI) built around a custom VLSI chip (called UTCSU),
which are also touched here.
Unlike traditional approaches, we employ a well-founded interval
paradigm to represent both system parameters and algorithmic quantities.
This entails the advantage of a uniform view of almost all aspects of
clock synchronization, which in turn allows to gain precious insights how
such algorithms work. In particular, we establish accuracy/precision
resp.~rate/consonance intervals along with suitable operations to capture the
state resp.~rate of clocks in the distributed system. Moreover, we introduce
the notion of internal global time/rate as a vehicle for the worst case
analysis of our algorithms. Of particular interest are interval-based
convergence functions that are in charge of computing proper clocks
adjustments despite faulty input intervals from remote nodes.
To highlight the major results, our clock state algorithm OP-STATE exhibits
optimality in terms of worst case precision and maximum clock adjustment,
and maintains slightly suboptimal on-line accuracy bounds. Moreover, our
thorough analysis reveals that clock granularities and discrete rate
adjustment techniques have a considerable impact upon the achievable
degree of synchronization. As a novelty, our clock rate algorithm
OP-RATE demonstrates that the oscillator stability is essentially
responsible for the achievable mutual clock drift, which may be
significantly smaller than the commonly specified maximum drift.
Abstract.
This paper addresses the problem of synchronizing the rate of clocks
in a fault-tolerant distributed system. Contrived to bring the rate
(i.e.~speed) of all correct clocks in accordance, rate synchronization
algorithms are very similar to usual state synchronization ones. Major
differences, however, arise from the fact that the quantities to
be synchronized are not directly accessible and that they do not proceed
linearly with time. Relying on an interval-based paradigm, we introduce
a basic system model and suitable building blocks for a generic convergence
function-based rate synchronization algorithm. Our rigorous analysis
of the achievable consonance (i.e.~mutual rate deviation) and drift
(i.e.~deviation towards the ideal rate of 1 Sec/sec) reveals that it is
the clocks' stability that takes over the role of maximum clock drift in
traditional clock synchronization approaches.
Abstract.
In this paper, we develop and analyze a simple interval-based
algorithm suitable for fault-tolerant external clock synchronization.
Unlike usual internal synchronization approaches, our convergence
function-based algorithm provides approximately synchronized clocks
maintaining both precision and accuracy w.r.t. external time. This
is accomplished by means of a time representation relying on
intervals that capture external time, providing accuracy information
encoded in interval lengths. The algorithm, which is generic w.r.t.
the convergence function and relies on either instantaneous
correction or continuous amortization for clock adjustment, is
analyzed by utilizing a novel, interval-based framework for
establishing worst-case precision and accuracy bounds subject to a
fairly detailed system model. Apart from individual clock rate and
transmission delay bounds, our system model incorporates non-standard
features like clock granularity and broadcast latencies as well.
Relying on a suitable notion of internal global time, our analysis
unifies treatment of precision and accuracy, ending up in striking
conceptual beauty and expressive power.
Abstract.
In this paper we promote rate synchronization for clocks in fault-tolerant
distributed systems and develop the underpinnings for a clock rate algorithm.
Two parameters are used for characterization, namely drift for external and
consonance for internal clock rate synchronization. A clock rate algorithm
is similar to a conventional clock state algorithm, but instead of depending
on their maximum oscillator drifts, their stability is exploited. We present a
comprehensive system model, work out the concepts for clock rate
synchronization and give a general analysis by using a suitable
interval paradigm.
Abstract.
We present a novel technique for establishing a highly
accurate global time in fault-tolerant, large-scale distributed real-time
systems. Unlike the usual clock synchronization approaches, our clock
validation technique provides a precise system time that also relates to
an external time standard like UTC with high accuracy. The underlying idea
is to validate time information of external time sources like GPS-receivers
against a global time maintained by the local clocks in the system.
As an example, a promising interval-based clock validation algorithm
ICV that exhibits excellent fault-tolerance properties is outlined and
analyzed. It requires only a few high-accurate external time sources
and provides each node with the actual accuracy of its clock.
