Department of Computer Science and Engineering

AY 2023-2024 III Year V Sem. REHEARSAL

CS3551- DISTRIBUTED COMPUTING
KEY – ANSWER

PART - A

1.Define distributed system

Distributed System is a collection of autonomous computer systems that are physically separated but are connected by a
centralized computer network that is equipped with distributed system software. The autonomous computers will communicate
among each system by sharing resources and files and performing the tasks assigned to them.

2.Compare shared memory Vs distributed shared memory

Shared-memory systems are difficult to build but easy to use, and are ideal for laptops and desktops. Distributed-memory systems
are easier to build but harder to use, comprising many shared-memory computers each with their own operating system and their
own separate memory

3. Identify consistent snapshot.

A distributed snapshot algorithm captures a consistent global state of a distributed system. A global state can be described by a cut
that indicates the time at which each process “checkpoints” its local state and messages

4.Define timestamp

A timestamp is the current time of an event that a computer records. Through mechanisms, such as the Network Time Protocol, a
computer maintains accurate current time, calibrated to minute fractions of a second. Such precision makes it possible for
networked computers and applications to communicate effectively.

5. What is deadlock?

A Deadlock is a situation where a set of processes are blocked because each process is holding a resource and waiting for another
resource occupied by some other process. When this situation arises, it is known as Deadlock.

6.Define two design issues for Suzuki-kasami’s algorithm

Design issues:
a).Distinguishing outdated REQUEST messages from current REQUEST messages
b) Determining which site has an outstanding request for the CS.

7.Describe local check pointing?

A local checkpoint is a snapshot of the state of the process at a given instance and the event of recording the state of a process is
called local check pointing. All processes save their local states at certain instants of time. A local check point is a snapshot of the
state of the process at a given instance

8. Illustrate what is orphan message?

In the time since its last checkpoint, a process may have sent some messages. If it is rolled back and restarted from the point of its
last checkpoint, it may create orphan messages, i.e., messages whose receive events are recorded in the states of the destination
processes but the send events are lost.

9. Describe cloud service.

Cloud services are application and infrastructure resources that exist on the Internet. Third-party providers contract with
subscribers for these services, allowing customers to leverage powerful computing resources without having to purchase or
maintain hardware and software.
10. What is Azure? List some examples of Azure services
Azure is the only consistent hybrid cloud, delivers unparalleled developer productivity, provides comprehensive, multilayered
security, including the largest compliance coverage of any cloud provider, and you'll pay less for Azure as AWS is five times
more expensive than Azure for Windows Server and SQL Server.

PART-B

11.a.i. Explain characteristics of distributed systems.

Characteristics of Distributed Systems
Transparency
One of the essential characteristics of the distributed system, transparency, is the notion that the user interacts with a whole
quantity rather than a cluster of cooperating elements
Heterogeneity
Heterogeneity refers to the system's ability to operate on various hardware and software components. Middleware in the software
layer helps achieve heterogeneity.
Openness
Another important characteristic of Distributed system is openness. A distributed system's openness is the difficulty in extending
or improving an existing system.
Scalability
In terms of effectiveness, scalability is one of the significant characteristics of distributed systems. It refers to the ability of the
system to handle growth as the number of users increases.
Fault Tolerance
A distributed system is very likely to be prone to system failures. This is due to the fact that several computers have diverse-aged
hardware. The ability of a system to handle these failures is called fault tolerance. Concurrency
Concurrency is the system's capability to access and use shared resources. It means multiple actions are performed at the same
time.
Efficiency
Efficiency refers to the capability of the system to use its resources effectively to execute the given tasks. The system's design, the
workload handled by the system, and the hardware and software resources used are some critical factors affecting the system's
efficiency.

11.a.ii. List the features of distributed systems

Features of distributed file systems
 Transparency. Transparency is a security mechanism that
shields details of one file system from other file systems and
users. ...
 Performance. ...
 Scalability. ...
 High availability. ...
 Data integrity. ...
 High reliability. ...
 Security. ...
 User mobility.

