Incremental clock
synchronization
Simulator
Project Description
In this version of the clock synchronization problem, processors
have access to local clocks, which run at the rate of real-time; some clock
may be corrupted and read wrong values. The clocks are not initialized
and processors need to adjust them to be as close as possible (using an
additive adjustment factor). A related issue is to allow processors
to join the system, without causing already-running processors to move
their clock back. Most algorithms for this problem require processors to
read current clock values from all other processors (in one communication
round), remove extreme values, and average.
In our setting, however, a processor can get only a few (constant number
of) clock values in each communication round and send only a few (or single)
values in each round. A simple algorithm was suggested for this setting,
which increments/decrements the adjustment factor, depending on whether
the received clock value is larger/bigger than the current clock.
Goal:
The purpose of this project is to explore clock synchronization
algorithms in this situation and compare them with unrestricted clock synchronization
algorithms, by means of simulation.
Definitions:
Gap - range of clock values
that will indicate synchronization. It will be determinate by founding
minimum and maximum clock values and measuring the difference between them.
Logical clock - Logical
clocks are clocks which are synchronized relatively to each other.
Algorithms:
The additive adjustment
algorithm (by Hagit Attiya).
1.Each process has its own logical clock.
2.Each tick, the process sends its clock value to another process.
3.When a process receives a clock value from another process, it updates
the own local clock:
Increment if the value is bigger then
own local clock (+1);
Decrement if the value less then own
local clock (-1);
The authenticated algorithm
(by Srikant and Toueg).
The following is an informal description of a synchronization
algorithm for systems with n processes of which most f are faulty. The
algorithm requires that n>=2f+1 and that messages are authenticated. Informally,
authentication prevents a faulty process from changing a message it relays,
or introducing a new message into the system and claiming to have received
it from some other process.
Let P be the logical time between resynchronizations.
A process expects the k-th resynchronization, for k>=1, at time kP on logical
clock. When its logical clock achieves kP ticks, it broadcasts a signed
message of the form (round k), indicating that its ready to resynchronize.
When a process receives such a message from f+1, it knows that at least
one correct process is ready to resynchronize, even if its logical clock
has not yet reached kP. A process resynchronizes by starting its k-th clock,
setting it to kP+a where a is constant. To ensure that clocks are
never set back, a is chosen to be greater then the increase in previous
resynchronization. To ensure that clocks are never set back, a is chosen
to be greater then the increase in previous resynchronization. After resynchronizing,
the process also relays the f+1 signed (round k) messages to all other
processes to ensure that they also resynchronize.
Algorithm
cobegin
If clock = kP
/* ready to start new clock */
? sign and broadcast (round k) fi
//
If accepted the message (round k)
/* received f+1 signed (round k) messages */
? clock = kP +a;
/* start new clock */
relay all f+1 signed messages to all fi
coend
In case that a new process p wishes to join the system, it sends a message
(joining) to the processes already in the system. It then receives messages
from these processes and determines the number i of the round being executed.
Since p could have started this algorithm in the middle of a resynchronization
period, it waits for resynchronization period i+1 and starts its logical
clock when it accepts a (round i+1) message. Process p begins to run the
resynchronization algorithm described earlier.
Input:
The
system has set of inputs, describing scenarios of three types:
Input
for all scenarios
1.Number
of messages is sent by one process per synchronization round .
2.The
way of sending of the messages (random, sequential…).
Scenarios:
1.Behaviour
of gap depending on time (in clock ticks)
INPUT:
1.
n - Total number of processes.
2.
Range of values of local clocks (minimum, maximum).
3.
p - Percent of correct (already synchronized) processes – which values
will be average of minimum and maximum.
4.
t - Time to stop the test (in ticks).
OUTPUT:
Output
is table of gap depending on time, where axe x is ticks from 0 to t and
axe y is gap.
2.Behavior
of number of rounds of synchronization (ticks) depending on number of processes.
INPUT:
1.
n - Max number of processes.
2.
Range of values of local clocks (minimum, maximum).
3.
p - Percent of correct (already synchronized) processes –which values will
be average of minimum and maximum.
4.
Gap to stop synchronization.
5.
Max time (with default value).
OUTPUT:
Output
is table of time (number of ticks) to reach the given gap per number of
processes, where axe x is number of processes from 2 to n and axe y is
number of rounds of synchronization – time that was taken to reach the
given gap.
N
processes created with given initial value. Then created new process with
local clock 0. The output is time of synchronization of each algorithm
and how close the new process gets to old ones in each test (gap).
INPUT:
1.
n - Max number of processes.
2.
Local clock of these processes.
3.
Initial value of new coming process.
4.
Gap to stop synchronize.
OUTPUT
Output
is table of time vs. number of processes. Axes are same as in second scenario.
Implementation:
The
project is written in C++ in NT
Each
process is represented by object. The scheduler will manage the clock system
and will allow equal execution possibility for every process at each synchronization
round. At every time slot (tick) a process reads messages sent to it in
previous time slot, updates its clock value and sends its messages according
to new clock value.
Each
process at every time slot executes both given algorithms and has two distinct
local clocks –one per algorithm. Thus at end of each time slot we can watch
behavior of the algorithms.
goto
output result
goto
downloads
Downloads
ClockProj.Zip
Class Diagram: Class Diagram.doc
Conclusions:
-
Incremental clock synchronization algorithm (by Hagit Attya)
does not allow syncronization when number of messages sent by particular
process is more than ~30% of number of processes.
-
The system will always synchronize in case of ST algorithm
in constant period of time (only if there are N/2 correct processes - this
is a main defect).
-
The algorithm of Hagit Attya syncronizes the system without
depending on number of correct processes (by experiment testing).
-
The optimal execution of Incremental clock synchronization
algorithm (by Hagit Attya) is reached when each process sends single message
in sequential order.
-
In case on integration of new process into arlready
synchronized system clock value of a new process does not influence on
rate of syncronization.
The general conclusion: one can use incremental
algorithm to get clocks value into close range (to reach situation where over
than half of processes are syncronized) and than proceed with ST algorithm that
allows better performance.
Written by:
| Greg
Fidelman |
sgregf@t2.technion.ac.il |
| Anna
Reitman |
s0anna0r@t2.technion.ac.il |
Supervisors:
| Hagit Attya |
hagit@cs.technion.ac.il |
| Saar Pilosof |
psaar@cs.technion.ac.il |
|
Home