Date: Wed, 15 Jan 1997 01:30:11 GMT
Server: NCSA/1.4.2
Content-type: text/html
Last-modified: Wed, 24 Jul 1996 23:39:29 GMT
Content-length: 2954
Fail-Aware Clock Synchronization
Abstract
Internal clock synchronization requires that at any
point in time the deviation between any two correct
clocks is bounded by an a priori given constant.
Due to network partitions, unbounded message transmission
and process scheduling delays, internal clock synchronization
is impossible to implement in asynchronous systems.
We address this problem by proposing a new kind of
clock synchronization that is implementable in asynchronous
systems with local hardware clocks:
fail-aware clock synchronization.
The specification of that new service is derived
using the general concept of
fail-awareness: this concept allows to
transform the specification of a synchronous service
into a fail-aware service such that it becomes
implementable in asynchronous systems.
To illustrate the usage of fail-aware clock synchronization,
we show how it can be used to solve the highly-available,
fail-aware leader election problem.
The specification of fail-aware clock synchronization requires that
- each time server maintains a synchronization indicator,
- for any time t and any two time servers p and q,
if the two synchronization indicators of p and q are
true at t, then the deviation between p's and q's
clock at time t is bounded by an a priori
given constant, and
- a time server which can communicate with a majority of
time servers in a timely manner and which is timely (i.e. it
does not suffer performance failures), has to set its synchronization
indicator to true.
We show how fail-aware clock synchronization can efficiently
be implemented in timed asynchronous systems.
These systems are characterized by
- a precise notion of what it means that
a process or message to be timely,
- unbounded message transmission and process scheduling delays, and
- each process has access to a local hardware clock with a
drift rate within some given bounds.
The proposed protocol to implement fail-aware clock synchronization
is based on the protocols described in
CS94-367 .
Each process p synchronizes its clock in a round based fashion.
Only when p succeeds to read the
synchronized clocks (i.e. their synchronization indicators are true)
of a majority of processes within some given reading error at the end of
a round, p can keep its synchronization indicator
true for the next round. Otherwise, p's
synchronization indicator is (automatically) switched to false.
Home