BUILDERS ENGINEERING COLLEGE, KANGEYAM

UNIT IV
1. What is meant by hardware and software clock?
Clock devices can be programmed to generate interrupts at regular intervals in orders that,
for example, time slicing can be implemented. The operating system reads the node’s
hardware clock value, H(t) , scales it and adds an offset so as to produce software clock C
(t)=αHi(t)+β that approximately measures real ,physical time t for process pi.
2. What is clock resolution?
Note that successive events will correspond to different timestamps only if the clock
resolution-the period between updates of the clock-value-is smaller than the time interval
betw4een successive events. The rate at which events occur depends on such factors as the
length of the processor instruction cycle.
3. What is clock drift?
Clock drift, which means that they count time at different rates and so diverge. The
underling oscillators are subject to physical variations, with the consequence that their
frequencies of oscillation differ. Moreover ,even the same clock’s frequency varies with
temperature. Designs exist that attempt to compensate for this variation, but they cannot
eliminate it. A clock’s drift rate is the change in the offset (difference in reading) between
the clock and a nominal perfect reference clock per unit of time measured by the reference
clock.
4. What is IAT?
Computer clocks can be synchronized to external sources of highly accurate time. The most
accurate physical clocks use atomic oscillators, whose drift rate is about one part in 1013.the
most accurate physical clocks use atomic oscillators, whose drift rate is about one part in
1013. The output of these atomic clocks is used as the standard for elapsed real a time,
known as International Atomic Time.
5. What is CUT?
Coordinated Universal Time-abbreviated as UTC (From the French equivalent)-is as
international standard for timekeeping. It is based on atomic time, but a so-called ‘leap
second’ is inserted-or, more rarely, deleted-occasionally to keep it in step with astronomical
time.
6. What is meant by external synchronization?
In order to know at what time of day events occur at the processes in our distributed system
–it is necessary to synchronize the processes’ clocks, C , with an authoritative, external
source of time. This is external synchronization.
We define these two modes of synchronization more closely as follows, over an interval of
real time I:
 For a synchronization bound D>0,|Ci(t)-Cj(t)|<D for i=0,1,2,… N and for a source S of
UTC time, |S(t)-Ci(t)|<D,for i=1,2,.. and for all real times t in I.
 The clocks Ci are accurate to within the bound D.

CS3551- DISTRIBUTED COMPUTING Page 1

 BUILDERS ENGINEERING COLLEGE, KANGEYAM

7. What is internal synchronization?

And if the clocks C are synchronized with one another to known degree of accuracy, then
we can measure the interval between two events occurring at different computers by
appealing to their local clocks, even though they are not necessarily synchronized to an
external source of time. This is internal synchronization.
 For a synchronization bound D > 0 and for a source S of UTC times, |S(t)-C i(t) | < D ,
for all real times t in I.
 Clocks C agree with in the bound D.
8. Define NTP and its design aims.
Cristian’s method and the Berkeley algorithm are intended primarily for use within
intranets. The Network Time Protocol (NTP) [Mills1995] defines an architecture for a time
service and a protocol to distribute time information over the Internet.
NTP’s chief design aims and features are as follows:
 To provide a service enabling clients across the Internet to be synchronized accurately to
UTC:
 To provide a reliable service that can survive lengthy losses of connectivity:
 To enable clients to resynchronize sufficiently frequently to offset the rates of drift
found in most computers: To provide protection against interference with the time
service, whatever malicious or accidental.
9. What is strata?
The NTP service is provided by a network of servers located across the Internet. Primary
servers are connected directly to a time source such as a radio clock receiving UTC;
secondary servers are synchronized, ultimately, with primary servers. The servers are
connected in a logical hierarchy called a synchronization subnet whose levels are called
strata.
10. Enumerate the mode of synchronization in NTP servers.
 NTP servers synchronize with one another in one of three: multicast, procedure-call and
symmetric mode
 Multicast mode is intended for use on a high-speed LAN. One or more servers
periodically multicasts the time to the servers running in other computers connected by
the LAN, Which set their clocks assuming a small delay. This mode can achieve only
relatively low accuracies, but ones that nonetheless are considered sufficient for many
purposes.
 Procedure-call mode is similar to the operation of Cristian’s algorithm. In this mode,
one server accepts requests from other computers, which it processes by replying with
its timestamp (current clock reading). This mode is suitable when higher accuracies are
required than can be achieved with multicast, or where multicast is not supported in
hardware.
 In, symmetric mode is intended for use by the servers that supply time information in