11.b. Write a brief note on the key algorithmic challenges in distributed computing
There are also multiple challenges of distributed systems that determine the performance of the overall system.
Heterogeneity
Heterogeneity is one of the challenges of a distributed system that refers to differences in hardware, software, or network
configurations among nodes.
Scalability
Scalability is one of the challenges in distributed systems. As distributed systems grow in size and complexity, it becomes
increasingly difficult to maintain their performance and availability.
Openness
Openness in distributed systems refers to achieving a standard between different systems that use different standards, protocols,
and data formats. It is crucial to ensure that different systems can communicate and exchange data seamlessly without the need for
extensive manual intervention.
Transparency
Transparency refers to the level of abstraction present in the system to hide complex information from the user. It is essential to
ensure that failures are transparent to users and do not affect the overall system's performance. Systems with different hardware
and software configurations provide to be a challenge for Transparency. Security is also a concern to maintain transparency in
distributed systems.
Concurrency
Concurrency is the ability to process data parallelly on different nodes of the system. One of the primary challenges of
concurrency in distributed systems is the issue of race conditions.
Security
The distributed and heterogeneous nature of the distributed system makes security a major challenge for data processing systems.
The system must ensure confidentiality from unauthorized access as data is transmitted across multiple nodes.
Failure Handling
One of the primary challenges of failure handling in distributed systems is identifying and diagnosing failures as failure can occur
at any node. Logging mechanisms should be implemented to identify the failed nodes.

12.a.i. Explain happen-before relation with example

To synchronize logical clocks Lamport defined a relation called happens-before.
The Happen-Before relation can be observed directly in two situations.
1) If A & B is true. B are events in same process and A occurs before B, then A B is
also true.
2) If A is the event of msg being send by one process and B is the event of msg being
sent by another process then A. A msg cannot be received before it is sent, or even at
the same time it is sent, since it take a finite,(non-zero) amount of time to arrive.B The
Happen-Before is a transitive relation, so if A & C. C then A B
If 2 events, X & X. Y is not true but neither Y Y happens in different processes that do
not exchange message ,then X These events are said to be concurrent which simply
means that nothing can be said about when the event happened or which event happened first.
Using this method, there is a way to assign time to all events in distributed systems subjects to the following conditions, If a
happens before b in the same process, c(a)<c(b).< p="">. If a & b represent to sending and receiving of a message, respectively
c(a) < c(b). For all distinctive, event a & b ,c(a)= c(b). E.g. Totally-Ordered Multicasting.

12.a.ii. Explain global state of distributed systems.

Why Global State? •Distributed applications/services execute concurrently on multiple machines. • A Snapshot of the distributed
application, i.e. a global picture is useful ○ Checkpointing: can restart distributed application on failure ○ Garbage collection of
objects: objects at servers that don’t have any other objects (at any servers) with pointers to them ○ Deadlock detection: Useful in
database transaction systems
Global States of Consistent Cuts. The global state of a distributed system is a collection of the local states of the processes and the
channels. A global state computed along a consistent cut is correct The global state of a consistent cut comprises the local state of
each process at the time the cut event happens and the set of all messages sent but not yet received The snapshot problem consists
in designing an efficient protocol which yields only consistent cuts and to collect the local state information Messages crossing the
cut must be captured Chandy & Lamport presented an algorithm assuming that message transmission is FIFO

12.b. Explain the types of group communications used in distributed systems

Group Communication in distributed Systems
Types of Group Communication in a Distributed System:
 Broadcast Communication : When the host process tries to communicate with every process in a distributed system at
same time. Broadcast communication comes in handy when a common stream of information is to be delivered to each
and every process in most efficient manner possible. Since it does not require any processing whatsoever, communication
is very fast in comparison to other modes of communication. However, it does not support a large number of processes
and cannot treat a specific process individually.
 Multicast Communication : When the host process tries to communicate with a designated group of processes in a
