Distributed Computing (2008)
756 pág.

Distributed Computing (2008)

DisciplinaAlgorítimos Distribuídos28 materiais272 seguidores
Pré-visualização50 páginas
crash recovery
An entire snapshot of the system at virtual time \u201ct\u201d can be constructed by a
procedure in which each process \u201csnapshots\u201d itself as it passes virtual time t
in the forward direction and \u201cunsnapshots\u201d itself whenever it rolls back over
virtual time \u201ct\u201d. Whenever GVT exceeds \u201ct,\u201d the snapshot is complete and
Example: distributed discrete event simulations Distributed discrete event
simulation [1, 16, 21] is the most studied example of virtual time systems;
every process represents an object in the simulation and virtual time is
identified with simulation time. The fundamental operation in discrete event
simulation is for one process to schedule an event for execution by another
process at a later simulation time. This is emulated by having the first
process send a message to the second process with the virtual receive time
of the message equal to the event\u2019s scheduled time in the simulation. When
an event message is received by a process, there are three possibilities: its
timestamp is either before, after, or equal to the local value of simulation
If its timestamp is after the local time, an input event combination is formed
and the appropriate action is taken. However, if the timestamp of the received
event message is less than or equal to the local clock value, the process has
78 Logical time
already processed an event combination with time greater than or equal to the
incoming event. The process must then rollback to the time of the incoming
message which is done by an elaborate checkpointing mechanism that allows
earlier states to be restored. Essentially an earlier state is restored, input event
combinations are rescheduled, and output events are cancelled by sending
antimessages. The process has buffers that save past inputs, past states, and
Distributed discrete event simulation is one of the most general applications
of the virtual time paradigm because the virtual times of events are completely
under the control of the user, and because it makes use of almost all the
degrees of freedom allowed in the definition of a virtual time system.
3.9 Physical clock synchronization: NTP
3.9.1 Motivation
In centralized systems, there is no need for clock synchronization because,
generally, there is only a single clock. A process gets the time by simply
issuing a system call to the kernel. When another process after that tries to
get the time, it will get a higher time value. Thus, in such systems, there is a
clear ordering of events and there is no ambiguity about the times at which
these events occur.
In distributed systems, there is no global clock or common memory. Each
processor has its own internal clock and its own notion of time. In practice,
these clocks can easily drift apart by several seconds per day, accumulating
significant errors over time. Also, because different clocks tick at different
rates, they may not remain always synchronized although they might be syn-
chronized when they start. This clearly poses serious problems to applications
that depend on a synchronized notion of time. For most applications and
algorithms that run in a distributed system, we need to know time in one or
more of the following contexts:
\u2022 The time of the day at which an event happened on a specific machine in
the network.
\u2022 The time interval between two events that happened on different machines
in the network.
\u2022 The relative ordering of events that happened on different machines in the
Unless the clocks in each machine have a common notion of time, time-
based queries cannot be answered. Some practical examples that stress the
need for synchronization are listed below:
\u2022 In database systems, the order in which processes perform updates on a
database is important to ensure a consistent, correct view of the database.
79 3.9 Physical clock synchronization: NTP
To ensure the right ordering of events, a common notion of time between
co-operating processes becomes imperative.
\u2022 Liskov [10] states that clock synchronization improves the performance of
distributed algorithms by replacing communication with local computation.
When a node p needs to query node q regarding a property, it can deduce
the property with some previous information it has about node p and its
knowledge of the local time in node q.
\u2022 It is quite common that distributed applications and network protocols use
timeouts, and their performance depends on how well physically dispersed
processors are time-synchronized. Design of such applications is simplified
when clocks are synchronized.
Clock synchronization is the process of ensuring that physically distributed
processors have a common notion of time. It has a significant effect on
many problems like secure systems, fault diagnosis and recovery, scheduled
operations, database systems, and real-world clock values. It is quite common
that distributed applications and network protocols use timeouts, and their
performance depends on how well physically dispersed processors are time-
synchronized. Design of such applications is simplified when clocks are
Due to different clocks rates, the clocks at various sites may diverge with
time, and periodically a clock synchrinization must be performed to correct
this clock skew in distributed systems. Clocks are synchronized to an accurate
real-time standard like UTC (Universal Coordinated Time). Clocks that must
not only be synchronized with each other but also have to adhere to physical
time are termed physical clocks.
3.9.2 Definitions and terminology
We provide the following definitions [13,14]. Ca and Cb are any two clocks.
1. Time The time of a clock in a machine p is given by the function Cp\ufffdt\ufffd,
where Cp\ufffdt\ufffd= t for a perfect clock.
2. Frequency Frequency is the rate at which a clock progresses. The fre-
quency at time t of clock Ca is C
3. Offset Clock offset is the difference between the time reported by a clock
and the real time. The offset of the clock Ca is given by Ca\ufffdt\ufffd\u2212 t. The
offset of clock Ca relative to Cb at time t \u2265 0 is given by Ca\ufffdt\ufffd\u2212Cb\ufffdt\ufffd.
4. Skew The skew of a clock is the difference in the frequencies of the clock
and the perfect clock. The skew of a clock Ca relative to clock Cb at time
t is C \u2032a\ufffdt\ufffd\u2212C \u2032b\ufffdt\ufffd.
If the skew is bounded by \ufffd, then as per Eq.(3.1), clock values are allowed
to diverge at a rate in the range of 1\u2212\ufffd to 1+\ufffd.
80 Logical time
5. Drift (rate) The drift of clock Ca is the second derivative of the clock
value with respect to time, namely, C \u2032\u2032a \ufffdt\ufffd. The drift of clock Ca relative
to clock Cb at time t is C
a \ufffdt\ufffd\u2212C \u2032\u2032b \ufffdt\ufffd.
3.9.3 Clock inaccuracies
Physical clocks are synchronized to an accurate real-time standard like UTC
(Universal Coordinated Time).
However, due to the clock inaccuracy discussed above, a timer (clock) is
said to be working within its specification if
1\u2212\ufffd\u2264 dC
\u2264 1+\ufffd\ufffd (3.1)
where constant \ufffd is the maximum skew rate specified by the manufacturer.
Figure 3.8 illustrates the behavior of fast, slow, and perfect clocks with respect
to UTC.
Offset delay estimation method
The Network Time Protocol (NTP) [15], which is widely used for clock syn-
chronization on the Internet, uses the the offset delay estimation method. The
design of NTP involves a hierarchical tree of time servers. The primary server
at the root synchronizes with the UTC. The next level contains secondary
servers, which act as a backup to the primary server. At the lowest level is
the synchronization subnet which has the clients.
Clock offset and delay estimation
In practice, a source node cannot accurately estimate the local time on the
target node due to varying message or network delays between the nodes.
This protocol employs a very common practice of performing several trials
and chooses the trial with the minimum delay. Recall that Cristian\u2019s