LANs and by the higher levels of the synchronization subnet, where the highest
accuracies are to be achieved.

CS3551- DISTRIBUTED COMPUTING Page 2

 BUILDERS ENGINEERING COLLEGE, KANGEYAM

11. What is filter dispersion?

NTP servers apply a data filtering algorithm to successive pairs which estimates the offset o
and calculates the quality of this estimates as a statistical quantity called the filter
dispersion.
12. What is synchronization dispersion?
Peers with lower stratum numbers are more favoured than those in higher strata because
they are ‘closer’ to the primary time sources. Also, those with the lowest synchronization
dispersion are relatively favoured. This is the sum of the filter dispersions measured
between the server and the root of the synchronization subnet.
13. What is meant by HB relation?
 Lamport called the partial ordering obtained by generalizing these two relationships the
happened-before relation. It is also sometimes known as the relation of causal ordering
or potential causal ordering.
 We can define the happened-before relation, denoted -> by as follow:
HB1: If process pi:e->ie’ , then e->e’
HB2: For any message m, send (m) receive (m)
HB3: IF e, e’ and e” are events such that e->e’ then e->e”
14. What is logical clock?
 Lamport [1978] invented a simple mechanism by which the happened before
ordering can be captured numerically, called a logical clock.
 A Lamport logical clock is a monotonically increasing software counter, whose
value need bear no particular relationship to any physical clock.
 Each process p keeps its own logical clock, L , which it uses to apply so-called
Lamport timestamps to a events.
 We denote the timestamp of event e at pi by L (e) , and by L(e) we denote the
timestamp of event e at whatever process it occurred at.
15. Define Vector clock
Vector clocks for a system of N processes is an array of N integers
• Shortcoming of Lamport clocks:
L(e) < L(e') doesn't imply e → e'
• Vector clock: an array of N integers for a system of N processes
– Each process keeps its own vector clock Vi to timestamp local events
– Piggyback vector timestamps on messages
• Rules for updating vector clocks:
– Vi[i]] is the number of events that pi has timestamped
– Viji] ( j≠ i) is the number of events at pj that pi has been affected by
VC1: Initially, Vi[ j ] := 0 for pi, j=1.. N (N processes)
VC2: before pi timestamps an event, Vi[ i ] := Vi[ i ]+1
VC3: pi piggybacks t = Vi on every message it sends

CS3551- DISTRIBUTED COMPUTING Page 3

 BUILDERS ENGINEERING COLLEGE, KANGEYAM

VC4: when pi receives a timestamp t, it sets Vi[ j ] := max(Vi[ j ] , t[ j ]) for j=1..N (merge
operation)
16. What do you meant by distributed garbage
An object is considered to be garbage if there are no longer any reference to it anywhere in
the distributed system. The memory taken up by that object can be reclaimed once it is
known as to be garbage.
17. Define Global History
Let us return to our general system p of N processes pi(i=1,2,3,…..N)
Here a series of events occurs at each process, and that we may characterize the execution of
each process by its history
18. What is meant by cut?
Consider the events occurring at processes p1 and p2 shown in figure

19. Define Global state predicate

 A Global State Predicate is a function that maps from the set of global process states to True
or False.
 Detecting a condition like deadlock or termination requires evaluating a Global State
Predicate.
 A Global State Predicate is stable: once a system enters a state where it is true, such as
deadlock or termination, it remains true in all future states reachable from that state.
 However, when we monitor or debug an application, we are interested in non stable
predicates.

CS3551- DISTRIBUTED COMPUTING Page 4

 BUILDERS ENGINEERING COLLEGE, KANGEYAM

20. List the assumption considered in snapshot algorithm

– Neither channels nor processes fail
– Reliable communications ensure every message sent is received exactly once
– Channels are unidirectional
– Messages are received in FIFO order
– There is a path between any two processes
– Any process may initiate a global snapshot at any time
– Processes may continue to function normally during a snapshot
21. Define Failure detector.
A failure detector is a service that processes queries about whether a particular process has
failed .It is often implemented by an object local to each process that runs failure detection
algorithms in conjunction with its counterparts at the other processes.
22. List the properties of failure detector
A failure detector is not necessarily accurate. Most fails into the category of unreliable
failure detectors.
 A result of unsuspected
 A result of Suspected
23. Define critical section problem
The application – level protocol for executing a critical section is as follows
 enter() - enter critical section – block if necessary
 resurceAccesses() - access shared resources in critical section
 exit() - leave critical section other processes may now