distributed system at the same time. This technique is mainly used to find a way to address problem of a high
workload on host system and redundant information from process in system. Multitasking can significantly decrease
time taken for message handling.
 Unicast Communication : When the host process tries to communicate with a single process in a distributed system
at the same time. Although, same information may be passed to multiple processes. This works best for two processes
communicating as only it has to treat a specific process only. However, it leads to overheads as it has to find exact
process and then exchange information/data.

13.a. Outline Lamport’s algorithm with an example.

 Lamport’s Distributed Mutual Exclusion Algorithm is a permission based algorithm proposed by Lamport as an
illustration of his synchronization scheme for distributed systems. In permission based timestamp is used to order critical section
requests and to resolve any conflict between requests. In Lamport’s Algorithm critical section requests are executed in the
increasing order of timestamps i.e a request with smaller timestamp will be given permission to execute critical section first than a
request with larger timestamp. In this algorithm:
 Three type of messages ( REQUEST, REPLY and RELEASE) are used and communication channels are assumed to
follow FIFO order.
 A site send a REQUEST message to all other site to get their permission to
enter critical section.
 A site send a REPLY message to requesting site to give its permission to
enter the critical section.
 A site send a RELEASE message to all other site upon exiting the critical
section.
 Every site Si, keeps a queue to store critical section requests ordered by their
timestamps. request_queuei denotes the queue of site Si.
Algorithm:
 To enter Critical section:
 When a site Si wants to enter the critical section, it sends a request message Request(tsi, i) to all other sites and
places the request on request_queuei. Here, Tsi denotes the timestamp of Site Si
 When a site Sj receives the request message REQUEST(tsi, i) from site Si, it returns a timestamped REPLY
message to site Si and places the request of site Si on request_queuej
 To execute the critical section:
 A site Si can enter the critical section if it has received the message with timestamp larger than (tsi, i) from all
other sites and its own request is at the top of request_queuei

 To release the critical section:

 When a site Si exits the critical section, it removes its own request from the top of its request queue
and sends a timestamped RELEASE message to all other sites
 When a site Sj receives the timestamped RELEASE message from site Si, it removes the request of
Si from its request queue

13.b. Explain how deadlock detection can achieve in distributed systems? Provide various models to carry out the same
Deadlock detection in Distributed systems
In a distributed system deadlock can neither be prevented nor avoided as the system is so vast that it is impossible to do so.
Therefore, only deadlock detection can be implemented. There are three approaches to detect deadlocks in distributed systems.
They are as follows:
Centralized approach – In the centralized approach, there is only one responsible resource to detect deadlock. The advantage of
this approach is that it is simple and easy to implement, while the drawbacks include excessive workload at one node, single-point
failure which in turns makes the system less reliable.
Distributed approach – In the distributed approach different nodes work together to detect deadlocks. No single point failure as
the workload is equally divided among all nodes. The speed of deadlock detection also increases.
Hierarchical approach – . In this approach, some selected nodes or clusters of nodes are responsible for deadlock detection and
these selected nodes are controlled by a single node.
There are three strategies for handling deadlocks:

Deadlock prevention:This is achieved either by having a process acquire all the needed resources simultaneously before it
begins executing or by preempting a process which holds the needed resource. Deadlock avoidance: A resource is granted to a
process if the resulting global system state is safe. This is impractical in distributed systems. Deadlock detection: This requires
examination of the status of process-resource interactions for presence of cyclic wait. Deadlock detection in distributed systems
seems to be the best approach to handle deadlocks in distributed systems.

14.a.i. Summarize the Koo–Toueg coordinated check pointing algorithm

