Regulation 2022(CBCS Scheme) BCS515D- Distributed Systems

Module-3

Time and Global States- Introduction-Clocks, events and process states-Synchronizing

physical clocks-Logical time and logical clocks-Global states

Time and Global States

There are two formal models of distributed systems: synchronous and asynchronous.

Synchronous distributed systems have the following characteristics:

 the time to execute each step of a process has known lower and upper bounds;

 each message transmitted over a channel is received within a known bounded

time;

 Each process has a local clock whose drift rate from real time has a known
bound.

Asynchronous distributed systems, in contrast, guarantee no bounds on process execution

speeds, message transmission delays, or clock drift rates. Most distributed systems we
discuss, including the Internet, are asynchronous systems.

Generally, timing is a challenging an important issue in building distributed systems.

Consider a couple of examples:

 Suppose we want to build a distributed system to track the battery usage of a

bunch of laptop computers and we'd like to record the percentage of the battery
each has remaining at exactly 2pm.

 Suppose we want to build a distributed, real time auction and we want to know
which of two bidders submitted their bid first.

 Suppose we want to debug a distributed system and we want to know whether

variable x1 in process p1 ever differs by more than 50 from variable x2 in process
p2.

In the first example, we would really like to synchronize the clocks of all participating
computers and take a measurement of absolute time. In the second and third examples,
knowing the absolute time is not as crucial as knowing the order in which events occurred.

R.Tharani, AP, AIML,SSCE

 Regulation 2022(CBCS Scheme) BCS515D- Distributed Systems
Module-3
Clock Synchronization

Every computer has a physical clock that counts oscillations of a crystal. This hardware clock
is used by the computer's software clock to track the current time. However, the hardware
clock is subject to drift -- the clock's frequency varies and the time becomes inaccurate. As a
result, any two clocks are likely to be slightly different at any given time. The difference
between two clocks is called their skew.

There are several methods for synchronizing physical clocks. External

synchronization means that all computers in the system are synchronized with an external
source of time (e.g., a UTC signal). Internal synchronization means that all computers in the
system are synchronized with one another, but the time is not necessarily accurate with
respect to UTC.

In a synchronous system, synchronization is straightforward since upper and lower bounds on

the transmission time for a message are known. One process sends a message to another
process indicating its current time, t. The second process sets its clock to t +
(max+min)/2 where max and min are the upper and lower bounds for the message
transmission time respectively. This guarantees that the skew is at most (max-min)/2.

Cristian's method for synchronization in asynchronous systems is similar, but does not rely on
a predetermined max and min transmission time. Instead, a process p1 requests the current
time from another process p2 and measures the RTT (Tround) of the request/reply.
Whenp1 receives the time t from p2 it sets its time to t + Tround/2.

The Berkeley algorithm, developed for collections of computers running Berkeley UNIX, is
an internal synchronization mechanism that works by electing a master to coordinate the
synchronization. The master polls the other computers (called slaves) for their times,
computes an average, and tells each computer by how much it should adjust its clock.

The Network Time Protocol (NTP) is yet another method for synchronizing clocks that uses
a hierarchical architecture where he top level of the hierarchy (stratum 1) are servers
connected to a UTC time source.

R.Tharani, AP, AIML,SSCE

 Regulation 2022(CBCS Scheme) BCS515D- Distributed Systems
Module-3
Logical Time

Physical time cannot be perfectly synchronized. Logical time provides a mechanism to define
the causal order in which events occur at different processes. The ordering is based on the
following:

 Two events occurring at the same process happen in the order in which they
are observed by the process.

 If a message is sent from one process to another, the sending of the message
happened before the receiving of the message.

 If e occurred before e' and e' occurred before e" then e occurred before e".

"Lamport called the partial ordering obtained by generalizing these two relationships
the happened-before relation." ( → )

In the figure, a → b and c → d . Also, b → c and d → f , which means that a → f . However,

we cannot say that a → e or vice versa; we say that they are concurrent

(a || e).

A Lamport logical clock is a monotonically increasing software counter, whose value

need bear no particular relationship to any physical clock. Each process pi keeps its own
logical clock, Li, which it uses to apply so-called Lamport timestamps to events.

R.Tharani, AP, AIML,SSCE

 Regulation 2022(CBCS Scheme) BCS515D- Distributed Systems
Module-3
Lamport clocks work as follows:

LC1: Li is incremented before each event is issued at pi.

LC2:

When a process pi sends a message m, it piggybacks on m the value t = Li.

On receiving (m, t), a process pj computes Lj: = max (Lj, t) and then applies LC1 before time
stamping the event receive (m).

An example is shown below:

If e → e ' then L (e) < L (e'), but the converse is not true. Vector clocks address this problem.
"A vector clock for a system of N processes is an array of N integers." Vector clocks are
updated as follows:

VC1: Initially, VI[j] = 0 for I, j = 1, 2, N

VC2: Just before pi timestamps an event, it sets Vi[i]:=Vi[i]+1.

VC3: pi includes the value t = Vi in every message it sends.