enter.
24. What is meant by election
Election: choosing a unique process for a particular role is called an election
– All the processes agree on the unique choice
– For example, server in dist. mutex
25. List the famous mutual exclusion algorithms
 Center server algorithm
 Ring- Based algorithms
 Mutual Exclusion using multicast and Logical Clocks
 Maekawa’s Voting algorithms
 Mutual Exclusion algorithms comparison
26. What do you meant by bully algorithms and types of messages
Assumption: Each process knows which processes have higher identifiers, and that it can
communicate with all such processes
•Compare with ring-based election
– Processes can crash and be detected by timeouts

CS3551- DISTRIBUTED COMPUTING Page 5

 BUILDERS ENGINEERING COLLEGE, KANGEYAM

• synchronous
• timeout T = 2Ttransmitting (max transmission delay) + Tprocessing (max processing delay)
Three types of messages
a. Election: announce an election
b. Answer: in response to Election
c. Coordinator: announce the identity of the elected process
27. What are the types of ordering in multicast
Three types of message ordering
 FIFO (First-in, first-out) ordering: if a correct process delivers a message before
another, every correct process will deliver the first message before the other
 Casual ordering: any correct process that delivers the second message will deliver the
previous message first
 Total ordering: if a correct process delivers a message before another, any other correct
process that delivers the second message will deliver the first message first
28. Define Consensus
Consensus more precisely and relates it to three related Problems of agreement.For processes to
agree on a value (consensus) after one or more of the processes has proposed what that value
should be Covered topics: byzantine generals, interactive consistency, totally ordered
multicast
• The byzantine generals problem: a decision whether multiple armies should attack or retreat,
assuming that united action will be more successful than some attacking and some retreating
• Another example might be space ship controllers deciding whether to proceed or abort. Failure
handling during consensus is a key concern
29. What are the requirements of interactive consistency?
Three requirements of a consensus algorithm
 Termination: Eventually every correct process sets its decision variable
 Agreement: The decision value of all correct processes is the same: if pi and pj are
correct and have entered the decided state, then di=dj for all (i,j=1,2, …, N)
 Integrity: If the correct processes all proposed the same value, then any correct process
in the decided state has chosen that value
30. What are the requirements of consensus algorithms
The requirements of a consensus algorithms are that are following conditions should hold
for every execution of it:
 Termination
 Agreement
 Integrity

PART B (16 MARK QUESTIONS)

CS3551- DISTRIBUTED COMPUTING Page 6
 BUILDERS ENGINEERING COLLEGE, KANGEYAM

1. Explain Christian’s method for synchronizing clocks.

Cristian suggested the use of a time server, connected to a device that receives
signals from a source of UTC, to synchronize computers externally Clock synchronization
using a time server

Discussion of Cristian’s algorithm

Cristian’s method suffers from the problem associated with all services implemented
by a single server: that the single time server might fail and thus render synchronization
temporarily impossible. Cristian suggested, for this reason, that time should be provided by
a group of synchronized time servers, each with a receiver for UTC time signals. For
example, a client could multicast its request to all servers and use only the first reply
obtained.

2. Explain logical clocks in details

Lamport invented a simple mechanism by which the happenedbefore ordering can
be captured numerically, called a logical clock. 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. We denote the timestamp of event e at pi by L(e) , and
by L(e) we denote the timestamp of event e at whatever process it occurred at.

To capture the happened-before relation , processes update their logical clocks and
transmit the values of their logical clocks in messages as follows:
LC1: Li is incremented before each event is issued at process pi :
Li := Li + 1.
LC2: (a) When a process pi sends a message m, it piggybacks on m the value t = Li .
(b) On receiving (m, t), a process pj computes Lj := max(Lj, t) and then
applies LC1 before timestamping the event receive(m).

CS3551- DISTRIBUTED COMPUTING Page 7

 BUILDERS ENGINEERING COLLEGE, KANGEYAM

3. Explain distributed mutual exclusion algorithms in details

Distributed processes often need to coordinate their activities. If a collection of
processes share a resource or collection of resources, then often mutual exclusion is required
to prevent interference and ensure consistency when accessing the resources. This is the
critical section problem, familiar in the domain of operating systems. In a distributed
system, however, neither shared variables nor facilities supplied by a single local kernel can
be used to solve it, in general. The solution to distributed mutual exclusion: one that is based
solely on message passing.

Algorithms for mutual exclusion

