Self-stabilizing clock synchronization in the presence of Byzantine faults.
We initiate a study of bounded clock synchronization under a more severe fault model than that proposed by Lamport and Melliar-Smith [1985]. Realistic aspects of the problem of synchronizing clocks in the presence of faults are considered. One aspect is that clock synchronization is an on-going task, thus the assumption that some of the processors never fail is too optimistic. To cope with this reality, we suggest self-stabilizing protocols that stabilize in any (long enough) period in which less than a third of the processors are faulty. Another aspect is that the clock value of each processor is bounded. A single transient fault may cause the clock to reach the upper bound. Therefore, we suggest a bounded clock that wraps around when appropriate.We present two randomized self-stabilizing protocols for synchronizing bounded clocks in the presence of Byzantine processor failures. The first protocol assumes that processors have a common pulse, while the second protocol does not. A new type of distributed counter based on the Chinese remainder theorem is used as part of the first protocol.
Introduction
In a distributed system, it is often necessary to keep the logical clocks of the processors synchronized.
In such a system physical clocks may drift and messages could have varying delivery times. Moreover,
processors may be faulty, and in many cases the type of failures is not predictable in advance. To handle
this situation, the worst type of failures must be considered, namely Byzantine faults [LSP-82]. In the
presence of Byzantine faults a processor can exhibit arbitrary "malicious", "two faced", behavior.
The problem of keeping clocks synchronized in the presence of Byzantine faults has been extensively
studied (e.g., [HS+-84, LM-85, MS-85, DHS-86, ST-87, WL-88, RSB-90]). Lamport and Melliar-Smith
[LM-85] were the first to present the problem and show that 3f processors are sufficient to tolerate
f Byzantine faults. The necessity of 3f processors to tolerate f faults was later proved in [DHS-86].
A weaker fault model called authenticated Byzantine allows a protocol that can tolerate any number of
faulty processors [HS+-84]. In that failure model reintegration of repaired processors is only possible if
less than half the processors are faulty. Many of the protocols for this problem assume that the clocks are
initially synchronized and thus focus on keeping them synchronized in the presence of clock drift.
The problem of how to ensure that the clocks are initially synchronized was addressed in, e.g., [ST-87,
WL-88]. In these protocols, some mechanism is assumed that allows all the nonfaulty processors to begin
the protocol within a bounded time period of each other. The mechanism essentially is that the processes
Supported in part by TAMU Engineering Excellence funds and NSF Presidential Young Investigator Award CCR-9158478.
y Department of Mathematics and Computer Science, Ben-Gurion University, Beer-Sheva, 84105, Israel. e-mail:
shlomi@cs.bgu.ac.il.
z Department of Computer Science, Texas A&M University, College Station,
are assumed to wake up in a distinguished initial state, in which they can uniquely perform initializing
actions, including communication with each other.
In this work we weaken the assumptions made for the design of clock synchronization protocols in the
presence of Byzantine faults. Our goal is protocols that cope with a more severe (and realistic) fault model
than the traditional Byzantine fault model [LSP-82]. Initially, protocols that tolerate Byzantine faults were
designed for flight devices that need to be extremely robust. In such a device the traditional assumptions
could be violated: Is it reasonable to assume that during any period of the execution less than one third
of the processors are faulty? What happens if for a short period more than a third are faulty (perhaps
experience a weaker fault than a Byzantine fault)? What happens if messages sent by nonfaulty processors
are lost in one instant of time?
In this paper we present self-stabilizing protocols that can overcome these problems. Such temporary
violations of the assumptions can be viewed as leaving the system in an arbitrary initial state from which
the protocol resumes. Self-stabilizing protocols work correctly when started in any initial system state.
Thus, even if the system loses its consistency due to an unexpected temporary violation of the assumptions
made (e.g., more than one-third faulty, unexpected message loss) the system synchronizes the clocks when
subsequently the assumptions hold (e.g., less than a third experience Byzantine faults).
Originally, Dijkstra defined (in [Dij-74]) a protocol to be self-stabilizing if, when started in an arbitrary
system state, the system converges to a consistent global state that realizes the task. Self-stabilizing
protocols are resilient to transient faults - faults that cause the state of a processor to change arbitrarily
and then from the new state, the processor resumes operation according to its program. A permanent
fault is a fault that causes a processor to permanently misbehave. A protocol tolerates hybrid faults if
it is resilient to both transient and permanent faults (e.g., [DW-93, GP-93] which consider napping and
omission faults, respectively). We are interested in clock synchronization protocols that can tolerate hybrid
faults: they should work from an arbitrary initial configuration and they should tolerate less than a third
of the processors exhibiting permanent Byzantine faults.
A realistic assumption for a clock synchronization protocol is that a 64-bit clock is "unbounded" for
most possible applications. However, in the context of self-stabilizing protocols transient faults could cause
the system to reach the upper bound of the clock at once. Thus, another aspect of the problem should be
considered: the fact that the clocks are bounded.
In this paper we present two randomized self-stabilizing clock synchronization protocols that work in
the presence of Byzantine faults. Both protocols work for bounded clocks. The first assumes the existence
of a common pulse while the second does not make this assumption. The expected stabilization time of
both protocols is exponential in n. This is a drawback when the number of processors is large. However,
in addition to being of theoretical interest, we believe that our protocols could be of practical interest, at
least when the number of backup processors is small.
One of the contributions of this paper is an interesting usage of the Chinese remainder theorem for
implementing a distributed counter. This counter is used to accelerate the first protocol.
The remainder of the paper is organized as follows. In the next section we formalize the assumptions and
requirements for the protocol. Section 3 presents a clock synchronization protocol under the assumption of
a common pulse. In Section 4 we present a protocol that does not assume the existence of common pulses.
Conclusions are in Section 5.
A distributed system consists of a set of processors that communicate by sending messages to each other.
Messages have a bounded delay. Each processor has a bounded physical clock that is constantly incre-
mented, wrapping around when appropriate; the physical clocks at the different processors run at approximately
the same rates. Each processor also has a bounded logical clock, which is computed as a function
of the current state and physical clock value. The goal is for the logical clocks of the nonfaulty processors
to become and subsequently remain close to each other, while continuing to progress at a reasonable rate
(wrapping around when appropriate). We consider two types of timing behavior of the system, synchronous
and semi-synchronous. In both models, processors take steps either when they receive a message, or when
their physical clocks reach some predetermined value. In addition, in the synchronous model, there is a
common pulse that periodically occurs simultaneously at all processors, causing them to take a step. We
now proceed more formally.
Each processor P i
modeled as a state machine. Associated with the processor is its
physical clock, which takes on integral values from 0 to M pc \Gamma 1 for some M pc . The state contains a
distinguished timer variable that can take on the values 0 to M pc \Gamma 1 and nil; it indicates that the processor
wants to take a step the next time its physical clock has the given value. A transition takes the current
state of the processor, the current value of its physical clock, and a message received (if any) and produces
a new state of the processor and a set of messages to be sent. The message system holds all messages sent
but not yet received. A configuration of the system is a set of processor states, one per processor, a set of
physical clock values, one per processor, and a state for the message system.
An execution is an alternating sequence of configurations and events C 0
\Delta. In a semi-synchronous
execution, events happen at real times, taking one configuration to the next. There are
two types of events. One type is a tick of some processor's physical clock, causing it to increase by 1 mod
. Nothing else changes. We require that the real time elapsed between two successive ticks of the same
processor be between fixed ae.
The other type of event is a step of some processor. No processor can take more than one step at
the same real time. In the step, the processor may or may not receive a message. The real time elapsed
between the sending and receiving of any message must be in the range [d \Gamma ffl; d + ffl] for some fixed d
and ffl. There is a fixed set of faulty processors of size f , where n ? 3f . If the processor taking the step
is nonfaulty, then the succeeding configuration must correctly reflect the processor's transition function
acting on the message received and the state and physical clock in the preceding configuration. Thus the
only changes are to the processor's state and the message system (removing the message received and
adding the messages sent). If the processor taking the step is faulty, it can change state arbitrarily and
add arbitrary messages (from itself) to the message system.
In a synchronous execution, in addition to the above constraints, there exists a value - ? 0 such that,
for all i, every processor P i receives a special Pulse message (from a dummy processor) at time i \Delta -. (I.e.,
all the processors take a step at each pulse and the pulses occur regularly with period -.)
We require that for every processor P i there exist a function clock i that, given a state of P i and a value
for P i 's physical clock, returns a value in the range 0 to M lc \Gamma 1 for some fixed M lc . This is the logical
clock of P i . Given a particular execution C 0
we denote by clock i (t) the value of the function clock i
applied to P i 's state and physical clock value in C j , where j is the configuration in the execution whose
real time of occurrence is the largest not exceeding t. We require that there exist a finite time t s for which
the following two conditions hold:
Clock Agreement: There exists =4 such that for all t - t s and all nonfaulty processors P i and
Clock Validity: There exists \Delta, =4, and there exists a - 0 such that for all real times t ? t s
and all i, if clock i
1 The constant 4 is chosen for convenience; any constant larger than 2 is sufficient. Note that if the constant is 2 then this
condition holds for any arbitrary configuration, since every two clock values are at most M lc =2 apart.
Clock Agreement states that after t s
, the difference between any two nonfaulty processors' clocks is at
most fl. Clock Validity states that after t s , the amount of logical clock time that elapses during \Delta real
time is a linear function of \Delta.
3 Synchronous Protocol
We first describe a protocol for the synchronous system, in which nonfaulty processors have access to a
periodic common pulse. Each pulse triggers the processors to synchronize their clocks. The time between
two successive pulses appears to be an important parameter to the problem. In case two successive pulses
are farther apart than the time required to run a Byzantine agreement protocol, then the following scheme
solves the problem: Every pulse starts a new version of the Byzantine agreement to agree on the common
clock value. However, when the pulses are only on the order of the round trip message delay apart, this
scheme cannot work.
We assume that the pulses are on the order of the round trip delay apart. Recall that - is the time
between two successive pulses. Nonfaulty processors send messages and update their logical clocks only
when a pulse occurs. We assume that - is long enough such that when a pulse takes place, no message sent
by a nonfaulty processor in the previous pulse is present in the system. Whenever a nonfaulty processor
P is triggered by a pulse, P sends a message with its clock value to all its neighbors. Then P waits to
receive all the clock values of the other processors. P waits for a period (1 ffl) that is longer than
the bound on the message delay and accounts for clock drift. If during that period P receives more than
one message from some neighbor, say Q, then P uses the latest value that arrives from Q. Thus, at the
end of such a period P has a set of at least n \Gamma f logical clock values, at most one value for each nonfaulty
processor including P . P uses the set of the logical clocks received in order to choose its own clock value.
The formal description of the protocol appears in Figure 1. We now describe the protocol informally.
The protocol for a processor P works as follows: (1) if the value of P 's clock appears less than
in the set of the received logical clocks then P assigns 0 to its clock. Otherwise, (2) in case that the value
of P 's clock appears at least n \Gamma f times, we further distinguish between the case (2.1) in which P 's clock
value is not equal to 0 and the case (2.2) in which it is equal to 0. In case (2.1) P increments its clock
by 1 (modulo the number of clock values M lc ). Case (2.2) is further subdivided into two cases: (2.2.1) in
which (according to the state of P ) in the previous pulse P incremented its clock by 1 (and the result was
and the case (2.2.2), otherwise. In case (2.2.1) P increments its clock by 1 (to be 1). In case (2.2.2) P
tosses a coin and assigns the result (0 or 1) to its clock.
The protocol guarantees (with probability 1) that the system eventually reaches a global state in which
all the nonfaulty processors have the clock value 1. Once such a global state is reached the clocks are
synchronized: In every pulse, every nonfaulty processor P receives messages from at least
processors containing a clock value that is identical to its own clock value. Moreover, a pulse in which
all the nonfaulty processors set their clocks to 0 always follows a pulse in which every nonfaulty processor
increments its clock value by 1 to set it to 0. Thus, case (2.2.2) is not applied.
The main idea of the protocol is to ensure that only when there are "enough" nonfaulty processors with
the same clock value will this value be incremented. It is proved in the sequel that in any pulse at most
one clock value of nonfaulty processors is incremented by 1 while the rest of the values are changed to be
zero. This ensures that after the first pulse, the set of clock values of the nonfaulty processors contains at
most two elements. Moreover, if two such elements indeed exist one of them is 0.
At first glance this seems to be sufficient and no coin toss is needed; the value that is incremented will
eventually wrap around to 0 and at that time the clocks of all the nonfaulty processors will be 0. However,
we now describe an infinite execution, E, that does not use coin tosses in which the clocks never become
synchronized. Consider a system with four processors
and P 4
in which P 4
exhibits Byzantine
behavior. Let 0; 0; 1 be the clock values of P 1
, respectively, in the first configuration of E. In the
first pulse P 4
sends clock value 1 to P 1
and P 3
and clock value 0 to P 2
. Thus, P 1
receives the clock values
vector 0; 0;
receives 0; 0;
is the only processor that finds processors
with the same clock value (namely, the clock value 0) and increments its clock value by one (to be 1). At
the same time, P 1
and P 3
find two clock values with value 1 and two with value 0 and assign 0 to their
clocks. Hence, a configuration with clock values 0; respectively, is obtained. P 4 continue
and sends the clock values
receives the clock values vector 0;
receives 0;
receives 0; 1; 0; 0. Similarly, P 3
is the only processor that finds processors
with the same clock value and assigns 1 to its clock while P 1
and
assign 0. We reach a configuration
with clock values 0; 0; 1 for
which are identical to the clock values in the first configuration.
Therefore, an infinite execution in which nonfaulty processors never agree on their clock values is possible.
To overcome the above problem we use coin tosses. In a pulse in which a nonfaulty processor with clock
value clock values with value 0 the processor tosses a coin and decides whether to assign
or 1 to its clock. This leads to a possible scenario (that has some probability of occurring) in which the
coin toss results cause all the nonfaulty processors to simultaneously assign 1 to their clocks.
when pulse occurs:
broadcast clock i
collect clock values until (1 has elapsed on the physical clock
(*case (1)*)
last increment i
06 else (*case (2)*)
07 if clock i 6= 0 then (*case (2.1)*)
last increment i := trueg
else (*case (2.2)*)
last increment
else (*case 2.2.2*) clock i := toss(0; 1)
last increment i := true
else last increment i := false

Figure

1: The Synchronous Protocol for P i
3.1 Correctness Proof of the Synchronous Protocol
Throughout the proof we say that a processor P i increments its clock by 1 in a certain pulse, if P i assigns
last increment := true during this pulse. Otherwise, we say that assigns 0 to clock i .
Lemma 3.1 If nonfaulty processors P i and P j increment their clocks by 1 during some pulse P, then
immediately after P, clock
Proof: Assume towards contradiction that clock
P . Hence, during P , P i finds at least n \Gamma f clock values that are equal to x. At least n \Gamma 2f of them belong
to nonfaulty processors. Thus, P j
also receives n \Gamma 2f clock values that are equal to x. Hence, P j
receives
at most clock values that are equal to y. Since n ? 3f , it holds that
contradicts the possibility of P j
receiving at least n \Gamma f clock values that are equal to y.
Lemma 3.1 implies in a straightforward manner the correctness of the next two corollaries.
Corollary 3.2 After every pulse, the set of clock values of the nonfaulty processors contains at most two
elements. In case there are such two values, one of them is 0.
Corollary 3.3 If during a pulse P a nonfaulty processor P increments its clock value by 1 and the result
is 0, then immediately following P the clock values of all the nonfaulty processors are 0.
3.4 If during a pulse P that follows the first pulse, a nonfaulty processor P increments its clock to
be 1 without tossing a coin, then just before P all the nonfaulty processors' clock values were 0.
Proof: The variable last increment is assigned during every pulse. Thus, since P follows the first pulse,
indeed increments during Q, the pulse before P . Thus by Lemma 3.1 all the nonfaulty processors have
clock values 0 after Q and before P .
The next theorem uses the scheduler-luck game of [DIM-91, DIM-95] to analyze the randomized pro-
tocol. The scheduler-luck game has two competitors, scheduler (adversary) and luck. The goal of the
scheduler is to prevent the protocol from reaching a safe configuration while the goal of luck is to help the
protocol reach a safe configuration. For the synchronous protocol a configuration is safe if for all nonfaulty
processors, the logical clocks are equal and last increment is true. For our system the scheduler chooses
the message delays and clock drifts during the execution (within the predefined limitations). Each time
the processor, activated by the scheduler, tosses a coin, luck may intervene and determine the result of
the coin toss. It is proved in [DIM-91, DIM-95] that if, starting with any possible configuration c, luck
has a strategy to win the scheduler-luck game within i interventions and expected time t, then the system
reaches a safe configuration within expected time t . The main observation used for this proof is the
fact that if a coin toss result differs from the desired result (according to luck strategy) a configuration is
reached from which a new game can begin.
Theorem 3.5 In expected M lc \Delta 2 2(n\Gammaf ) pulses, the system reaches a configuration in which the value of
every nonfaulty processor's clock is 1.
Proof: The proof is by the use of Lemma 1 of [DIM-91] (Theorem 5 of [DIM-95]). We present a strategy
for luck to win the scheduler-luck game with 2(n \Gamma f) interventions and within M lc +2- time. The strategy
of luck is (1) wait for the first pulse to elapse. Thereafter, (2) luck waits till a pulse P in which a nonfaulty
processor with clock value 0 receives clock values that are 0. This occurs within the next M lc pulses (if
it does not occur by then, there is at least one nonfaulty processor that does not assign 0 to its clock during
successive pulses, which is impossible). In case (2.1) during this pulse all the nonfaulty processors are
either tossing a coin or assigning 1 without tossing. Then luck intervenes at most n \Gamma f times and fixes the
coin toss results of all the nonfaulty processors to be 1. Otherwise, (2.2) if there is a nonfaulty processor
P that is neither about to toss a coin nor about to assign 1 without tossing, then luck intervenes and fixes
all the coin toss results (less than f) to be 0. Note that before P , P 's clock is not equal to 0. Thus, by
3.4 no processor assigns 1 without tossing a coin. By Lemma 3.1 and the fact that some nonfaulty
processor tosses a coin during P , it holds that following P the clock values of all the nonfaulty processors
are 0. Therefore, in the next pulse case (2.1) is reached and luck could intervene and fix at most n \Gamma f
coin toss results to ensure that the desired global state is reached.
By Theorem 3.5 the system reaches a configuration in which the value of every nonfaulty processor's
clock is 1, in expected time M lc \Delta 2 2(n\Gammaf ) . It is easy to see that in any successive pulse, all the nonfaulty
processors have the same clock value. Thus the clock agreement requirement holds with the
clocks of the nonfaulty processors are incremented by 1 in every pulse and the pulses are constant time
apart, the clock validity requirement also holds. Note that the clock value could be multiplied by - (if -
is known), the time difference between two successive pulses, in order to yield a clock value that reflects
real time. Otherwise, the value of a of the clock validity requirement encodes 1=-.
3.2 Accelerating the Protocol
If M our protocol converges after expected 2 64 pulses. Certainly, because
of this time complexity this protocol cannot be used in practice. However, if M lc
, n, and f are all small 2
then the expected number of pulses required is reasonably small. For instance, if M
then the expected number of pulses is 128. We use the above observation to accelerate our protocol.
We achieve synchronization of clock values in the range of M expected number of
pulses that is less than 381 synchronization occurs within expected number of
pulses that is less than 58
We define the Chinese remainder counter by the use of the Chinese remainder theorem, which appears
in [Kn-81] p. 270:
Theorem 3.6 Let m 1
r be positive integers that are relatively prime in pairs, i.e.,
r be integers. Then there is
exactly one integer u that satisfies the conditions a - u ! a +m, and u j u
We use the Theorem for the case
. Let 2; 3; 5; :::; p j
be the series of prime numbers
up to the j-th prime such that 2 \Delta 3 We run j parallel versions
of our protocol. The i-th version runs the protocol with M lc
. Each message carries the value of j
clocks, one clock value for each version. The computation of the new clock value of some version i uses
the values received for this particular version and is independent from the computation of all the other
versions. Thus, the i-th version converges within expected pulses. Therefore, the expected time
for all the versions to be synchronized is less than (p 1
This is an upper bound
on the expectation since it corresponds to a scenario in which version i starts to synchronize after every
Now we apply the Chinese remainder theorem to show that every combination of those values is mapped
to one and only one number in the range 0 to 2 well-known technique could be used in order
to convert such a representation to its mapping (e.g., by Garner methods, c.f. p. 274 [Kn-81]).
The Chinese remainder theorem could be used for other implementations of distributed counters based
on the number presentation method suggested in [ST-67]. One possible use is as a memory and communication
efficient distributed counter. Let DC be a distributed counter that is maintained by a set of processors
are triggered by a common pulse. increments the counter mod p i in every trigger.
does not need to store the entire bits of the clock or to send messages to indicate the carry (when its
counter wraps around). Thus, when the counter is incremented no communication between processors is
needed. Only when the value of the counter is to be scanned is communication required.
4 Semi-synchronous Protocol
In this section we drop the assumption of common pulses. We present a self-stabilizing randomized protocol
for semi-synchronous systems. Due to space constraints, the formal description of the protocol and the full
correctness proof are excluded from this section.
2 It is reasonable to think of n and f as being small when a single processor can efficiently compute a task and additional
processors are added only to ensure reliability. Let the reliability be f=(n the ratio of the number of faulty processors
to the total number of processors. To reach a reliability of 0.25, the number of processors needed (and thus, in general terms,
the blowup in the hardware and cost) is four. To improve the reliability to 2/7-0.28 the blowup would be 7. Asymptotically,
we need an infinite blowup to reach reliability of 1/3. Thus, most devices would use a relatively small number of processors
for which our protocol stabilizes in a relatively short time.
Our protocol uses the fault-tolerant averaging function first introduced in [DL+-86] for solving approximate
agreement and later used for clock synchronization in [WL-88]. Given a multiset of values, a
processor applies the function by discarding the f highest and f lowest values and then taking the midpoint
of the remaining values. It has been shown that this function, when used in the context of the protocols
of [DL+-86, WL-88], approximately halves the range of values held by the nonfaulty processors.
In our situation, with bounded clocks, the notions of "highest" and "lowest" must be appropriately
modified. But the real difficulty in directly applying the previous result is that the analysis showing the
range is cut in half depends on all nonfaulty processors working with approximately the same multisets at
each "round". The multisets can differ arbitrarily in the values corresponding to the faulty processors, but
the values corresponding to nonfaulty processors must be close to the same (allowing for error introduced
by clock drift and uncertain message delays). This "round" structure can be achieved because the actions
of the processors are roughly synchronized in time in the [WL-88] protocols, due to the assumption of
initial synchronization or of distinguished initial states.
Since our protocol is self-stabilizing, it cannot rely on either of those assumptions. Thus using the fault-tolerant
averaging function in the obvious manner, with the processors starting with arbitrary information
and collecting clock values at arbitrary times, would not ensure that the function is applied at the processors
in rounds. For instance, P could apply the function to a multiset M , then subsequently Q could apply the
function to a multiset M 0 that reflects P 's new value instead of P 's old value.
To achieve some sort of approximate rounds for applying the fault-tolerant averaging function, we first
use randomization to bring all the clock values of the nonfaulty processors close to each other. Once this
is achieved, all the nonfaulty processors collect (approximately) the same multisets from all the nonfaulty
processors. In this stage the midpoint averaging function can be shown (cf. [WL-88]) to approximately
halve the nonfaulty clock values, thus overcoming the ongoing effects of clock drift and uncertainty of
message delay.
We now describe the protocol. A processor P i
has two synchronization procedures. The first is called
the averaging procedure and the second is the jumping procedure. The averaging procedure is executed
when the value of clock i is in a range greater than 0 and smaller than ffi and T a time has elapsed since the
previous time that clock i had a value in this range. The jumping procedure is executed when T j time has
elapsed since the previous execution of the jumping procedure and P i is not currently in the range dedicated
for executing the averaging function. P i
measures T a
and T j
using its physical clock. Roughly speaking,
the jumping procedure causes the clocks of the nonfaulty processors to be within a small range. Then the
averaging procedure keeps the clocks of the nonfaulty processors in a small range by approximately halving
the range each time the clock values wrap around.
Both the synchronization procedures of processor P i
start with a request for clock values. During the
execution of the averaging procedure, a processor measures 2(d in order to make sure that
all the requests for clock values arrive at their destinations and the responses return before it proceeds to
decide on a new clock value. Thus each execution of the averaging procedure takes some period of time.
We define the symmetric clock of clock i to be clock In both procedures, if P i finds
clock values within a small range ffi from clock i , then P i eliminates f values from each side of the
symmetric clock value 3 . Then, in the jumping procedure, P i chooses one of the clock values at random
from the reduced clock values list, while in the averaging procedure, P i
chooses the midpoint of the reduced
clock values list. In both procedures, if less than processors are found within ffi from clock i , P i chooses
randomly one of the clock values.
3 For instance, if the collected values are 2,3,10,11, the symmetric clock value is 7 and are eliminated.
4.1 Correctness Proof Sketch of the Semi-synchronous Protocol
A period of time is a jumping period if no nonfaulty processor executes the averaging procedure during this
period. We choose T a
to be 2(n \Gamma f)(5T j
. The next lemma proves that the above choice
yields the existence of a period of length 5T ae) that is a jumping period.
Lemma 4.1 Every T a time there is a jumping period that is at least 5T j
long.
Proof: A processor measures time by the use of its physical clock, whose drift rate from real time is at
most ae. Thus, if a processor measures a period of time T on its physical clock, then the real time elapsed
during the measurement is at least T=(1 + ae) and at most T(1 ae). By the way T a is chosen, in every
period of length
processor executes the averaging function at most once. A processor measures 2(d
to make sure that the requests for clock values arrive at their destinations and the responses arrive before
it decides on a new clock value. Thus, the time that the averaging function is executed by each processor
in a period of ae). Hence, the total
time of averaging of all the processors during a period of 2(n \Gamma f)(5T j
ae) is no more than
ae). Therefore, the total non averaging time is at least 2(n \Gamma
ae). By the pigeon hole principle at least one jumping
period is of length
A safe configuration is a system configuration in which the nonfaulty processors' clocks are within ffi=8
of each other. Moreover, in case a processor is in the middle of collecting clock values then all the clock
values in transit sent by nonfaulty processors are within this range too.
We use the following assumptions in our correctness proof:
Assumption 1: (1
Assumption 2: (n
Lemma 4.2 During any jumping period of length 5T j (1+ae), with probability at least 1=n 6(n\Gammaf ) , the system
reaches a safe configuration.
Sketch of proof: We prove the lemma by presenting a sequence of random choice results, that forces
the system to reach a configuration in which the clocks of all the nonfaulty processors are less than ffi =8
apart. This sequence of random choice results has probability of at least 1=n 6(n\Gammaf ) to occur. Let c be the
configuration at the beginning of the jumping period.
Without loss of generality we assume that the number of faulty processors f is the maximal possible 4
that does not violate the inequality n ? 3f . Let c be the first configuration in a choosing period. For
every nonfaulty processor P , luck counts the number of other nonfaulty processors that have clocks within
clock in the configuration c. Each nonfaulty processor that has at least
clock values is called an anchor.
We claim that all the anchor processors are at most 2T r apart. Assume towards contradiction that there
are two nonfaulty anchor processors, P and Q, such that their clock values are more than 2T r apart. Thus,
P is surrounded by processors and Q is surrounded by different nonfaulty
4 In case there are fewer faulty processors, one could assume that some of the nonfaulty processors "only behave" like
nonfaulty processors.
processors. Therefore, the total number of nonfaulty processors is at least 2(n \Gamma
contradiction.
Note that it is possible that no anchor processor exists. In this case luck chooses one nonfaulty processor
to be an anchor processor.
Then luck chooses a single anchor processor A out of the anchor processors.
Until every nonfaulty processor executes the jump procedure twice luck uses the following strategy:
Every time a processor, P j , chooses a clock value and the value of the clock of A is a possible choice (i.e.,
either
does not find or A is in the reduced clock values list), this value is chosen;
otherwise the value of clock j is not changed. Let c 1
be the first configuration reached from c after each
processor executes the jump procedure at least twice with results according to the strategy of luck. Let E 1
be the execution that starts with c and ends with c 1
. Since in a jumping period every nonfaulty processor
chooses a clock value at least once in every period of length T
occurs at most 2T
after c.
We now show that in c 1
all the nonfaulty processors are within 2T r of each other. We
first show that any nonanchor processor, P , assigns the value of A's clock to P 's clock either in the first
execution of the jump procedure or in the second one. Every processor collects the clock values during
every execution of the jump procedure. In particular a nonanchor processor, P j , receives the value of the
clock of A before the second execution of the jump procedure. Next we show that, in the second execution
of the jump procedure P j can choose the value of A's clock.
The choice of P j
is restricted to a subset of the clock values that P j
read, only if P j
finds
values within ffi range of clock j . Since P j is a nonanchor processor it holds in c 1
that there are less than
processors within ffi range of clock j . Moreover, no nonfaulty processor can assign a clock value within
range of clock j since: (1) Every nonfaulty processor P k that changes its clock value by the use of the
jump procedure assigns the clock value of A (with up to ffl range from the clock of A). (2) Every nonfaulty
processor P k that does not change its clock value by the use of the jump procedure can have a rate of drift
from the clock of P j of at most 2ae. Thus, the difference between clock j and clock k can be shorten by at
most 2T j
was more than T r
in c then P j cannot consider P k to have a clock in ffi range from clock j during
assigns clock j
by the value of the clock of A).
This proves that in c 1
all the nonanchor processors are within ffl ae from A's clock. The anchor
processors that do not assign the clock value of A to their clock during
were at most 2T r apart in c,
thus they are at most 2T r
The fact that all the nonfaulty processors are within a small range of each other is used to define a
new anchor processor A 0 . A 0 is the nonfaulty processor left after removing f nonfaulty processors with the
highest clock values (mod M lc ) and f nonfaulty processors with the smallest values (mod M lc ).
?From c 1
and until every processor executes the jump procedure at least twice, luck continues as follows:
Any processor P i that is in the process of collecting clock values in c 1
does not change clock i in the first
execution of the jump procedure. For any other execution of the jump function, luck intervenes to fix the
result to be the clock of A 0 or a clock of a processor that has already set its clock to the value of A 0 's clock
since c 1
. We have to prove that the above is a possible result of the jump function. This is obvious when
the processor does not find processors within ffi from its clock, since the choice is not restricted. It
is also clear for the first set of processors that execute the jump procedure and use the clock values in c 1
as the base for the decision on the new clock value. Moreover, since luck intervenes and fixes all those
results to be the value of the clock of A 0 , the reduced list of every processor that uses the new clock values
includes either the clock of A 0 or a clock of a processor that assigned its clock by the clock of A 0 .
Hence, in the first configuration, c 2
, that follows the first two executions of the jump function of all the
processors following c 1
, all the nonfaulty processors are within (n ae)ae of each other, which,
by assumption 2, is less than ffi =8.
Following c 2
any processor that is waiting for answers in the process of collecting clocks does not change
its clock value. Thus, (d
a safe configuration is reached.
The length of the execution is 2T j
is reached, 2T j
to c 2
and additional
configuration is reached. Thus, a safe configuration is reached following
ae) from c. By Assumption 1, 5T ae). Thus any processor could
choose at most six times in such a range. Thus the total number of interventions is
Lemma 4.3 In any configuration of any execution that starts with a safe configuration, the clock values
of all the nonfaulty processors are within at most ffi=2 of each other.
The main observation made for the proof of the above lemma is that starting in a safe configuration
every processor that either executes the jumping or the averaging procedure finds clock values within
ffi from its clock value. Thus, the new clock value chosen when jumping or averaging is in the range of clock
values of the nonfaulty processors. The averaging procedure approximately halves the range of the clock
values of the nonfaulty processors whenever they pass the zero clock value.
Theorem 4.4 In expected O(T a n 6(n\Gammaf stabilizes.
Concluding Remarks
Extensive research has been done to find efficient clock synchronization protocols in the presence of Byzantine
faults. In this work we considered a more severe (and realistic) model of faults, i.e., one that takes
into account transient faults as well as Byzantine faults. When arbitrary corruption of state is possible,
as is often the case with transient faults, it is no longer reasonable to approximate unbounded clocks with
bounded clocks, no matter how large. Consequently, clocks that can take on only a bounded number of
values (and wrap around when appropriate) have been assumed in this paper. We presented two randomized
self-stabilizing protocols for synchronizing bounded clocks in the presence of f Byzantine processor
failures, where n ? 3f .
We believe that our observations and definitions for the types of faults to be considered and the type
of clocks (namely, bounded) reflect reality and open new directions for research. Protocols designed under
our fault tolerance model are more robust than existing clock synchronization protocols. Therefore, such
protocols might be preferred by the system implementer over protocols that cope with only Byzantine
faults.

Acknowledgment

Many thanks to Brian Coan, Injong Rhee and Swami Natarajan for helpful discussions




--R

"Self stabilizing systems in spite of distributed control,"
"On the possibility and impossibility of achieving clock synchronization,"
"Uniform dynamic self stabilizing leader election,"
"Analyzing Expected Time by Scheduler-Luck Games,"
"Reaching approximate agreement in the presence of faults,"
"Wait-free clock synchronization,"
"Unifying self-stabilization And fault-tolerance,"
"Fault-tolerant clock synchronization,"
The art of computer programming
"Synchronizing clocks in the presence of faults,"
"The Byzantine generals problem,"
"Inexact agreement: accuracy, precision and graceful degradation,"
"Fault-tolerant clock synchronization in distributed systems,"
"Optimal clock synchronization,"
Residue arithmetic and its applications to computer technology
"A new fault-tolerant algorithm for clock synchronization,"
--TR
Synchronizing clocks in the presence of faults
Reaching approximate agreement in the presence of faults
On the possibility and impossibility of achieving clock synchronization
Optimal clock synchronization
A new fault-tolerant algorithm for clock synchronization
Fault-Tolerant Clock Synchronization in Distributed Systems
Wait-free clock synchronization
Unifying self-stabilization and fault-tolerance
The art of computer programming, volume 2 (3rd ed.)
Inexact agreement
The Byzantine Generals Problem
Self-stabilizing systems in spite of distributed control
Analyzing Expected Time by Scheduler-Luck Games
Uniform Dynamic Self-Stabilizing Leader Election (Extended Absrtact)
Fault-tolerant clock synchronization

--CTR
Ariel Daliot , Danny Dolev, Self-stabilizing byzantine agreement, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA
clock synchronization;self-stabilization;byzantine failures