Koo-Toueg coordinated checkpointing algorithm • A coordinated checkpointing and recovery technique that takes a consistent set
of check pointing and avoids domino effect and live lock problems during the recovery • Includes 2 parts: the checkpointing
algorithm and the recovery algorithm. Checkpointing algorithm – Assumptions: FIFO channel, end-to-end protocols,
communication failures do not partition the network, single process initiation, no process fails during the execution of the
algorithm – Two kinds of checkpoints: permanent and tentative • Permanent checkpoint: local checkpoint, part of a consistent
 global checkpoint • Tentative checkpoint: temporary checkpoint, become permanent checkpoint when the algorithm terminates
successfully
The initiating process takes a tentative checkpoint and requests all other processes to take tentative checkpoints. Every process
can not send messages after taking tentative checkpoint. All processes will finally have the single same decision: do or discard •
All processes will receive the final decision from initiating process and act accordingly – Correctness: for 2 reasons • Either all or
none of the processes take permanent checkpoint. No process sends message after taking permanent checkpoint – Optimization:
maybe not all of the processes need to take checkpoints (if not change since the last checkpoint)
Correctness: resume from a consistent state. Optimization: may not to recover all, since some of the processes did not change
anything

14.a.ii. Explain the rollback recovery algorithm

Rollback-recovery from a consistent set of checkpoints appears deceptively simple. The following scheme seems to work:
Whenever a process rolls back to its checkpoint, it notifies all other processes to also roll back to their respec- tive checkpoints. It
then installs its checkpointed state and resumes execution.
Checkpoint based rollback recovery techniques can be classified into three categories: uncoordinated checkpointing, coordinated
checkpointing and communication induced check pointing. Uncoordinated checkpointing allows each process the maximum
autonomy in deciding when to take checkpoints.

14.b. Give byzantine agreement tree algorithm and illustrate with an example
Byzantine Fault Tolerance(BFT) is the feature of a distributed network to reach consensus(agreement on the same value) even
when some of the nodes in the network fail to respond or respond with incorrect information. The objective of a BFT mechanism
is to safeguard against the system failures by employing collective decision making(both – correct and faulty nodes) which aims
to reduce to influence of the faulty nodes. BFT is derived from Byzantine Generals’ Problem.
A practical Byzantine Fault Tolerant system can function on the condition that the maximum number of malicious nodes must
not be greater than or equal to one-third of all the nodes in the system. As the number of nodes increase, the system becomes
more secure.
BFT consensus rounds are broken into 4 phases(refer with the image below):
 The client sends a request to the primary(leader) node.
 The primary(leader) node broadcasts the request to the all the secondary(backup) nodes.
 The nodes(primary and secondaries) perform the service requested and then send back a reply to the client.
 The request is served successfully when the client receives ‘m+1’ replies from different nodes in the network with the same
result, where m is the maximum number of faulty nodes allowed.

15.a.i. What is cloud computing? Explain advantages and disadvantages of cloud computing
Cloud computing is the delivery of different services through the Internet, including data storage, servers, databases, networking,
and software. Cloud storage has grown increasingly popular among individuals who need larger storage space and for businesses
seeking an efficient off-site data back-up solution
Pros: Disaster Recovery (DR), Access your data anywhere, Low cost, Scalability, Security
Cons: Lack of total control, Difficult to migrate, Requires Internet, Security and privacy have been an issue. Fixed contracts can
be a problem

15.a.ii. Define virtualization. Explain full-virtualization and para-virtualization

Virtualization is technology that you can use to create virtual representations of servers, storage, networks, and other physical
machines. Virtual software mimics the functions of physical hardware to run multiple virtual machines simultaneously on a single
physical machine.
In Full virtualization, virtual machines permit the execution of the instructions with the running of unmodified OS in an entirely
isolated way. Full Virtualization uses binary translation and a direct approach as a technique for operations
In Paravirtualization, a virtual machine does not implement full isolation of OS but rather provides a different API which is
utilized when OS is subjected to alteration. While the Paravirtualization is more secure than the Full Virtualization.

15.B. Discuss in detail about differences between IaaS, PaaS and SaaS

Parameter SaaS PaaS IaaS