The performance of algorithms for mutual exclusion according to the following criteria:
• the bandwidth consumed, which is proportional to the number of messages sent in each
entry and exit operation;
• the client delay incurred by a process at each entry and exit operation;
• the algorithm’s effect upon the throughput of the system. This is the rate at which the
collection of processes as a whole can access the critical section, given that some
communication is necessary between successive processes.

The central server algorithm

CS3551- DISTRIBUTED COMPUTING Page 8

 BUILDERS ENGINEERING COLLEGE, KANGEYAM

A ring-based algorithm

4. Explain the two phase commit protocol with an example

During the progress of a transaction, there is no communication between the
coordinator and the participants apart from the participants informing the coordinator when
they join the transaction. A client’s request to commit (or abort) a transaction is directed to
the coordinator. If the client requests abortTransaction, or if the transaction is aborted by
one of the participants, the coordinator informs all participants immediately. It is when the
client asks the coordinator to commit the transaction that the two-phase commit protocol
comes into use.

The two-phase commit protocol

Phase 1 (voting phase):
1. The coordinator sends a canCommit? request to each of the participants in the transaction.

2. When a participant receives a canCommit? request it replies with its vote (Yes or No) to
the coordinator. Before voting Yes, it prepares to commit by saving objects in permanent
storage. If the vote is No, the participant aborts immediately.

Phase 2 (completion according to outcome of vote):

3. The coordinator collects the votes (including its own).
(a) If there are no failures and all the votes are Yes, the coordinator decides to
commit the transaction and sends a doCommit request to each of the participants.
(b)Otherwise, the coordinator decides to abort the transaction and sends doAbort
requests to all participants that voted Yes.

4. Participants that voted Yes are waiting for a doCommit or doAbort request from the
coordinator. When a participant receives one of these messages it acts accordingly and, in
the case of commit, makes a haveCommitted call as
confirmation to the coordinator.

CS3551- DISTRIBUTED COMPUTING Page 9

 BUILDERS ENGINEERING COLLEGE, KANGEYAM

Communication in two-phase commit protocol

5. Explain ring based election algorithms

An algorithm for choosing a unique process to play a particular role is called an
election Algorithm
A ring-based election algorithm
Initially, every process is marked as a non-participant in an election. Any process
can begin an election. It proceeds by marking itself as a participant, placing its identifier in
an election message and sending it to its clockwise neighbor.

When a process receives an election message, it compares the identifier in the

message with its own. If the arrived identifier is greater, then it forwards the message to its
neighbour. If the arrived identifier is smaller and the receiver is not a participant, then it
substitutes its own identifier in the message and forwards it; but it does not forward the
message if it is already a participant. On forwarding an election message in any case, the
process marks itself as a participant.

The election was started by process 17. The highest process identifier encountered
so far is 24. Participant processes are shown in a darker tint.

CS3551- DISTRIBUTED COMPUTING Page 10

 BUILDERS ENGINEERING COLLEGE, KANGEYAM

6. Explain bully’s algorithms

The bully algorithm allows processes to crash during an election, although it
assumes that message delivery between processes is reliable. Unlike the ring-based
algorithm, this algorithm assumes that the system is synchronous: it uses timeouts to detect
a process failure.

The operation of the algorithm is shown in above figure. There are four processes, p1 –
p4 . Process p1 detects the failure of the coordinator p4 and announces an election (stage 1 in
the figure). On receiving an election message from p1 , processes p2 and p3 send answer
messages to p1 and begin their own elections; p3 sends an answer message to p2 , but p3
receives no answer message from the failed process p4 (stage 2). It therefore decides that it is
the coordinator. But before it can send out the coordinator message, it too fails (stage 3). When
p1 ’s timeout period T expires (which we assume occurs before p2 ’s timeout expires), it
deduces the absence of a coordinator message and begins another election. Eventually, p2 is
elected coordinator (stage 4).

CS3551- DISTRIBUTED COMPUTING Page 11

 BUILDERS ENGINEERING COLLEGE, KANGEYAM

7. Explain global states and consistent cuts in details

It is possible in principle to observe the succession of states of an individual process,
but the question of how to ascertain a global state of the system – the state of the collection
of processes – is much harder to address.

The essential problem is the absence of global time. If all processes had perfectly
synchronized clocks, then we could agree on a time at which each process would record its
state – the result would be an actual global state of the system. From the collection of
process states we could tell, for example, whether the processes were deadlocked. But we
cannot achieve perfect clock synchronization, so this method is not available to us.

Cuts

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

CS3551- DISTRIBUTED COMPUTING Page 12