VC4: When pi receives a timestamp t in a message, it sets Vi[j]:=max(Vi[j], t[j]), for 1, 2,

...N. Taking the component wise maximum of two vector timestamps in this way is known as
a merge operation.

R.Tharani, AP, AIML,SSCE

 Regulation 2022(CBCS Scheme) BCS515D- Distributed Systems
Module-3
An example is shown below:

Vector timestamps are compared as follows:

V=V' iff V[j] = V'[j] for j = 1, 2, ..., N

V <= V' iff V[j] <=V'[j] for j = 1, 2, ..., N

V < V' iff V <= V' and V != V'

If e → e ' then V(e) < V(e') and if V(e) < V(e') then e → e ' .

Global States

It is often desirable to determine whether a particular property is true of a distributed system

as it executes. We'd like to use logical time to construct a global view of the system state
and determine whether a particular property is true. A few examples are as follows:

 Distributed garbage collection: Are there references to an object anywhere in

the system? References may exist at the local process, at another process, or in
the communication channel.

 Distributed deadlock detection: Is there a cycle in the graph of the "waits for"
relationship between processes?

 Distributed termination detection: Has a distributed algorithm terminated?

R.Tharani, AP, AIML,SSCE

 Regulation 2022(CBCS Scheme) BCS515D- Distributed Systems
Module-3
 Distributed debugging: Example: given two processes p1 and p2 with variables
x1 and x2 respectively, can we determine whether the condition |x1-x2| > δ is ever
true.

In general, this problem is referred to as Global Predicate Evaluation. "A global state
predicate is a function that maps from the set of global state of processes in the system ρ to
{True, False}."

 Safety - a predicate always evaluates to false. A given undesirable property

(e.g., deadlock) never occurs.

 Liveness - a predicate eventually evaluates to true. A given desirable

property (e.g., termination) eventually occurs.

R.Tharani, AP, AIML,SSCE

 Regulation 2022(CBCS Scheme) BCS515D- Distributed Systems
Module-3

Cuts

Because physical time cannot be perfectly synchronized in a distributed system it is not

possible to gather the global state of the system at a particular time. Cuts provide the ability
to "assemble a meaningful global state from local states recorded at different times".

Definitions:

 ρ is a system of N processes pi (i = 1, 2, ..., N)

 history(pi) = hi = < e i 0 , e i 1 ,...>

 h i k =< e i 0 , e i 1 ,..., e i k > - a finite prefix of the process's history

 s i k is the state of the process pi immediately before the kth event occurs

 All processes record sending and receiving of messages. If a process pi records

the sending of message m to process pj and pj has not recorded receipt of the
message, then m is part of the state of the channel between pi and pj.

 A global history of ρ is the union of the individual process histories: H

= h0 ∪ h1 ∪ h2 ∪...∪hN-1

 A global state can be formed by taking the set of states of the

individual processes: S = (s1, s2, ..., sN)

 A cut of the system's execution is a subset of its global history that is a union
of prefixes of process histories (see figure below).

 The frontier of the cut is the last state in each process.

 A cut is consistent if, for all events e and e':

o ( e ∈ C and e ' → e ) ⇒ e ' ∈ C

 A consistent global state is one that corresponds to a consistent cut.

R.Tharani, AP, AIML,SSCE

 Regulation 2022(CBCS Scheme) BCS515D- Distributed Systems
Module-3

Distributed Debugging

To further examine how you might produce consistent cuts, we'll use the distributed
debugging example. Recall that we have several processes, each with a variable x i. "The
safety condition required in this example is |xi-xj| <= δ (i, j = 1, 2, ..., N)."

The algorithm we'll discuss is a centralized algorithm that determines post hoc whether the
safety condition was ever violated. The processes in the system, p1, p2, ..., pN, send their states
to a passive monitoring process, p0. p0 is not part of the system. Based on the states collected,
p0 can evaluate the safety condition.

Collecting the state: The processes send their initial state to a monitoring process and send
updates whenever relevant state changes, in this case the variable x i. In addition, the
processes need only send the value of x i and a vector timestamp. The monitoring process
maintains an ordered queue (by the vector timestamps) for each process where it stores the
state messages. It can then create consistent global states which it uses to evaluate the safety
condition.

R.Tharani, AP, AIML,SSCE

 Regulation 2022(CBCS Scheme) BCS515D- Distributed Systems
Module-3

R.Tharani, AP, AIML,SSCE

 Regulation 2022(CBCS Scheme) BCS515D- Distributed Systems
Module-3
Let S = (s1, s2, ..., SN) be a global state drawn from the state messages that the
monitor process has received. Let V(si) be the vector timestamp of the state si
received from pi. Then it can be shown that S is a consistent global state if and
only if:

V(si)[i] >= V(sj)[i] for i, j = 1, 2, ..., N

R.Tharani, AP, AIML,SSCE

 Regulation 2022(CBCS Scheme) BCS515D- Distributed Systems
Module-3

R.Tharani, AP, AIML,SSCE