Stands for Software as a service. Platform as a service. Infrastructure as a service.
Used by The end users use it. Developers use PAAS. Network architects use it.
Access SAAS gives access to the end user. PAAS gives access to the runtime It provides access to the
environment for deployment and resources like virtual machines
development tools and virtual storage.
 Parameter SaaS PaaS IaaS
Model It is a service model in cloud It is a cloud computing service model IaaS is a service model that
computing that hosts software. that delivers tools that are used for the provides virtualized computing
development of applications. resources over the internet.
Technical No need for technical knowledge. Some knowledge is required for basic It requires technical writing.
understanding setup.
Control is given to Nothing Data of Application OS, Runtime, Middleware, etc
developers
Abstraction Complete abstraction Abstraction of the underlying Only for underlying hardware
hardware and software resources. resources
Operational Cost Minimal Lower Highest
Portability No portability Lower Best
Risk of Vendor Highest Medium Lowest
Interlock
Examples of Google Workspace, Salesforce, Windows Azure, Force.com, Google AWS, Google Compute Engine,
Cloud services Dropbox, CISCO, MS Office Web, App Engine, OpenShift, Heroku, etc. Rackspace, Digital Ocean,
etc. VCloud Express, Sun, etc

16.a. Show that the Ricart-Agarwala algorithm the critical section is accessed in increasing order of timestamp.
Ricart–Agrawala algorithm is an algorithm for mutual exclusion in a distributed system proposed by Glenn Ricart and Ashok
Agrawala. This algorithm is an extension and optimization of Lamport’s Distributed Mutual Exclusion Algorithm. Like Lamport’s
Algorithm, it also follows permission-based approach to ensure mutual exclusion. In this algorithm:
 Two type of messages ( REQUEST and REPLY) are used and communication channels are assumed to follow FIFO
order.
 A site send a REQUEST message to all other site to get their permission to enter the critical section.
 A site send a REPLY message to another site to give its permission to enter the critical section.
 A timestamp is given to each critical section request using Lamport’s logical clock.
 Timestamp is used to determine priority of critical section requests. Smaller timestamp gets high priority over larger
timestamp. The execution of critical section request is always in the order of their timestamp.
Algorithm:
 To enter Critical section:
 When a site Si wants to enter the critical section, it send a timestamped REQUEST message to all other sites.
 When a site Sj receives a REQUEST message from site Si, It sends a REPLY message to site Si if and only if
 Site Sj is neither requesting nor currently executing the critical section.
 In case Site Sj is requesting, the timestamp of Site Si‘s request is smaller than its own request.
 To execute the critical section:
 Site Si enters the critical section if it has received the REPLY message from all other sites.
 To release the critical section:
 Upon exiting site Si sends REPLY message to all the deferred requests.
16.b. Discuss the design issues and challenges in distributed systems from a system perspective
Design issues of the distributed system –
1. Heterogeneity: Heterogeneity is applied to the network, computer hardware, operating system, and implementation of
different developers. A key component of the heterogeneous distributed system client-server environment is middleware.
Middleware is a set of services that enables applications and end-user to interact with each other across a heterogeneous
distributed system.
2. Openness: The openness of the distributed system is determined primarily by the degree to which new resource-sharing
services can be made available to the users.
3. Scalability: The scalability of the system should remain efficient even with a significant increase in the number of users
and resources connected.
4. Security: The security of an information system has three components Confidentially, integrity, and availability.
Encryption protects shared resources and keeps sensitive information secrets when transmitted.
6. Failure Handling: When some faults occur in hardware and the software program, it may produce incorrect results or
they may stop before they have completed the intended computation so corrective measures should to implemented to
handle this case.
7. Concurrency: There is a possibility that several clients will attempt to access a shared resource at the same time.
Multiple users make requests on the same resources, i.e. read, write, and update. Each resource must be safe in a
concurrent environment
8. Transparency: Transparency ensures that the distributed system should be perceived as a single entity by the users or
the application programmers rather than a collection of autonomous systems, which is cooperating