DISTRIBUTED SYSTEM

(Madhu_Kulkarni)
Unit-1
Q1. Explain issues in designing Distributed system. OR Explain in detail issues in designing a
distributed operating system.

Ans - Issues in Designing Distributed Computing Environment A distributed operating system

must be designed to provide all the advantages of a distributed system to its users. That is, the
users should be able to view a distributed system as a virtual centralized system that is flexible,
efficient, reliable, secure, and easy to use. To meet this challenge, the designers of a distributed
operating system must deal with several design issues. Some of the key design issues are described
below.

i. Transparency - In a distributed system the resources are physically separated there is no common
clock among the multiple processors, delivery of messages is delayed, and messages could even
be lost [3]. Achieving complete transparency is a difficult task and requires that several different
aspects of transparency be supported by the distributed operating system. The eight forms of
transparency identified by the International Standards Organization's Reference Model for Open
Distributed Processing I. II. III. IV. Access transparency. Location transparency. Replication
transparency. Failure transparency. V. Migration transparency. VI. Concurrency transparency. VII.
Performance transparency. VIII. Scaling transparency

ii. Reliability - Distributed system, which manages multiple resources, must be designed properly
to increase the system's reliability by taking full advantage of this characteristic feature of a
distributed system. For higher reliability, the fault-handling mechanisms of a distributed operating
system must be designed properly to avoid faults, to tolerate faults, and to detect and recover from
faults. Commonly used methods for dealing with these issues are fault avoidance and fault
tolerance.

iii. Flexibility - Another important issue in the design of distributed operating systems is flexibility.
Flexibility is the most important feature for open distributed systems. The design of distributed
operating system should be flexible due to the following reasons: Ease of modification & Ease of
enhancement

iv. Performance - The overall performance should be better than or at least equal to that of running
the same application on a single processor system. Some design principles considered useful for
better performance are as follows: 1. Batch if possible. 2. Cache whenever possible. 3. Minimize
copying of data. 4. Minimize network traffic. 5. Take advantage of fine-grain parallelism for
multiprocessing.
 iv. Scalability - A distributed operating system should be designed to easily cope with the growth
of nodes and users in the system. That is, such growth should not cause serious disruption of
service or significant loss of performance to users. Some guiding principles for designing scalable
distributed systems are as follows: 1. Avoid centralized entities. 2. Avoid centralized algorithms.
vi. Heterogeneity - A heterogeneous distributed system consists of interconnected sets of
dissimilar hardware or software systems. Because of the diversity, designing heterogeneous
distributed systems is far more difficult than designing homogeneous distributed systems, in which
each system is based on the same, or closely related, hardware and software. However, as a
consequence of large scale, heterogeneity is often inevitable in distributed systems. Furthermore,
often heterogeneity is preferred by many users because heterogeneous distributed systems provide
the flexibility to their users of different computer platforms for different applications.

vii. Security - In order that the users can trust the system and rely on it, the various resources of a
computer system must be protected against destruction and unauthorized access. Enforcing
security in a distributed system is more difficult than in a centralized system because of the lack
of a single point of control and the use of insecure networks for data communication. Therefore,
as compared to a centralized system, enforcement of security in a distributed system has the
following additional requirements 1. It should be possible for the sender of a message to know that
the message was received by the intended receiver 2. It should be possible for the receiver of a
message to know that the message was sent by the genuine sender. 3. It should be possible for both
the sender and receiver of a message to be guaranteed that the contents of the message were not
changed while it was in transfer

Q2. What is distributed cloud computing? Describe distributed computing system models.

Ans - Distributed Cloud Computing is a computing model in which cloud services are distributed
across multiple physical locations (or data centers), but remain centrally managed. It allows data,
applications, and services to be hosted closer to the users or data sources, improving performance,
compliance, and availability.
In essence, it's an extension of cloud computing that leverages the principles of distributed
computing—using a network of interconnected computers (nodes) that work together to perform
tasks—to deliver cloud services across geographically distributed infrastructure.

Key Features:

• Geographic distribution of cloud infrastructure

• Centralized control with decentralized execution

• Low latency due to proximity to end-users

• Scalability and resilience

• Enables edge computing, hybrid cloud, and multi-cloud architectures
Distributed Computing System Models

A distributed computing system is a network of independent computers that work together as a

unified system. Different system models define how these components interact and collaborate.

1. Client-Server Model

• Clients request services, and servers provide them.

• Simple and widely used (e.g., web browsers and web servers).

• Limitations: Server can become a bottleneck.

2. Peer-to-Peer (P2P) Model

• Each node acts as both a client and a server.

• No central authority; nodes share resources directly.

• Examples: File sharing systems like BitTorrent.

• High scalability and fault tolerance.

3. Three-Tier Model (Multitier Architecture)

• Divides systems into three layers: presentation, logic, and data.

o Presentation Tier: User interface (e.g., web browser)

o Logic Tier: Business logic (e.g., application server)

o Data Tier: Database or storage

• Common in enterprise applications.

4. N-Tier Model

• Extends the three-tier model with additional layers for better scalability and modularity.

• Layers can include load balancers, caching layers, etc.

• Common in large-scale enterprise and cloud applications.

5. Service-Oriented Architecture (SOA)

• System components provide services to other components via well-defined interfaces

(e.g., REST, SOAP).

• Promotes reusability, interoperability, and modularity.

• Basis for microservices architecture.

6. Microservices Architecture
 • Application is broken down into small, independent services.

• Each service is loosely coupled and can be deployed independently.

• Popular in cloud-native and distributed systems.

7. Cluster Computing
• A group of linked computers (nodes) work together and appear as a single system.

• Often used for high-performance computing (HPC).

8. Grid Computing

• Combines geographically dispersed resources to achieve a common goal.

• Used in scientific research and large-scale computations.

9. Edge Computing

• A form of distributed computing where data processing happens near the data source or
user.

• Reduces latency and bandwidth usage.

Q3. What is Distributed operating system? Why Distributed operating system gaining popularity.
Ans - A Distributed Operating System (DOS) is an OS that manages a group of distinct, networked
computers and makes them appear to the users as a single, unified system. It is responsible for
managing hardware and software resources across all connected machines in a distributed system.

In simple terms, a distributed OS abstracts the complexity of multiple independent computers and
presents a single-system image, so users and applications interact with the distributed system as if
it were one computer.

Key Functions of a Distributed Operating System:

• Resource management across multiple nodes

• Process management (scheduling, execution, migration)

• File and data sharing among systems

• Communication management (message passing, synchronization)

• Fault tolerance and recovery

• Security and authentication

Why Distributed Operating Systems Are Gaining Popularity

Distributed OSs are becoming more popular due to several technological and practical trends:
1. Scalability

• Easily scale out by adding more machines or nodes to the system.

• Suitable for applications requiring large-scale computation and storage.

2. Performance
• Tasks can be parallelized and executed across multiple machines, improving processing
speed.

• Low latency for geographically distributed applications.

3. Fault Tolerance

• The system can continue working even if one or more nodes fail.
• Redundancy and replication improve reliability.

4. Resource Sharing

• Efficient use of hardware across multiple machines.

• Users and applications can access files, printers, and computation power from anywhere in
the network.

5. Transparency

• Provides transparency in:

o Access: Users don’t need to know where resources are located.

o Location: Appears as a local system regardless of physical location.

o Replication: Multiple copies of files/services are hidden from users.

o Concurrency: Multiple users can access resources without conflict.

6. Support for Modern Applications

• Ideal for cloud computing, IoT, edge computing, and big data processing.

• Used in services like distributed databases, content delivery networks, etc.

7. Cost-Effective
• Can use a network of commodity hardware instead of expensive centralized systems.

• Makes use of underutilized resources across a network.

Real-World Examples of Distributed Operating Systems:

• Google's Borg (precursor to Kubernetes)
 • Apache Hadoop YARN

• Microsoft Azure Fabric

• Amoeba, Mach, and MOSIX (research OSs)

Q4. What is different system model of distributed system?

Ans - Different System Models of Distributed Systems

In a distributed system, multiple independent computers communicate and coordinate with each
other to achieve a common goal. To design and understand these systems, different system models
are used. These models describe how components interact, how data is handled, and what
assumptions are made about communication and failures.

1. Architectural Models

These describe how components (like clients, servers, and middleware) are organized and interact.
a) Client-Server Model

• Clients request services; servers respond to requests.

• Common in web applications, databases, etc.

• Easy to implement, but server can become a bottleneck.

b) Peer-to-Peer (P2P) Model

• All nodes (peers) are equal and can act as both clients and servers.

• Decentralized and scalable.

• Examples: BitTorrent, blockchain networks.

c) Three-Tier / Multi-Tier Model

• Divides the system into layers:

o Presentation layer (UI)

o Application logic layer (server)

o Data layer (database)

• Improves scalability, maintainability.

d) Service-Oriented Architecture (SOA)
• Components provide services through standard interfaces.
 • Promotes loose coupling and reusability.

• Basis for microservices and cloud-native applications.

2. Fundamental Models
These focus on the underlying properties and assumptions of the system: interaction, failure,
and security.

a) Interaction Model
Describes communication between components.

• Synchronous:
o Known time limits on message delivery and execution.

o Easier to reason about, but unrealistic in many real-world systems.

• Asynchronous:

o No time guarantees on communication or execution.

o More flexible but complex.

b) Failure Model

Describes how systems behave in the presence of faults.

• Crash failures – Node stops working.

• Omission failures – Message lost.

• Timing failures – Delays beyond expected time.

• Byzantine failures – Arbitrary or malicious faults (worst-case).

c) Security Model
Deals with threats like:

• Interception (eavesdropping)

• Modification (data tampering)

• Impersonation (spoofing identities)

• Protection mechanisms: encryption, authentication, authorization, etc.

3. Data Models

Describe how data is distributed and accessed.

a) Replication Model

• Data is copied across multiple nodes.

• Improves reliability and performance.

• Needs synchronization to keep copies consistent.

b) Partitioning Model

• Data is split across nodes (sharding).

• Each node stores only part of the data.

• Reduces load on individual servers.

4. Concurrency Model
Focuses on how the system handles multiple operations at once.

• Deals with synchronization, mutual exclusion, and deadlock prevention.

• Critical for distributed databases, file systems, etc.

Summary Table:

Model Type Key Purpose Examples

Architectural Model Defines system structure and roles Client-Server, P2P, SOA

Interaction Model Describes communication assumptions Synchronous, Asynchronous

Failure Model Handles different types of faults Crash, Omission, Byzantine

Security Model Defines threat models and protection Encryption, Auth

Data Model Deals with data distribution Replication, Partitioning

Concurrency Model Manages simultaneous operations Locks, Transactions

 Unit-2
Q1. Explain group communication in detail.
Ans - The most elementary form of message-based interaction is one-to-one
communication (also known as point-to-point, or unicast communication) in which
a single-sender process sends a message to a single-receiver process. For
performance and ease of programming, several highly parallel distributed
applications require that a message-passing system should also provide group
communication facility. Depending on single or multiple senders and receivers, the
following three types of group communication are possible: One to many (single
sender and multiple receivers). Many to one (multiple senders and single receivers).
Many to many (multiple senders and multiple receivers). One-to-Many
Communication In this scheme, there are multiple receivers for a message sent by a
single sender. One-to-many scheme is also known as multicast communication. A
special case of multicast communication is broadcast communication, in which the
message is sent to all processors connected to a network. Many-to-One
Communication In this scheme, multiple senders send messages to a single receiver.
The single receiver may be selective or nonselective. A selective receiver specifies
a unique sender; a message exchange takes place only if that sender sends a message.
On the other hand, a nonselective receiver specifies a set of senders, and if any one
sender in the set sends a message to this receiver, a message exchange takes place.
An important issue related to the many-to-one communication scheme is no
determinism. It is not known in advance which member (or members) of the group
will have its information available first Many-to-Many Communication In this
scheme, multiple senders send messages to multiple receivers. An important issue
related to many-to-many communication scheme is that of ordered message delivery.
Ordered message delivery ensures, that all messages are delivered to all receivers in
an order acceptable to the application.
Q2. Explain desirable features of good message passing system detail.
Ans - Message Passing system is subsystem of Distributed System that provides a
set of message based IPC protocol and does so by hiding details of complex network
protocols and multiples heterogeneous platform from programmers. • * 2 Primitives:
Send & Receive.

Simplicity: Simple and Ease to use. Simple and Clear Semantics of IPC Protocols of
message passing makes it easier.
• Uniform Semantics: There are two types of communication : [Link] [Link]
Semantics of Remote should be as close as possible to local communication for ease
of use.
• Efficiency : It can be made efficient by reducing number of message exchange.
Avoiding cost of setting and terminating connections between the same pair.
Minimizing the cost of maintaining connections. Piggybacking.
• Reliability : • Distributed System is prone to node crashes or communication link
failure resulting into loss of data. • Handling of lost message • Duplicate messages,
capable of detecting and handling duplicates. • Generating and assigning appropriate
sequences
• Correctness : • Atomicity: Message to All of None. • Order Delivery: Message in
Order. • Survivability: Message delivery despite of partial failure.
• Flexibility : • User may choose types and level of reliability •
Synchronous/Asynchronous, Send/Receive Choice. • Security: • It must provide
secure end to end communication.
• Necessary Steps: • Authentication of receiver by sender. • Authentication of sender
by receiver. • Portability: • Two Aspects: • Message passing system should itself be
portable. • Applications written by using primitives of IPC Protocols of Message
Passing System should be Portable
Q3. Explain process addressing in IPC
Ans -

Q4. What is group communication? Explain in detail Message ordering techniques

(Absolute, consistent and casual ordering).
Ans - Absolute Ordering The absolute ordering semantics ensures that all messages
are delivered to all receiver processes in the exact order in which they were sent.
One method to implement this semantics is to use global timestamps as message
identifiers. That is, the system is assumed to have a clock at each machine and all
clocks are synchronized with each other, and when a sender sends a message, the
clock value (timestamp) is taken as the identifier of that message and the timestamp
is embedded in the message.
To implement absolute ordering semantics, the kernel of each receiver’s machines
saves all incoming messages meant for a receiver in a separate queue. A sliding-
window mechanism is used to periodically deliver the message from the queue to
the receiver. That is, a fixed time interval is selected as the window size, and
periodically all messages whose timestamp values fall within the current window
are delivered to the receiver. Messages whose timestamp values fall outside the
window are left in the queue because of the possibility that a tardy message having
a timestamp value lower than that of any of the messages in the queue might still
arrive. The window size must be properly chosen taking into consideration the
maximum possible time that may be required by a message to go from one machine
to any other machine in the network.
Consistent Ordering (Total Ordering) - Absolute-ordering semantics requires
globally synchronized clocks, which are not easy to implement. Moreover, absolute
ordering is not really what many applications need to function correctly. Therefore,
instead of supporting absolute ordering semantics, most systems support consistent-
ordering semantics (total order semantics). This semantics ensures that all messages
are delivered to all receiver processes in the same order. However, this order may be
different from the order in which messages were sent.
Causal Ordering - For some applications consistent-ordering semantics is not
necessary and even weaker semantics is acceptable. Therefore, an application can
have better performance if the message-passing system used supports a weaker
ordering semantics that is acceptable to the application. One such weaker ordering
semantics that is acceptable to many applications is the causal ordering semantics.
This semantics ensures that if the event of sending one message is causally related
to the event of sending another message, the two messages are delivered to all
receivers in the correct order. However, if two message sending events are not
causally related, the two messages may be delivered to the receivers in any order.
Two message-sending events are said to be causally related if they are correlated by
the happened-before relation.
Q5. What is multi-datagram messaging? Explain the failure handling technique in
IPC.
Ans - Almost all networks have an upper bound of data that can be transmitted at a
time. This size is known as maximum transfer unit (MTU). A message whose size is
greater than MTU has to be fragmented into multiples of the MTU, and then each
fragment has to be sent separately. Each packet is known as a datagram. Messages
larger than the MTU are sent in miltipackets, and are known as multidatagram
messages. A message data should be meaningful to the receiving process. This
implies that, ideally, the structure of program objects should be preserved while they
are being transmitted from the address space of the sending process to the address
space of the receiving process. However, even in homogenous systems, it is very
difficult to achieve this goal mainly because of two reasons: An absolute pointer
value loses its meaning when transferred from one process address space to another.
Different program objects occupy varying amount of storage space. To be
meaningful, a message must normally contain several types of program objects, such
as long integers, short integers, variable-length character strings, and so on. In
transferring program objects in their original form, they are first converted to a
stream form that is suitable for transmission and placed into a message buffer. The
process of reconstruction of program object from message data on the receiver side
is known as decoding of message data. One of the following two representations
may by used for the encoding and decoding of a message data: In tagged
representation the type of each program object along with its value is encoded in the
message. In untagged representation the message data only contains program object.
No information is included in the message data to specify the type of each program
object.
Failure Handling Mechanism - During interprocess communication partial failures
such as a node crash or communication link failure may lead to the following
problems: Loss of request message. This may happen either due to the failure of
communication link between the sender and receiver or because the receiver’s node
is down at the time the request message reaches there. Loss of response message.
This may happen either due to the failure of communication link between the sender
and receiver or because the sender’s node is down at the time the response message
reaches there. Unsuccessful execution of the request. This may happen due to the
receiver’s node crashing while the request is being processed.
 Four-message reliable IPC protocol for client-server communication between two
processes works as follows: The client sends a request message to the server. When
the request message is received at the server’s machine, the kernel of that machine
returns an acknowledgment message to the kernel of the client machine. If the
acknowledgment is not received within the timeout period, the kernel of the client
machine retransmits the request message. When the server finishes processing the
client’s request it returns a reply message (containing the result of processing) to the
client. When the reply is received at client machine, the kernel of that machine
returns an acknowledgment message to the kernel of the server machine. If the
acknowledgment message is not received within the timeout period, the kernel of
the server machine retransmits the reply message. In client-server communication,
the result of the processed request is sufficient acknowledgment that the request
message was received by the server. Based on this idea, a three-message reliable IPC
protocol for client-server communication between two processes works as follows:
The client sends a request message to the server. When the server finishes processing
the client’s request, it returns a reply message (containing the result of processing)
to the client. The client remains blocked until the reply is received. If the reply is not
received within the timeout period, the kernel of the client machine retransmits the
request message. When the reply message is received at the client’s machine, the
kernel of that machine returns an acknowledgment message to the kernel of the sever
machine. If the acknowledgment message is not received within the timeout period,
the kernel of the server machine retransmits the reply message.
A message-passing system may be designed to use the following two-message IPC
protocol for client-server communication between two processes: The client sends a
request message to the server and remains blocked until a reply is received from the
server. When the server finishes processing the client’s request, it returns a reply
message (containing the result of processing) to the client. If the reply is not received
within the timeout period, the kernel of the client machine retransmits the request
message.
Q6. What is inter process communication? How inter process communication is used
in distributed systems?
Ans - • Processes executing concurrently in the distributed system may be either
independent or cooperating processes.
• Reasons for providing an environment that allows process cooperation. 1)
Information Sharing Several users may be interested in the same piece of
information. 2) Computational Speed up Process can be divided into sub tasks to run
faster, speed up can be achieved if the computer has multiple processing elements.
3) Modularity Dividing the system functions into separate processes or threads. 4)
Convenience Even an individual user may work on many tasks at the same time.
Q7. Elaborate Issues in IPC by Message-Passing and Synchronization.
Ans –

IPC Synchronization
• The general synchronization and data exchange problems involve (at least) two
tasks, which we will call the “sender” and the “receiver”. (These tasks are often also
called “writer” and “reader”, or “producer” and “consumer”.) For synchronization,
“sender” and “receiver” want to make sure they are both in (or not in) specified parts
of their code at the same time. For data exchange, “sender” and “receiver” want to
make sure they can exchange data efficiently, without having to know too much of
each other), and according to several different policies, such as blocking/non-
blocking, or with/without data loss.
• Data exchange has a natural direction of flow, and, hence, the terminology “sender”
and “receiver” is appropriate. Synchronization is often without natural order or
direction of flow, and, hence, the terminology “sender” and “receiver” is less
appropriate in this context, and “(IPC) client” might be a more appropriate because
symmetric terminology. Anyway, the exact terminology doesn’t matter too much.
Unless we want to be more specific, we will use the generic system calls send() and
receive() to indicate the IPC primitives used by sender and receiver, respectively.
• IPC primitives can have different effects on task scheduling: • • Blocking. When
executing the send() part of the IPC, the sender task is blocked (i.e., non-available
for scheduling) until the receiver has accepted the IPC in a receive() call. And
similarly the other way around. If both the sender and the receiver block until both
of them are in their send() and receive() commands, the IPC is called synchronous.
(Other names are: rendez-vous, or handshake.) Synchronous IPC is the easiest to
design with, and is very similar to building hardware systems. • • Non-blocking
(asynchronous). Sender and receiver are not blocked in their IPC commands. This
means that there is incomplete synchronization: the sender doesn’t know when the
receiver will get its message, and the receiver cannot be sure the sender is still in the
same state as when it sent the message. • • Blocking with time out. The tasks wait in
their IPC commands for at most a specified maximum amount of time. • •
Conditional blocking. The tasks block in their IPC commands only if a certain
condition is fulfilled. Of course, blocking primitives should be used with care in real-
time sections of a software system.

Unit-3
Q1. What is Remote procedure call? Explain how transparency is achieved in RPC?
[Link] is RPC? Explain working of RPC in detail.
Q8. How transparency is achieved in RPC?
Ans - • A remote procedure call (RPC) is an inter-process communication that allows
a computer program to cause a procedure to execute in another address space
(commonly on another computer on a shared network) without the programmer
explicitly coding the details for this remote interaction. • It further aims at hiding
most of the intricacies of message passing and is idle for client-server application. •
RPC allows programs to call procedures located on other machines. But the
procedures ‘send’ and ‘receive’ do not conceal the communication which leads to
achieving access transparence in distributed systems. • Example: when process A
calls a procedure on B, the calling process on A is suspended and the execution of
the called procedure takes place. (PS: function, method, procedure difference, stub,
state process model definition) • Information can be transported in the form of
parameters and can come back in procedure result. No message passing is visible to
the programmer. As calling and called procedures exist on different machines, they
execute in different address spaces, the parameters and result should be identical and
if machines crash during communication, it causes problems.
TRANSPARENCY OF RPC • A major issue in the design of an RPC facility is its
transparency property. A transparent RPC mechanism is one in which local
procedures and remote procedures are (effectively) indistinguishable to
programmers. This requires the following two types of transparencies: 1. Syntactic
transparency means that a remote procedures call should have exactly the same
syntax as a local procedure call. 2. Semantic transparency means that the semantics
of a remote procedure call are identical to those of a local procedure call. • It is not
very difficult to achieve syntactic transparency of an RPC mechanism, and we have
seen that the semantics of remote procedure calls are also analogous to that of local
procedure calls for most parts :
1. The calling process is suspended until the called procedure returns. 2. The caller
can pass arguments to the called procedure (remote procedure). 3. The called
procedure (remote procedure) can return results to the caller.
• Unfortunately, achieving exactly the same semantics for remote procedure calls as
for local procedure calls is close to impossible. This is mainly because of the
following differences between remote procedure calls and local procedure calls.
1. Unlike local procedure calls, with remote procedure calls the called procedure is
executed in an address space that is disjoint from the calling program’s address
space. Due to this reason, the called (remote) procedure cannot have access to any
variables or data values in the calling program’s environment. Thus in the absence
of shared memory, it is meaningless to pass addresses in arguments, making call-by
reference pointers highly unattractive. Similarly, it is meaningless to pass argument
values containing pointer structures (e.g., linked lists), since pointers are normally
represented by memory addresses.
2. Remote procedure calls are more vulnerable to failure than local procedure calls,
since they involve two different processes and possibly a network and two different
computers. Therefore programs that make use of remote procedure calls must have
the capability of handling even those errors that cannot occur in local procedure
calls. The need for the ability to take care of the possibility of processor crashes and
communication problems of a network makes it even more difficult to obtain the
same semantics for remote procedure calls as for local procedure calls. 3. Remote
procedure calls consume much more time (100– 1000 times more) than local
procedure calls. This is mainly due to the involvement of a communication network
in RPCs. Therefore applications using RPCs must also have the capability to handle
the long delays that may possibly occur due to network congestion.
Q2. What is 1:M and M:1 group communication?
Ans - Importance of Group Communication in Distributed Systems
Group communication is critically important in distributed systems due to several
key reasons:
• Multiple nodes must collaborate and synchronize their actions. Group
communication helps them exchange information and stay updated.
• Different nodes can create data that needs to be shared. Group communication
helps quickly send this information to everyone involved, reducing delays and
keeping data consistent.
• Group communication protocols enhance reliability by allowing messages to
be replicated or acknowledged across multiple nodes. This ensures robust
communication, even during failures or network issues.
• As distributed systems expand, effective scaling is crucial. Group
communication mechanisms can manage more nodes and messages without
sacrificing performance, keeping the system efficient and responsive.
Types of Group Communication in a Distributed System
Below are the three types of group communication in distributed systems:
1. Unicast Communication
Unicast Communication
Unicast communication is the point-to-point transmission of data between two nodes
in a network. In the context of distributed systems:
• Unicast is when a sender sends a message to a specific recipient, using their
unique network address.
• Each message targets one recipient, creating a direct connection between the
sender and the receiver.
• You commonly see unicast in client-server setups, where a client makes
requests and receives responses, as well as in direct connections between
peers.
• This method makes good use of network resources, is easy to implement, and
keeps latency low because messages go straight to the right person.
• Unicast isn’t efficient for sending messages to many recipients at once, as it
requires separate messages for each one, leading to more work.
2. Multicast Communication
Multicast Communication
Multicast communication involves sending a single message from one sender to
multiple receivers simultaneously within a network. It is particularly useful in
distributed systems where broadcasting information to a group of nodes is necessary:
• Multicast lets a sender share a message with a specific group of people who
want it.
• This way, the sender can reach many people at once, which is more efficient
than sending separate messages.
• This approach is often used to send updates to subscribers or in collaborative
applications where real-time sharing of changes is needed.
• By sending data just once to a group, multicast saves bandwidth, simplifies
communication, and can easily handle a larger number of recipients.
• Managing group membership is necessary to ensure reliable message delivery,
and multicast can run into issues if there are network problems that affect
everyone in the group.
3. Broadcast Communication
Broadcast communication involves sending a message from one sender to all nodes
in the network, ensuring that every node receives the message:
Broadcast Communication
• Broadcast is when a sender sends a message to every node in the network
without targeting specific recipients.
• Messages are delivered to all nodes at once using a special address designed
for this purpose.
• It’s often used for network management tasks, like sending status updates, or
for emergency alerts that need to reach everyone quickly.
• Broadcast ensures that every node receives the message without needing to
specify who the recipients are, making it efficient for sharing information
widely.
• It can cause network congestion in larger networks and raises security
concerns since anyone on the network can access the broadcast message,
which might lead to unauthorized access.
Reliable Multicast Protocols for Group Communication
Messages sent from a sender to multiple recipients should be delivered reliably,
consistently, and in a specified order. Types of Reliable Multicast Protocols include:
• FIFO Ordering:
o Ensures that messages are delivered to all group members in the order
they were sent by the sender.
o Achieved by sequencing messages and delivering them sequentially to
maintain the correct order.
• Causal Ordering:
o Preserves the causal relationships between messages based on their
dependencies.
 o Ensures that messages are delivered in an order that respects the causal
dependencies observed by the sender.
• Total Order and Atomicity:
o Guarantees that all group members receive messages in the same global
order.
o Ensures that operations based on the multicast messages (like updates
to shared data) appear atomic or indivisible to all recipients.

Q 4. What is RPC model? Explain in detail complicated RPC.

Ans - • The following are the two types of RPCs as complicated : 1. RPCs involving
long-duration calls or large gaps between calls. 2. RPCs involving arguments and /
or results that are too large to fit in a signle datagram packet. • Different protocols
are used for handling these two types of complicated RPCs. • Acomplicated RPC
can refer to scenarios where the process involves more advanced or non-trivial
configurations and features. Here are some examples of complicated RPC scenarios:
1. Asynchronous RPCs • Many RPC systems use a synchronous communication
model, where the client waits for the server to respond before continuing. An
asynchronous RPC allows the client to send a request and continue executing other
tasks while waiting for the server's response. • This can be complicated because it
introduces the need to handle callbacks or promises, manage thread pools, and deal
with concurrency issues. 2. Bidirectional Streaming RPCs • A bidirectional
streaming RPC allows both the client and server to send a sequence of messages to
each other. Unlike simple request-response RPCs, both the client and the server can
continuously exchange data. • These can be complex to implement because they
require careful management of message streams, flow control, and error handling.
3. Nested RPCs or Chained RPCs • In some systems, a single RPC might involve
multiple sub-RPC calls, where the server calls other remote services as part of the
processing for the main request. • Nested or chained RPCs introduce complexity
because the failure or latency in any part of the chain can propagate errors or delays
through the entire process. 4. Distributed Transactions with RPC • Implementing
distributed transactions in a system using RPC requires ensuring that multiple
remote systems are in sync and that operations are either all committed or all rolled
back (ACID properties). • This is difficult because you have to handle things like
network partitions, retries, and error recovery in a distributed environment. 5. RPC
Security (Authentication and Authorization) • Securing RPCs is more complicated
when dealing with sensitive data. This may involve implementing encryption, token-
based authentication (like OAuth or JWT), and fine-grained authorization checks. •
Managing security across multiple services or nodes requires ensuring the integrity
of messages, protecting against man-in-the-middle attacks, and verifying the
identities of both clients and servers

Q5. What is light weight RPC? Explain in detail.

Ans - • Based on the size of the kernel, operating systems may be broadly classified
into two categories– monolithic– kernel operating systems and microkernel
operating systems. Monolithic– kernel operating systems have a large, monolithic
kernel that is insulated from user programs by simple hardware boundaries. • Onthe
other hand, in microkernel operating systems, a small kernel provides only primitive
operations and most of the services are provided by user-level servers. The servers
are usually implemented as processes and can be programmed separately. • Each
server forms a component of the operating system and usually has its own address
space. As compared to the monolithic– kernel approach, in this approach services
are provided less efficiently because the various components of the operating system
have to use some form of IPC to communicate with each other. • The advantages of
this approach include simplicity and flexibility. Due to modular structure,
microkernel operating systems are simple and easy to design, implement, and
maintain. • In the microkernel approach, when different components of the operating
system have their own address spaces, the address space of each component is said
to form a domain, and messages are used for all interdomain communication. In this
case, the communication traffic in operating systems are of two types:
1. Cross-domain, which involves communication between domains on the
same machine. • 2. Cross-machine, which involves communication
between domains located on separate machines. • The LRPC is a
communication facility designed and optimized for cross-domain
communications. • Although conventional RPC systems can be used for
both cross domain and cross machine communications. Bershad et al.
observed that the use of conventional RPC systems for crossdomain
communications, which dominate cross-machine communications,
incurs an unnecessarily high cost. • This cost leads system designers to
coalesce weakly related components of microkernel operating systems
into a single domain, trading safety and performance. Therefore, the
basic advantages of using the microkernel approach are not fully
exploited. Based on these observations, Bershad et al. designed the
LRPC facility for crossdomain communications, which has better
performance than conventional RPC systems. Nonetheless, LPRC is
safe and transparent and represents a viable communication alternative
for microkernel operating systems. • To achieve better performance
than conventional RPC systems, the four techniques described below
are used by LRPC. • Simple Control Transfer : Whenever possible,
LRPC uses a control transfer mechanism that is simpler than the used
in conventional RPC systems. • For example, it uses a special threads
scheduling mechanism, called handoff scheduling for direct context
switch from the client thread to the server thread of an LRPC. In this
mechanism, when a client calls a server’s procedure, it provides the
server with an argument stack and its own thread of execution. The call
causes a trap to the kernel. • The kernel validates the caller, creates a
call linkage, and dispatches the client’s thread directly to the server
domain, causing the server to start executing immediately. When the
called procedure completes, control and results return through the
kernel back to the point of the client’s call. • In contrast to this, is
conventional RPC implementations, context switching between the
client and server threads of an RPC is slow because the client thread
and the server thread are fixed in their own domains, signaling one
another at a rendezvous, and the critical domain transfer path. • On the
other hand, latency is reduced by reducing context switching overhead
by caching domains on idle processors. • This is basically a
generalization of the idea of decreasing operating system latency by
caching recently blocked threads on idle processors to reduce wake-up
latency. • Instead of threads, LRPC caches domains so that any thread
that needs to run in the context of an idle domain can do so quickly, not
 just the thread that ran there most recently. • It was found that LRPC
achieves a factor-of-three performance improvement over more
traditional approaches. Thus LRPC reduces the cost of cross-domain
communication to nearly the lower bound imposed by conventional
hardware.
Q6. Differentiate between stateful & stateless servers. Which servers are better for
fault recovery and why?
Ans - In networking, how interactions between clients and servers are managed
greatly affects system performance. There are two main types of protocols for this
purpose: stateless and stateful protocols. Stateless protocols do not maintain state
information, so a server does not need to retain information from prior requests. This
simplifies server design and optimizes resource utilization. In contrast, stateful
protocols maintain session information, allowing for more consistent interaction
between clients and servers. Understanding the characteristics and differences of
these protocols is crucial for properly designing network systems.
What is the Stateless Protocol?
Stateless Protocols are the type of network protocols in which the Client sends a
request to the server and the server responds back according to the current state. It
does not require the server to retain session information or status about each
communicating partner for multiple requests.
HTTP (Hypertext Transfer Protocol), UDP (User Datagram Protocol), and DNS
(Domain Name System) are examples of Stateless Protocols.
Salient Features of Stateless Protocols
• Stateless Protocol simplifies the design of the Server.
• The stateless protocol requires fewer resources because the system does not
need to keep track of the multiple link communications and the session details.
• In Stateless Protocol each information packet travels on its own without
reference to any other packet.
• Each communication in Stateless Protocol is discrete and unrelated to those
that precedes or follow.
What is Stateful Protocol?
In Stateful Protocol If client send a request to the server then it expects some kind
of response, if it does not get any response then it resend the request. FTP (File
Transfer Protocol), TCP, and Telnet are the example of Stateful Protocol.
Salient Features of Stateful Protocol
• Stateful Protocols provide better performance to the client by keeping track of
the connection information.
• Stateful Application require Backing storage.
• Stateful request are always dependent on the server-side state.
• TCP session follow stateful protocol because both systems maintain
information about the session itself during its life.
Comparisons Between Stateless and Stateful Protocol

Stateless Protocol Stateful Protocol

Stateless Protocol does not require the Stateful Protocol require server to
server to retain the server information or save the status and session
session details. information.

In Stateful protocol, there is tight

In Stateless Protocol, there is no tight
dependency between server and
dependency between server and client.
client

The Stateful protocol design makes

The Stateless protocol design simplify the
the design of server very complex
server design.
and heavy.

Stateless Protocols works better at the Stateful Protocol does not work
time of crash because there is no state that better at the time of crash because
Stateless Protocol Stateful Protocol

must be restored, a failed server can stateful server have to keep the
simply restart after a crash. information of the status and session
details of the internal states.

Stateless Protocols handle the transaction Stateful Protocols handle the

very quickly. transaction very slowly.

Stateless Protocols are easy to implement Stateful protocols are logically

in Internet. heavy to implement in Internet.

It is difficult and complex to scale

Scaling architecture is relatively easier.
architecture.

The requests are not dependent on the The requests are always dependent
server side and are self contained. on the server side.

To process different information at a time To process every request , the same

, different servers can be used. server must be utilized.

Example of Stateless Example of Stateful

are UDP , DNS , HTTP , etc. are FTP , Telnet , etc.

Q7. Briefly explain the external data representation and marshalling.

Ans - • Implementation of remote procedure calls involves the transfer of arguments
from the client process to the server process and the transfer of results from the server
process to the client process. These arguments and results are basically language-
level data structures (program objects), which are transferred in the form of message
data between the two computers involved in the call. The transfer of message data
between two computers requires encoding and decoding of the message data. For
RPC this operation is known as marshaling and basically involves the following
actions. 1. Taking the arguments (of a client process) or the result (of a server
process) that will form the message data to be set to the remote process. 2. Encoding
the message data of step 1 above on the sender’s computer. This encoding process
involves the conversion of program objects into a stream form that is suitable for
transmission and placing them into a message buffer. 3. Decoding of the message
data on the receiver’s computer. This decoding process involves the reconstruction
of program objects from the message data that was received in stream form. • In
order that encoding and decoding of an RPC message can be performed successfully,
the order and the representation method (tagged or untagged) used to marshal
arguments and results must be known to both the client and the server of the RPC.
This provides a degree of type safety between a client a server because the server
will not accept a call from a client until the client uses the same interface definition
as the server. Type safety is of particular importance to servers since it allows them
to survive against corrupt call requests. • The marshaling process must reflect the
structure of all types of program objects used in the concerned language. These
include primitive types, structured types, and user defined types. Marshaling
procedures may be classified into two groups : 1. Those provided as a part of the
RPC software. Normally marshaling procedures for scalar data types, together with
procedures to marshal compound types built from the scalar ones, fall in this group.
2. Those that are defined by the users of the RPC system. This group contains
marshaling procedures for user– defined data types and data types that include
pointers. For example, in Concurrent CLU, developed for use in the Cambridge
Distributed Computer System, for user-defined types, the type definition must
contain procedures for marshaling.
Q9. Explain some Communication RPC.
Ans - The RPC (Remote Procedure Call) architecture in distributed systems is
designed to enable communication between client and server components that reside
on different machines or nodes across a network. The architecture abstracts the
complexities of network communication and allows procedures or functions on one
system to be executed on another as if they were local. Here’s an overview of the
RPC architecture:
1. Client and Server Components
• Client: The client is the component that makes the RPC request. It invokes a
procedure or method on the remote server by calling a local stub, which then
handles the details of communication.
• Server: The server hosts the actual procedure or method that the client wants
to execute. It processes incoming RPC requests and sends back responses.
2. Stubs
• Client Stub: Acts as a proxy on the client side. It provides a local interface
for the client to call the remote procedure. The client stub is responsible for
marshalling (packing) the procedure arguments into a format suitable for
transmission and for sending the request to the server.
• Server Stub: On the server side, the server stub receives the request,
unmarshals (unpacks) the arguments, and invokes the actual procedure on the
server. It then marshals the result and sends it back to the client stub.
3. Marshalling and Unmarshalling
• Marshalling: The process of converting procedure arguments and return
values into a format that can be transmitted over the network. This typically
involves serializing the data into a byte stream.
• Unmarshalling: The reverse process of converting the received byte stream
back into the original data format that can be used by the receiving system.
4. Communication Layer
• Transport Protocol: RPC communication usually relies on a network
transport protocol, such as TCP or UDP, to handle the data transmission
between client and server. The transport protocol ensures that data packets are
reliably sent and received.
• Message Handling: This layer is responsible for managing network
messages, including routing, buffering, and handling errors.
5. RPC Framework
• Interface Definition Language (IDL): Used to define the interface for the
remote procedures. IDL specifies the procedures, their parameters, and return
types in a language-neutral way. This allows for cross-language
interoperability.
• RPC Protocol: Defines how the client and server communicate, including the
format of requests and responses, and how to handle errors and exceptions.
6. Error Handling and Fault Tolerance
• Timeouts and Retries: Mechanisms to handle network delays or failures by
retrying requests or handling timeouts gracefully.
• Exception Handling: RPC frameworks often include support for handling
remote exceptions and reporting errors back to the client.
7. Security
• Authentication and Authorization: Ensures that only authorized clients can
invoke remote procedures and that the data exchanged is secure.
• Encryption: Protects data in transit from being intercepted or tampered with
during transmission.

Unit-4
Q1. Explain the need of election algorithm. Q5. Explain Bully election algorithm
with suitable example. OR What are election algorithms? Explain Bully algorithm.
Is it more efficient than Ring algorithm?
Ans – ▪ Several distributed algorithms require that there be a coordinator process in
the entire system that performs some type of coordination activity needed for the
smooth running of other processes in the system. Two examples of such coordinator
processes encountered in this chapter are the coordinator in the centralized algorithm
for mutual exclusion and the central coordinator in the centralized deadlock
detection algorithm. • Since all other processes in the system have to interact with
the coordinator, they all must unanimously agree on who the coordinator is.
Furthermore, if the coordinator process fails due to the failure of the site on which it
is located, a new coordinator process must be elected to take up the of the failed
coordinator. • Election algorithms are meant for electing to take coordinator process
from among the currently running processes in such a mannerthat at any instance of
time there is a single coordinator for all processes in the system. • Election algorithm
are based on the following assumptions : • 1. Each process in the system has a unique
priority number. • 2. Whenever an election is held, the process having the highest
priority number among the currently active processes is elected as the coordinator. •
3. On recovery, a failed process can take appropriate actions to rejoin the set of active
processes.
Ring Election Algorithm -
• Itis based on the use of a ring as the name suggests. But this does not use a token.
Processes are physically ordered in such a way that every process knows its
successor. • When any process notices that the coordinator is no longer functioning,
it builds up an ELECTION message containing its own number and passes it along
the to its successor. If the successor is down, then sender skips that member along
the ring to the next working process. • At each step, the sender adds its own process
number to the list in the message effectively making itself a candidate to be elected
s the coordinator. At the end, the message gets back to the process that started it. •
That process identifies this event when it receives an incoming message containing
its own process number. Then the same message is changed as coordinator and is
circulated once again • Example: two process, Number 2 and Number 5 discover
together that the previous coordinator; Number 7 has crashed. Number 2 and
Number 5 will each build an election meaage and start circulating it along the ring.
Both the messages in the end will go to Number 2 and Number 5 and they will
convert the message into the coordinator with exactly the same number of members
and in the same order. When both such messages have gone around the ring, they
both will be discarded and the process of election will re-start.

Q2. What is logical clock? Why are logical clocks required in distributed systems?
Q6. What is logical clock concept? Explain implementation of logical clocks
with suitable diagram.
Ans - • Consider cases that involve assigning sequence numbers (“timestamps”) to
events upon which all cooperating processes can agree. What matters in these cases
is not the time of day at which the event occurred but that all processes can agree on
the order in which related events occur. Our interest is in getting event sequence
numbers that make sense system wide. These clocks are called logical clocks. •
Ifwecandothis across all events in the system, we have something called total
ordering: every event is assigned a unique timestamp (number), every such
timestamp is unique. • However, we don’t always need total ordering. If processes
do not interact then we don’t care when their events occur. If we only care about
assigning timestamps to related (causal) events then we have something known as
partial ordering. • Leslie Lamport developed a “happens before” notation to express
the relationship between events
Implementation of Logical Clock –
Q3. How Lamport does synchronizes logical clock? Which events are said to be
concurrent in Lamports timestamp?
Ans - Lamport’s Logical Clock was created by Leslie Lamport. It is a procedure to
determine the order of events occurring. It provides a basis for the more
advanced Vector Clock Algorithm. Due to the absence of a Global Clock in
a Distributed Operating System Lamport Logical Clock is needed.
Algorithm:
• Happened before relation(->): a -> b, means ‘a’ happened before ‘b’.
• Logical Clock: The criteria for the logical clocks are:
o [C1]: Ci (a) < Ci(b), [ Ci -> Logical Clock, If ‘a’ happened before ‘b’,
then time of ‘a’ will be less than ‘b’ in a particular process. ]
o [C2]: Ci(a) < Cj(b), [ Clock value of Ci(a) is less than Cj(b) ]
Reference:
 • Process: Pi
• Event: Eij, where i is the process in number and j: jth event in
the ith process.
• tm: vector time span for message m.
• Ci vector clock associated with process Pi, the jth element is Ci[j] and
contains Pi‘s latest value for the current time in process Pj.
• d: drift time, generally d is 1.
Implementation Rules[IR]:
• [IR1]: If a -> b [‘a’ happened before ‘b’ within the same process]
then, Ci(b) =Ci(a) + d
• [IR2]: Cj = max(Cj, tm + d) [If there’s more number of processes, then tm =
value of Ci(a), Cj = max value between Cj and tm + d]
Q4. Explain Absolute ordering and Casual ordering process with the help of example
for many to many communications.
Ans - Causal ordering of messages is one of the four semantics of multicast
communication namely unordered, totally ordered, causal, and sync-ordered
communication. Multicast communication methods vary according to the message’s
reliability guarantee and ordering guarantee. The causal ordering of messages
describes the causal relationship between a message send event and a message
receive event.
For example, if send(M1) -> send(M2) then every recipient of both the messages M1
and M2 must receive the message M1 before receiving the message M2. In
Distributed Systems the causal ordering of messages is not automatically
guaranteed.
Reasons that may lead to violation of causal ordering of messages
1. It may happen due to a transmission delay.
 2. Congestion in the network.
3. Failure of a system.
Protocols that are used to provide causal ordering of messages
1. Birman Schipher Stephenson Protocol
2. Schipher Eggli Sandoz Protocol
Both protocol’s algorithm requires that the messages be delivered reliably and both
prefer that there is no network partitioning between the systems. The general idea of
both protocols is to deliver a message to a process only if the message immediately
preceding it has been delivered to the process. Otherwise, the message is not
delivered immediately instead it is stored in a buffer memory until the message
preceding it has been delivered.
The ISIS System
The ISIS system was developed by Ken Birman and Joseph in 1987 and 1993. It is
a framework for reliable distributed communication which is achieved through the
help of process groups. It is a programming toolkit whose basic features consist of
process group management calls and ordered multicast primitives for
communicating with the process group members. ISIS provides multicast facilities
such as unordered multicast (FBCAST), casually ordered multicast (CBCAST),
totally ordered multicast (ABCAST), and sync-ordered multicast (GBCAST).
Q7. Explain implementation of sequential consistency model with suitable diagram.
Ans - The sequential consistency model is a memory consistency model where the
result of execution is the same as if the operations of all processors were
executed in some sequential order, and the operations of each individual
processor appear in this sequence in the order issued by that processor.
Implementation Overview:
1. Centralized Memory System:
o All processors communicate through a shared memory.
o A global clock or a controller ensures operations appear in a
consistent order.
 2. Maintaining Program Order:
o Each processor issues memory operations in program order (i.e., no
reordering within a processor).
o This order must be respected when seen by other processors.
3. Ensuring Global Order:
o All processors must agree on a single interleaving of operations from
all processors.
o This can be achieved using:
▪ Locks to control access to shared memory.
▪ Atomic operations to prevent race conditions.
▪ Memory fences/barriers to prevent reordering by compilers or
hardware.
Q8. What is Happened Before Relation? How does it help in event ordering? Explain
with help of an example.
Ans –
Q9. What is clock synchronization? Compare and contrast the various algorithms
used for clock synchronization in distributed system.
Ans - Clock synchronization in distributed systems refers to the process of ensuring
that all clocks across various nodes or computers in the system are set to the same
time or at least have their times closely aligned.
• In a distributed system, where multiple computers communicate and
collaborate over a network, each computer typically has its own local clock.
• However, due to factors such as hardware differences, network delays, and
clock drift (inaccuracies in timekeeping), these local clocks can drift apart
over time.
Importance of Clock Synchronization
Below are the importance of clock synchronization in distributed system:
 • Consistency and Coherence:
o Clock synchronization ensures that timestamps and time-based
decisions made across different nodes in the distributed system are
consistent and coherent. This is crucial for maintaining the correctness
of distributed algorithms and protocols.
• Event Ordering:
o Many distributed systems rely on the notion of event ordering based on
timestamps to ensure causality and maintain logical consistency. Clock
synchronization helps in correctly ordering events across distributed
nodes.
• Data Integrity and Conflict Resolution:
o In distributed databases and file systems, synchronized clocks help in
timestamping data operations accurately. This aids in conflict resolution
and maintaining data integrity, especially in scenarios involving
concurrent writes or updates.
• Fault Detection and Recovery:
o Synchronized clocks facilitate efficient fault detection and recovery
mechanisms in distributed systems. Timestamps can help identify the
sequence of events leading to a fault, aiding in debugging and recovery
processes.
• Security and Authentication:
o Timestamps generated by synchronized clocks are crucial for security
protocols, such as in cryptographic operations and digital signatures.
They provide a reliable basis for verifying the authenticity and temporal
validity of transactions and messages.
Q OR Explain the clock synchronization algorithms.
Ans - • Clock synchronization algorithms may be broadly classified as Centralized
and Distributed: • Centralized Algorithms In centralized clock synchronization
algorithms one node has a real-time receiver. This node, called the time server node
whose clock time is regarded as correct and used as the reference time. The goal of
these algorithms is to keep the clocks of all other nodes synchronized with the clock
time of the time server node. Depending on the role of the time server node,
centralized clock synchronization algorithms are again of two types– Passive Time
Sever and Active Time Server.
1. Passive Time Server Centralized Algorithm: In this method each node periodically
sends a message to the time server. When the time server receives the message, it
quickly responds with a message (“time = T”), where T is the current time in the
clock of the time server node. Assume that when the client node sends the “time =
?” message, its clock time is T0, and when it receives the “time = T” message, its
clock time is T1. Since T0 and T1 are measured using the same clock, in the absence
of any other information, the best estimate of the time required for the propagation
of the message “time = T” from the time server node to the client’s node is (T1-
T0)/2. Therefore, when the reply is received at the client’s node, its clock is
readjusted to T + (T1-T0)/2.
2. Active Time Server Centralized Algorithm: In this approach, the time server
periodically broadcasts its clock time (“time = T”). Based on this knowledge, it first
readjusts the clock values of the reply messages, It then takes a fault-tolerant average
of the clock values of all the computers (including its own). To take the fault tolerant
average, the time server chooses a subset of all clock values that do not differ from
one another by more than a specified amount, and the average is taken only for the
clock values in this subset. This approach eliminates readings from unreliable clocks
whose clock values could have a significant adverse effect if an ordinary average
was taken. The calculated average is the current time to which all the clocks should
be readjusted, The time server readjusts its own clock to this value, Instead of
sending the calculated current time back to other computers, the time server sends
the amount by which each individual computer’s clock requires adjustment, This can
be a positive or negative value and is calculated based on the knowledge the time
server has about the approximate time required for the propagation of a message
from each node to its own node. The other nodes receive the broadcast message and
use the clock time in the message for correcting their own clocks. Each node has a
priori knowledge of the approximate time (Ta) required for the propagation of the
message “time = T” from the time server node to its own node, Therefore, when a
broadcast message is received at a node, the node’s clock is readjusted to the time
T+Ta. A major drawback of this method is that it is not fault tolerant. If the broadcast
message reaches too late at a node due to some communication fault, the clock of
that node will be readjusted to an incorrect value. Another disadvantage of this
approach is that it requires broadcast facility to be supported by the network. 2.
Another active time server algorithm that overcomes the drawbacks of the above
algorithm is the Berkeley algorithm proposed by Gusella and Zatti for internal
synchronization of clocks of a group of computers running the Berkeley UNIX. In
this algorithm, the time server periodically sends a message (“time = ?”) to all the
computers in the group. On receiving this message, each computer sends back its
clock value to the time server. The time server has a priori knowledge of the
approximate time required for the propagation of a message from each node to its
own node.
• Distributed Algorithms We know that externally synchronized clocks are also
internally synchronized. That is, if each node’s clock is independently synchronized
with real time, all the clocks of the system remain mutually synchronized. Therefore,
a simple method for clock synchronization may be to equip each node of the system
with a real time receiver so that each node’s clock can be independently
synchronized with real time. Multiple real time clocks (one for each node) are
normally used for this purpose. Theoretically, internal synchronization of clocks is
not required in this approach. However, in practice, due to inherent inaccuracy of
real-time clocks, different real time clocks produce different time. Therefore,
internal synchronization is normally performed for better accuracy. One of the
following two approaches is used for internal synchronization in this case. 1. Global
Averaging Distributed Algorithms: In this approach, the clock process at each node
broadcasts its local clock time in the form of a special “resync” message when its
local time equals T0+iR for some integer I, where T0 is a fixed time in the past
agreed upon by all nodes and R is a system parameter that depends on such factors
as the total number of nodes in the system, the maximum allowable drift rate, and so
on. i.e. a resync message is broadcast from each node at the beginning of every fixed
length resynchronization interval. However, since the clocks of different nodes run
slightly different rates, these broadcasts will not happen simultaneously from all
nodes. After broadcasting the clock value, the clock process of a node waits for time
T, where T is a parameter to be determined by the algorithm. During this waiting
period, the clock process records the time, according to its own clock, when the
message was received. At the end of the waiting period, the clock process estimates
the skew of its clock with respect to each of the other nodes on the basis of the times
at which it received resync messages. It then computes a fault-tolerant average of
the next resynchronization interval. 2. The global averaging algorithms differ mainly
in the manner in which the fault-tolerant average of the estimated skews is
calculated. Two commonly used algorithms are: 1. The simplest algorithm is to take
the average of the estimated skews and use it as the correction for the local clock.
However, to limit the impact of faulty clocks on the average value, the estimated
skew with respect to each node is compared against a threshold, and skews greater
than the threshold are set to zero before computing the average of the estimated
skews. 2. In another algorithm, each node limits the impact of faulty clocks by first
discarding the m highest and m lowest estimated skews and then calculating the
average of the remaining skews, which is then used as the correction for the local
clock. The value of m is usually decided based on the total number of clocks (nodes)

Q10. Explain Distributed Algorithm for Mutual Exclusion in detail. OR Explain

Distributed Approach for providing Mutual Exclusion.
Ans - There are several resources in a system that must not be used simultaneously
by multiple processes if program operation is to be correct. For example, a file must
not be simultaneously updated by multiple processes. Similarly, use of unit record
peripherals such as tape drives or printers must be restricted to a single process at a
time. Therefore, exclusive access to such a shared resource by a process must be
ensured. This exclusiveness of access is called mutual exclusion between processes.
The sections of a program that need exclusive access to shared resources are referred
to as critical sections. For mutual exclusion, means are introduced to prevent
processes from executing concurrently within their associated critical sections.
An algorithm for implementing mutual exclusion must satisfy the following
requirements : Issues in Recovery from Deadlock : Two important issues in the
recovery action are selection of victims and use of transaction mechanism. These are
described below.
Selection of Victim(s): In any of the recovery approaches described above, deadlock
is broken by killing or rolling back one or more processes. These processes are called
victims. Notice that even in the operator intervention approach, recovery involves
killing one or more victims. Therefore, an important issue in any recovery procedure
is to select the victims. Selection of victim(s) is normally based on two major factors:
1. Minimization of recovery cost : This factor suggests that those processes should
be selected as victims whose termination / rollback will incur the minimum recovery
cost. Unfortunately, it is not possible to have a universal cost function, and therefore,
each system should determine its own cost function to select victims. Some of the
factors that may be considered for this purpose are (a) the priority of the processes;
(b) the nature of the processes, such as interactive or batch and possibility of return
with no ill effects; (c) the number and types of resources held by the processes; (d)
the length of service already received and the expected length of service further
needed by the processes; and (e) the total number of processes that will be affected.
2. Prevention of starvation : If a system only aims at minimization of recovery cost,
it may happen that the same process (probably because its priority is very low) is
repeatedly selected as a victim and may never complete. This situation known as
starvation, must be somehow prevented in any practical system. One approach to
handle this problem is to raise the priority of the process every time it is victimized.
Another approach is to include the number of times a process is victimized as a
parameter in the cost function.
Use of Transaction Mechanism: After a process is killed or rolled back for recovery
from deadlock, it has to be return. However, rerunning a process may not always be
safe, especially when the operations already performed by the process are non-
idempotent. For example, if a process has updated the amount of a bank account by
adding a certain amount to it, re-execution of the process will result in adding the
same amount once again, leaving the balance in the account in an incorrect state.
Therefore, the use of transaction mechanism (which ensures all or no effect)
becomes almost inevitable for most processes when the system chooses the method
of detection and recovery for handling deadlocks. However, notice that the
transaction mechanism need not be used for those processes that can be rerun with
no ill effects. For example, rerun of a compilation process has no ill effects because
all it does is read a source file and produce an object file.
Main Ans - • Mutualexclusion (often abbreviated to mutex) algorithms are used
in concurrent programming to avoid the simultaneous use of a commonresource,
such as a global variable, by pieces of computer code called critical sections. A
critical section is a piece of code in which a process or thread accesses a common
resource. The critical section by itself is not a mechanism or algorithm for mutual
exclusion. A program, process, or thread can have the critical section in it without
any mechanism or algorithm which implements mutual exclusion. • Centralized
Algorithm Here one process is selected as the coordinator of the system with the
authority of giving access to other process for entering the critical region. If any
process wants to enter the critical, it has to take the permission from the coordinator
process. This permission is taking by sending a REQUEST message

a) Process 1 asks the coordinator for permission to enter a critical region. Permission
is granted. b) Process 2 then asks permission to enter the same critical region. The
coordinator does not reply. c) When process 1 exits the critical region, it tells the
coordinator, when then replies to process 2. • the coordinator is not reply to process
2 when the critical region is occupied. Here, depending on the type of system, the
coordinator can also reply back to the process 2 that it is in queue. If the coordinator
doesn’t do so, then the waiting process 2 will be unable to distinguish between
‘permission denied” or a “dead” coordinator. • This type of system as a single point
of failure, if the coordinator fails, then the entire system crashes.
Q11. Explain Design and implementation issues of Distributed Shared Memory.
Ans - DSM is a mechanism that manages memory across multiple nodes and makes
inter-process communications transparent to end-users. To design information
shared memory we might deal with certain issues which are called issues.
Issues to Design and Implementation of DSM:
• Granularity
• Structure of shared memory space
• Memory coherence and access synchronization
• Data location and access
• Replacement strategy
• Thrashing
• Heterogeneity
1. Granularity: Granularity refers to the block size of a DSM system. Granularity
refers to the unit of sharing and the unit of data moving across the network when a
network block shortcoming then we can utilize the estimation of the block size as
words/phrases. The block size might be different for the various networks.
[Link] of shared memory space: Structure refers to the design of the shared
data in the memory. The structure of the shared memory space of a DSM system
is regularly dependent on the sort of applications that the DSM system is intended
to support.
3. Memory coherence and access synchronization: In the DSM system the shared
data things ought to be accessible by different nodes simultaneously in the network.
The fundamental issue in this system is data irregularity. The data irregularity might
be raised by the synchronous access. To solve this problem in the DSM system we
need to utilize some synchronization primitives, semaphores, event count, and so on.
4. Data location and access: To share the data in the DSM system it ought to be
possible to locate and retrieve the data as accessed by clients or processors.
Therefore the DSM system must implement some form of data block finding system
to serve network data to meet the requirement of the memory coherence semantics
being utilized.
5. Replacement strategy: In the local memory of the node is full, a cache miss at
the node implies not just a get of the gotten to information block from a remote node
but also a replacement. A data block of the local memory should be replaced by the
new data block. Accordingly, a position substitution methodology is additionally
vital in the design of a DSM system.
6. Thrashing: In a DSM system data blocks move between nodes on demand. In
this way on the off chance that 2 nodes compete for write access to the single data
item. The data relating data block might be moved to back and forth at such a high
rate that no genuine work can get gone. The DSM system should utilize an approach
to keep away from a situation generally known as thrashing.
7. Heterogeneity: The DSM system worked for homogeneous systems and need not
address the heterogeneity issue. In any case, assuming the underlined system
environment is heterogeneous, the DSM system should be designed to deal with
heterogeneous, so it works appropriately with machines having different
architectures.
Q12. Explain the Architecture of Distributed Shared Memory.
Ans - implements the distributed systems shared memory model in a distributed
system, that hasn’t any physically shared memory. Shared model provides a virtual
address area shared between any or all nodes. To beat the high forged of
communication in distributed system. DSM memo, model provides a virtual address
area shared between all nodes. systems move information to the placement of access.
Information moves between main memory and secondary memory (within a node)
and between main recollections of various nodes. Every Greek deity object is in hand
by a node. The initial owner is that the node that created the object. possession will
amendment as the object moves from node to node. Once a method accesses
information within the shared address space, the mapping manager maps shared
memory address to physical memory (local or remote).
DSM permits programs running on separate reasons to share information while not
the software engineer having to agitate causation message instead underlying
technology can send the messages to stay the DSM consistent between compute.
DSM permits programs that wont to treat constant laptop to be simply tailored to
control on separate reason. Programs access what seems to them to be traditional
memory. Hence, programs that Pine Tree State DSM square measure sometimes
shorter and easier to grasp than programs that use message passing. But, DSM isn’t
appropriate for all things. Client-server systems square measure typically less suited
to DSM, however, a server is also wont to assist in providing DSM practicality for
information shared between purchasers.
Architecture of Distributed Shared Memory (DSM) :
The architecture of a Distributed Shared Memory (DSM) system typically consists
of several key components that work together to provide the illusion of a shared
memory space across distributed nodes. the components of Architecture of
Distributed Shared Memory :
[Link]: Each node in the distributed system consists of one or more CPUs and a
memory unit. These nodes are connected via a high-speed communication network.
[Link] Mapping Manager Unit: The memory mapping manager routine in each
node is responsible for mapping the local memory onto the shared memory space.
This involves dividing the shared memory space into blocks and managing the
mapping of these blocks to the physical memory of the node.
Caching is employed to reduce operation latency. Each node uses its local memory
to cache portions of the shared memory space. The memory mapping manager treats
the local memory as a cache for the shared memory space, with memory blocks as
the basic unit of caching.
[Link] Network Unit: This unit facilitates communication between
nodes. When a process accesses data in the shared address space, the memory
mapping manager maps the shared memory address to physical memory. The
communication network unit handles the communication of data between nodes,
ensuring that data can be accessed remotely when necessary.
A layer of code, either implemented in the operating system kernel or as a runtime
routine, is responsible for managing the mapping between shared memory addresses
and physical memory locations.
Each node’s physical memory holds pages of the shared virtual address space. Some
pages are local to the node, while others are remote and stored in the memory of
other nodes.
In summary, the architecture of a DSM system includes nodes with CPUs and
memory, a memory mapping manager responsible for mapping local memory to the
shared memory space, caching mechanisms to reduce latency, a communication
network unit for inter-node communication, and a mapped layer to manage the
mapping between shared memory addresses and physical memory locations.
 Unit-5
Q1. Explain desirable features of global scheduling algorithm.
Ans - • No A Priori knowledge about the Processes: A good process scheduling
algorithm should operate with absolutely no a priori knowledge about the processes
to be executed. Scheduling algorithms that operate based on the information about
the characteristics and resource requirements of the processes normally pose an extra
burden upon the users who must specify this information while submitting their
processes for execution.
• Dynamic in Nature : It is intended that a good process scheduling algorithm should
be able to take care of the dynamically changing load (or status) of the various nodes
of the system. That is, process assignment decisions should be based on the current
load of the system and not on some fixed static policy. For this, sometimes it is also
recommended that the scheduling algorithm should possess the flexibility to migrate
a process more than once because the initial decision of placing a process on a
particular node may have to be changed after some time to adapt to the new system
load. This feature may also require that the system support preemptive process
migration facility in which a process can be migrated from one node to another
during the course of its execution.
• Quick Decision Making Capability : A good process scheduling algorithm must
make quick decisions about the assignment of processes to processors. This is an
extremely important aspect of the algorithms and makes many potential solutions
unsuitable. For example, an algorithm that models the system by a mathematical
program and solves it on line is unsuitable because it does not meet this requirement.
Heuristic methods requiring less computational effort while providing near optimal
results are therefore normally preferable to exhaustive (optimal) solution methods.
• Balanced System Performance and Scheduling Overhead: Several global
scheduling algorithms collect global state information and use this information in
making process assignment decisions. A common intuition is that greater amounts
of information describing global system state allow more intelligent process
assignment decisions to be made that have a positive affect on the system as a whole.
In a distributed environment, however, information regarding the state of the system
is typically gathered at a higher cost than in a centralized system. The general
observation is that, as overhead is increased in an attempt to obtain more information
regarding the global state of the system, the usefulness of that information is
decreased due to both the aging of the information being gathered and the low
scheduling frequency as a result of the cost of gathering and processing that
information. Hence algorithms that provide near optimal system performance with
a minimum of global state information gathering overhead are desirable.
• Stability : A scheduling algorithm is said to be unstable if it can enter a state in
which all the nodes of the system are spending all of their time migrating processes
without accomplishing any useful work in an attempt to properly schedule the
processes for better performance. This form of fruitless migration of processes is
known as processor thrashing. Processor thrashing can occur in situations where
each node of the system has the power of scheduling its own processes and
scheduling decisions either are made independently of decisions made by other
processors or are based on relatively old data de to transmission delay between
nodes. For example, it may happen that node 1 n and 2 n both observe that node 3 n
is idle and then both offload a portion of their work to node 3 n without being aware
of the offloading decision made by the other. Now if node 3 n becomes overloaded
due to the processes received fro both nodes 1 n and 2 n , then it may again start
transferring its processes to other nodes. This entire cycle may be repeated again and
again, resulting in an unstable state. This is certainly not desirable for a good
scheduling algorithm.
Q2. Explain different load estimation and process transfer policies used by load
balancing algorithms.
1. Ans - Load estimation policy : In this the load of the machine is calculated
based on the following criteria:
• Resource demands.
• Instruction mixes of processes.
• Architecture and speed of node CPU.
• Number of CPU cycles executed per cycle of real time.
1. Process transfer policy :
The mechanism of identifying load based on threshold of another machines is known
as process transfer policy.

State Transition Diagram.

1. Priority assignment policy : To migrate any process find the node which gives
highest priority to remote process.
• Selfish approach - It gives highest priority to local process.
• Althresihic - It gives higher priority to remote process.
• Intermediate - It gives higher priority to majority of processes current present
in system.
 1. Location transfer policy - This will select the node on which the process will
be migrated.
• Threshold - This will final load of destination and node which should be below
specific threshold value.
• Shortest - fFnd node with minimum load.
• Bidding - The destination node will start giving the offer and select the best
offer out of received one.
• Pairing - Pair overloaded machine with under loaded and normal with normal
and under loaded with under loaded.
1. Migration limiting policy - This will help to control thrashing.
• Controlled - This will limit the no. of nodes the process can be migration.
• uncontrolled - There would be no control on thrashing.
1. State information exchange policy - This will tell when to share the state.
• Periodic broadcast - The problem is cure if there is node change in state
broadcasting needs to be done.
• Broadcast with state change when state changes then only broadcast.
• On demand exchange.
• Exchange by policy.

Q3. Explain file caching schemes.

Ans - • File caching enhances I/O performance because previously read files are kept
in the main memory. Because the files are available locally, the network transfer is
zeroed when requests for these files are repeated. Performance improvement of the
file system is based on the locality of the file access pattern. Caching also helps in
reliability and scalability. • File caching is an important feature of distributed file
systems that helps to improve performance by reducing network traffic and
minimizing disk access. In a distributed file system, files are stored across multiple
servers or nodes, and file caching involves temporarily storing frequently accessed
files in memory or on local disks to reduce the need for network access or disk
access. • Here are some ways file caching is implemented in distributed file systems:
• Client-side caching: In this approach, the client machine stores a local copy of
frequently accessed files. When the file is requested, the client checks if the local
copy is up-to-date and, if so, uses it instead of requesting the file from the server.
This reduces network traffic and improves performance by reducing the need for
network access. • Server-side caching: In this approach, the server stores frequently
accessed files in memory or on local disks to reduce the need for disk access. When
a file is requested, the server checks if it is in the cache and, if so, returns it without
accessing the disk. This approach can also reduce network traffic by reducing the
need to transfer files over the network. • Distributed caching: In this approach, the
file cache is distributed across multiple servers or nodes. When a file is requested,
the system checks if it is in the cache and, if so, returns it from the nearest server.
This approach reduces network traffic by minimizing the need for data to be
transferred across the network. Advantages of file caching in distributed file systems
include • Improved performance: By reducing network traffic and minimizing disk
access, file caching can significantly improve the performance of distributed file
systems. • Reduced latency: File caching can reduce latency by allowing files to be
accessed more quickly without the need for network access or disk access. • Better
resource utilization: File caching allows frequently accessed files to be stored in
memory or on local disks, reducing the need for network or disk access and
improving resource utilization. Disadvantages of file caching in distributed file
systems include • Increased complexity: File caching can add complexity to
distributed file systems, requiring additional software and hardware to manage and
maintain the cache. • Cache consistency issues: Keeping the cache up-to-date can be
a challenge, and inconsistencies between the cache and the actual file system can
occur. • Increased memory usage: File caching requires additional memory resources
to store frequently accessed files, which can lead to increased • Memory usage on
client machines and servers: Overall, file caching is an important feature of
distributed file systems that can improve performance and reduce latency. However,
it also introduces some complexity and requires careful management to ensure cache
consistency and efficient resource utilization.
Q4. Write a short note on Replication and the types of it.
Ans - • Replication in distributed systems involves creating duplicate copies of data
or services across multiple nodes. This redundancy enhances system reliability,
availability, and performance by ensuring continuous access to resources despite
failures or increased demand. • Replication in distributed systems refers to the
process of creating and maintaining multiple copies (replicas) of data, resources, or
services across different nodes (computers or servers) within a network. The primary
goal of replication is to enhance system reliability, availability, and performance by
ensuring that data or services are accessible even if some nodes fail or become
unavailable. • Importance of Replication in Distributed Systems: Replication plays
a crucial role in distributed systems due to several important reasons: • Enhanced
Availability: • By replicating data or services across multiple nodes in a distributed
system, you ensure that even if some nodes fail or become unreachable, the system
as a whole remains available. • Users can still access data or services from other
healthy replicas, thereby improving overall system availability. • Improved
Reliability: • Replication increases reliability by reducing the likelihood of a single
point of failure. • If one replica fails, others can continue to serve requests,
maintaining system operations without interruption. • This redundancy ensures that
critical data or services are consistently accessible. • Reduced Latency: • Replicating
data closer to users or clients can reduce latency, or the delay in data transmission. •
This is particularly important in distributed systems serving users across different
geographic locations. • Users can access data or services from replicas located nearer
to them, improving response times and user experience. • Scalability: • Replication
supports scalability by distributing the workload across multiple nodes. • As
thedemand for resources or services increases, additional replicas can be deployed
to handle increased traffic or data processing requirements. • This elasticity ensures
that distributed systems can efficiently handle varying workloads. Types of
Replication in Distributed Systems • Primary-Backup Replication: Primary-Backup
Replication (also known as active-passive replication) involves designating one
primary replica (active) to handle all updates (writes), while one or more backup
replicas (passive) maintain copies of the data and synchronize with the primary. •
Multi-Primary Replication: Multi-Primary Replication allows multiple replicas to
accept updates independently. Each replica acts as both a client (accepting updates)
and a server (propagating updates to other replicas). • Chain Replication: Chain
Replication involves replicating data sequentially through a chain of nodes. Each
node in the chain forwards updates to the next node in the sequence, typically ending
with a return path to the primary node. • Distributed Replication: Distributed
Replication distributes data or services across multiple nodes in a less structured
manner compared to primary-backup or chain replication. Replicas can be located
geographically or logically distributed across the network. • Synchronous vs.
Asynchronous Replication: 1. Synchronous Replication: In synchronous replication,
updates are committed to all replicas before acknowledging the write operation to
the client. This ensures strong consistency but can introduce latency as the system
waits for all replicas to confirm the update. 2. Asynchronous Replication: In
asynchronous replication, updates are propagated to replicas after the write operation
is acknowledged to the client. This reduces latency but may lead to eventual
consistency issues if replicas fall behind or if there is a failure before updates are
fully propagated.
Q5. What are features of good global scheduling algorithm? Explain task assignment
approach in detail? OR Q7. Explain task assignment approach in detail.
Ans - • No A Priori knowledge about the Processes: A good process scheduling
algorithm should operate with absolutely no a priori knowledge about the processes
to be executed. Scheduling algorithms that operate based on the information about
the characteristics and resource requirements of the processes normally pose an extra
burden upon the users who must specify this information while submitting their
processes for execution.
• Dynamic in Nature : It is intended that a good process scheduling algorithm should
be able to take care of the dynamically changing load (or status) of the various nodes
of the system. That is, process assignment decisions should be based on the current
load of the system and not on some fixed static policy. For this, sometimes it is also
recommended that the scheduling algorithm should possess the flexibility to migrate
a process more than once because the initial decision of placing a process on a
particular node may have to be changed after some time to adapt to the new system
load. This feature may also require that the system support preemptive process
migration facility in which a process can be migrated from one node to another
during the course of its execution.
• Quick Decision Making Capability : A good process scheduling algorithm must
make quick decisions about the assignment of processes to processors. This is an
extremely important aspect of the algorithms and makes many potential solutions
unsuitable. For example, an algorithm that models the system by a mathematical
program and solves it on line is unsuitable because it does not meet this requirement.
Heuristic methods requiring less computational effort while providing near optimal
results are therefore normally preferable to exhaustive (optimal) solution methods.
• Balanced System Performance and Scheduling Overhead: Several global
scheduling algorithms collect global state information and use this information in
making process assignment decisions. A common intuition is that greater amounts
of information describing global system state allow more intelligent process
assignment decisions to be made that have a positive affect on the system as a whole.
In a distributed environment, however, information regarding the state of the system
is typically gathered at a higher cost than in a centralized system. The general
observation is that, as overhead is increased in an attempt to obtain more information
regarding the global state of the system, the usefulness of that information is
decreased due to both the aging of the information being gathered and the low
scheduling frequency as a result of the cost of gathering and processing that
information. Hence algorithms that provide near optimal system performance with
a minimum of global state information gathering overhead are desirable.
• Stability : A scheduling algorithm is said to be unstable if it can enter a state in
which all the nodes of the system are spending all of their time migrating processes
without accomplishing any useful work in an attempt to properly schedule the
processes for better performance. This form of fruitless migration of processes is
known as processor thrashing. Processor thrashing can occur in situations where
each node of the system has the power of scheduling its own processes and
scheduling decisions either are made independently of decisions made by other
processors or are based on relatively old data de to transmission delay between
nodes. For example, it may happen that node 1 n and 2 n both observe that node 3 n
is idle and then both offload a portion of their work to node 3 n without being aware
of the offloading decision made by the other. Now if node 3 n becomes overloaded
due to the processes received fro both nodes 1 n and 2 n , then it may again start
transferring its processes to other nodes. This entire cycle may be repeated again and
again, resulting in an unstable state. This is certainly not desirable for a good
scheduling algorithm.
 TASK ASSIGNMENT APPROACH • The Basic Idea: In this approach, a process
is considered to be composed of multiple tasks and the goal is to find an optimal
assignment policy for the tasks of an individual process. Typical assumptions found
in task assignment work are as follows :
• A process has already been split into pieces called tasks. This split occurs along
natural boundaries, so that each task will have integrity in itself and data transfers
among the tasks will be minimized.
• The amount of computation required by each task and the speed of each processor
are known
• The cost of processing each task on every node of the system is known. This cost
is usually derived based on the information about the speed of each processor and
the amount of computation required by each task.
• The Inter-pcrosses Communication (IPC) costs between every pair of tasks is
known. The IPC cost of considered zero (negligible) for tasks assigned to the same
node. They are usually estimated by an analysis of the static program of a process.
For example during the execution of the process, if two tasks communicate n times
and average time for each intertask communication is t, the intertask communication
cost for the two tasks is n*t .
• Other constraints, such as resource requirements of the tasks and the available
resources at each node, precedence relationships among the tasks, and so on, are also
known.
• Reassignment of the tasks is generally not possible. • With these assumptions, the
task assignment algorithms seek to assign the tasks of a process to the nodes of the
distributed system in such a manner so as to achieve goals such as the following. •
Minimization of IPC costs • Quick turnaround time for the complete process • A high
degree of parallelism • Efficient utilization of system resources in genera.
Q6. What is process management? Explain features of a good process migration.
Ans - What is Process Migration in Distributed Systems?
Process migration in distributed systems refers to the transfer of a process or its
execution state from one node (computer or server) to another within a network. This
can be done for various reasons such as balancing the load across nodes, optimizing
resource usage, improving system performance, or enhancing fault tolerance and
recovery.

Process Migration in Distributed System

• The process typically involves saving the current state of the process,
including its memory and execution context, transferring this state to the target
node, and then resuming execution on the new node.
• This capability is crucial in distributed systems where resources are spread
across multiple machines, enabling dynamic adjustments to changing
workloads and system conditions.
Why use Process Migration in Distributed System?
The reason to use process migration are:
• Dynamic Load Balancing: It permits processes to exploit less stacked nodes
by relocating from overloaded ones.
• Accessibility: Processes that inhibit defective nodes can be moved to other
perfect nodes.
• System Administration: Processes that inhabit a node if it is going through
system maintenance can be moved to different nodes.
 • The locality of data: Processes can exploit the region of information or other
extraordinary abilities of a specific node.
• Mobility: Processes can be relocated from a hand-operated device or
computer to an automatic server-based computer before the device gets
detached from the network.
• Recovery of faults: The component to stop, transport and resume a process
is actually valuable to support in recovering the fault in applications that are
based on transactions.
Key Concepts in Process Migration in Distributed System
Below are the key concepts in Process Migration:
• Process State: The complete status of a process, including its memory
contents, register values, program counter, and open file descriptors, that must
be captured and transferred during migration.
• Checkpointing: The act of saving the current state of a process to enable
resumption from that point after migration. Checkpoints can be taken
manually or automatically at regular intervals.
• Migration Overhead: The resources and time required to transfer the process
state from one node to another, including network bandwidth and
computational resources.
• Consistency: Ensuring that the process state remains consistent and valid
during and after migration, avoiding data corruption or inconsistencies.
• Transparency: Making the migration process seamless so that the process
and its users do not notice the transition, which involves hiding the
complexities of migration from the user.
• Fault Tolerance: Mechanisms to handle failures during migration, ensuring
that the process can be restarted or resumed without loss of critical data.
Types of Process Migration in Distributed Systems
Below are the types of process migration in distributed system:
• Static Migration:
 o Definition: The entire process is moved to a new node, and it starts
execution from the point where it was suspended.
o Pros: Simple to implement; the process state is saved and restored in
full.
o Cons: High overhead due to the transfer of the entire process state; not
ideal for processes with large memory footprints.
• Dynamic Migration:
o Definition: The process migrates while it is still running, often by
migrating its active state incrementally.
o Pros: Reduces downtime and allows for more fluid load balancing.
o Cons: More complex to manage; requires sophisticated mechanisms to
maintain consistency and manage intermediate states.
• Preemptive Migration:
o Definition: The process is temporarily paused, its state is saved, and it
is then moved to a new node where it resumes execution.
o Pros: Allows for planned migrations with minimal disruption.
o Cons: The process experiences a temporary halt, which may affect
performance.
• Non-Preemptive Migration:
o Definition: The process continues execution until it reaches a natural
stopping point or checkpoint before migration occurs.
o Pros: Avoids disruption during migration; can be more efficient for
long-running processes.
o Cons: Requires processes to reach suitable stopping points, which may
not always align with optimal migration times.
• Incremental Migration:
o Definition: The process state is migrated incrementally, in stages,
rather than all at once.
 o Pros: Can reduce the impact of migration on system performance and
allows for smoother transitions.
o Cons: More complex to implement; requires careful coordination to
maintain process state consistency.
Each type of process migration has its own advantages and trade-offs, and the choice
of method depends on factors like the system’s architecture, the nature of the
processes, and performance requirements.
Steps involved in Process Migration in Distributed Systems
The steps which are involved in migrating the process are:
• Step 1: Selection of Process for Migration
o Description: Identify the process that needs to be migrated based on
criteria such as load balancing, resource optimization, or fault
tolerance.
o Details: Evaluate the process’s resource usage, current load on the
source node, and potential benefits of migration.
• Step 2: Choosing the Destination Node
o Description: Select the appropriate destination node where the process
will be relocated.
o Details: Consider factors like available resources, compatibility,
network latency, and current load on potential destination nodes.
• Step 3: Migrating the Process to the Destination Node
o Description: Transfer the process from the source node to the
destination node.
o Details: This involves several subcategories of migration, each
addressing different aspects of the process’s state and execution.
Subcategories of Process Migration:
• Halting and Restarting the Process
 o Pause the process on the source node, transfer its state, and then restart
it on the destination node.
o The process is temporarily halted to save its state, which is then restored
and execution resumes on the new node.
• Transferring the Address Space
o Move the process’s address space, including memory and execution
context, from the source node to the destination node.
o The entire address space or significant portions are transferred to ensure
that the process can resume exactly where it left off.
• Message Forwarding
o Handle the communication of messages intended for the migrated
process.
o Forward any incoming messages or communication that was directed
to the process before migration to the new location.
• Managing Communication Between Collaborating Processes
o Coordinate and manage communication between the migrated process
and other processes it was interacting with before migration.
o Address potential isolation issues and ensure that inter-process
communication continues smoothly despite the migration.
Q8. Explain Load balancing approach in detail.
Ans – • A load balancer is a device that acts as a reverse proxy and distributes
network or application traffic across a number of servers. Load adjusting is the
approach to conveying load units (i.e., occupations/assignments) across the
organization which is associated with the distributed system. Load adjusting should
be possible by the load balancer. The load balancer is a framework that can deal with
the load and is utilized to disperse the assignments to the servers. The load balancers
allocates the primary undertaking to the main server and the second assignment to
the second server.
• Purpose of Load Balancing in Distributed Systems: Security: A load balancer
provide safety to your site with practically no progressions to your application.
Protect applications from emerging threats: The Web Application Firewall (WAF) in
the load balancer shields your site. Authenticate User Access: The load balancer can
demand a username and secret key prior to conceding admittance to your site to
safeguard against unapproved access. Protect against DDoS attacks: The load
balancer can distinguish and drop conveyed refusal of administration (DDoS) traffic
before it gets to your site. Performance: Load balancers can decrease the load on
your web servers and advance traffic for a superior client experience. SSL Offload:
Protecting traffic with SSL (Secure Sockets Layer) on the load balancer eliminates
the upward from web servers bringing about additional assets being accessible for
your web application. Traffic Compression: A load balancer can pack site traffic
giving your clients a vastly improved encounter with your site.
OR. [Link] are the Load Balancing transfer policies used for distributed systems?
Ans -

Q9. Explain load sharing approach in detail.

Ans – • Load sharing basically denotes the process of forwarding a router to share
the forwarding of traffic, in case of multiple paths if available in the routing table.
In case there are equal paths then the forwarding process will follow the load-sharing
algorithm. In load sharing systems, all nodes share the overall workload, and the
failure of some nodes increases the pressure of the rest of the nodes. The load sharing
approach ensures that no node is kept idle so that each node can share the load. • For
example, suppose there are two connections of servers of different bandwidths of
500Mbps and another 250Mbps. Let, there are 2 packets. Instead of sending the 2
packets to the same connection i.e. 500Mbps, 1 packet will be forwarded to the
500Mbps and another to the 250Mbps connection. Here the goal is not to use the
same amount of bandwidth in two connections but to share the load so that each
connection can sensibly deal with it without any traffic. • Why use Load Sharing? •
There are several issues in designing Load Balancing Algorithms. To overcome these
issues we use the load-sharing algorithm. The issues are: • Load assessment: It
decides how to evaluate the workload of a node in a distributed framework. • Process
transfer: It concludes whether the process can be executed locally or from a distance.
• Static information exchange: It decides how the framework loads information that
can be exchanged among the nodes. • Location policy: It decides the determination
of an objective hub during process migration. • Priority assignment: It decides the
priority of execution of a bunch of nearby and remote processes on a specific node.
• Migration restricting policy: It decides the absolute number of times a process can
move starting with one hub then onto the next.
OR [Link] is the load-sharing policies used for distributed systems?
Ans - • Load Sharing algorithm includes policies like location policy, process
transfer policy, state information exchange policy, load estimation policy, priority
assignment policy, and migration limiting policy. • 1. Location Policies: The location
policy concludes the sender node or the receiver node of a process that will be moved
inside the framework for load sharing. Depending upon the sort of node that steps
up and searches globally for a reasonable node for the process, the location strategies
are of the accompanying kinds: • Sender-inaugurated policy: Here the sender node
of the process has the priority to choose where the process has to be sent. The
actively loaded nodes search for lightly loaded nodes where the workload has to be
transferred to balance the pressure of traffic. Whenever a node’s load turns out to be
more than the threshold esteem, it either communicates a message or arbitrarily tests
different nodes individually to observe a lightly loaded node that can acknowledge
at least one of its processes. In the event that a reasonable receiver node isn’t found,
the node on which the process began should execute that process. • Receiver-
inaugurated policy: Here the receiver node of the process has the priority to choose
where to receive the process. In this policy, lightly loaded nodes search for actively
loaded nodes from which the execution of the process can be accepted. Whenever
the load on a node falls under threshold esteem, it communicates a text message to
all nodes or tests nodes individually to search for the actively loaded nodes. Some
vigorously loaded node might move one of its processes if such a transfer does not
reduce its load underneath the normal threshold. • 2. Process transfer Policy: All or
nothing approach is used in this policy. The threshold value of all the nodes is allotted
as 1. A node turns into a receiver node if there is no process and on the other side a
node becomes a sender node if it has more than 1 process. If the nodes turn idle then
they can’t accept a new process immediately and thus it misuses the processing
power To overcome this problem, transfer the process in such a node that is expected
to be idle in the future. Sometimes to ignore the processing power on the nodes, the
load-sharing algorithm turns the threshold value from 1 to 2. • 3. State Information
exchange Policy: In load-sharing calculation, it is not required for the nodes to
regularly exchange information, however, have to know the condition of different
nodes when it is either underloaded or overloaded. Thus two sub-policies are used
here: • Broadcast when the state changes: The nodes will broadcast the state
information request only when there is a change in state. In the sender-inaugurated
location policy, the state information request is only broadcasted by the node when
a node is overloaded. In the receiver-inaugurated location policy, the state
information request is only broadcasted by the node when a node is underloaded. •
Poll when the state changes: In a large network the polling operation is performed.
It arbitrarily asks different nodes for state information till it gets an appropriate one
or it reaches the test limit. • 4. Load Estimation Policy: Load-sharing algorithms aim
to keep away from nodes from being idle yet it is adequate to know whether a node
is occupied or idle. Consequently, these algorithms typically utilize the least
complex load estimation policy of counting the absolute number of processes on a
node. • 5. Priority Assignment Policy: It uses some rules to determine the priority of
a particular node. The rules are: • Selfish: Higher priority is provided to the local
process than the remote process. Thus, it has the worst response time performance
for the remote process and the best response time performance for the local process.
• Altruistic: Higher priority is provided to the remote process than the local process.
It has the best response time performance. • Intermediate: The number of local and
remote processes on a node decides the priority. At the point when the quantity of
local processes is more or equivalent to the number of remote processes then local
processes are given higher priority otherwise remote processes are given higher
priority than local processes. • 6. Migration limiting policy: This policy decides the
absolute number of times a process can move. One of the accompanying two
strategies might be utilized. • Uncontrolled: On arrival of a remote process at a node
is handled similarly as a process emerging at a node because of which any number
of times a process can migrate. • Controlled: A migration count parameter is used to
fix the limit of the migration of a process. Thus, a process can migrate a fixed number
of times here. This removes the instability of uncontrolled strategy.
Q10. How file management is performed in a distributed environment? Explain with
an example.
Ans – How File Management is Performed in a Distributed Environment
1. File Location Transparency
Users don't need to know where files are stored physically. The system
handles file locations and provides a unified namespace.
2. File Access Transparency
Accessing a remote file is as easy as accessing a local file, thanks to network
protocols and mounting mechanisms.
3. Concurrency Control
Multiple users can access the same file at once. DFSs manage locks or
versions to avoid conflicts.
4. Replication & Fault Tolerance
Files are replicated across multiple nodes to prevent data loss in case of
hardware failures.
5. Security & Permissions
The system ensures secure access through authentication and permission
checks, even across different machines.
6. Caching
Frequently accessed data is cached locally to reduce network traffic and
improve performance.
7. Consistency Models
Ensures that all users see a consistent view of the files (e.g., immediate,
eventual consistency).
Example: Google File System (GFS)
Scenario:
Google runs massive data processing tasks (e.g., indexing web pages). It needs a file
system that can handle:
• Very large files (GBs to TBs)
• Frequent reads and appends
• Fault tolerance
• Scalability
How It Works:
1. Architecture
o Master Server: Manages metadata (file names, locations,
permissions).
o Chunk Servers: Store file data in large chunks (e.g., 64MB each).
o Clients: Interact with the master to find file chunks and then talk
directly to chunk servers.
2. File Access Example
o A client wants to read [Link].
o It asks the master: “Where are the chunks of [Link]?”
o The master replies with locations of chunk servers.
o The client fetches chunks directly from chunk servers.
3. Replication
o Each chunk is replicated (usually 3 times) across different chunk
servers for reliability.
Q11. Explain Desirable Features of a good Distributed File Systems.
Ans - • A distributed file system (DFS) is a file system that is distributed on various
file servers and locations. It permits programs to access and store isolated data in the
same method as in the local files. It also permits the user to access files from any
system. It allows network users to share information and files in a regulated and
permitted manner. Although, the servers have complete control over the data and
provide users access control.
• DFS's primary goal is to enable users of physically distributed systems to share
resources and information through the Common File System (CFS). It is a file
system that runs as a part of the operating systems. Its configuration is a set of
workstations and mainframes that a LAN connects. The process of creating a
namespace in DFS is transparent to the clients.
• There are various features of the DFS. Some of them are as follows:
• Transparency: There are mainly four types of transparency. These are as follows:
1. Structure Transparency: The client does not need to be aware of the number or
location of file servers and storage devices. In structure transparency, multiple file
servers must be given to adaptability, dependability, and performance.
2. Naming Transparency: There should be no hint of the file's location in the file's
name. When the file is transferred form one node to other, the file name should not
be changed.
3. Access Transparency: Local and remote files must be accessible in the same
method. The file system must automatically locate the accessed file and deliver it to
the client.
4. Replication Transparency : When a file is copied across various nodes, the copies
files and their locations must be hidden from one node to the next.
• Scalability: The distributed system will inevitably increase over time when more
machines are added to the network, or two networks are linked together. A good DFS
must be designed to scale rapidly as the system's number of nodes and users
increases.
• Data Integrity: Many users usually share a file system. The file system needs to
secure the integrity of data saved in a transferred file. A concurrency control method
must correctly synchronize concurrent access requests from several users who are
competing for access to the same file. A file system commonly provides users with
atomic transactions that are high-level concurrency management systems for data
integrity.
• High Reliability: The risk of data loss must be limited as much as feasible in an
effective DFS. Users must not feel compelled to make backups of their files due to
the system's unreliability. Instead, a file system should back up key files so that they
may be restored if the originals are lost. As a high-reliability strategy, many file
systems use stable storage.
• High Availability: A DFS should be able to function in the case of a partial failure,
like a node failure, a storage device crash, and a link failure. • Ease of Use: The UI
of a file system in multiprogramming must be simple, and the commands in the file
must be minimal.
• Performance: The average time it takes to persuade a client is used to assess
performance. It must perform similarly to a centralized file system.
Q12. Explain File Accessing Models in Distributed System.
Ans - • Themannerin which aclient’s request to access a file is serviced depends on
the file accessing model used by the file system. The file accessing model of a
distributed file system mainly depends on two factors– the method used for
accessing remote files and the unit of data access. • Byte level transfer model : In
this model, file data transfers across the network between a client and a server take
place in units of bytes. This model provides maximum flexibility because it allows
storage and retrieval of an arbitrary sequential subrange of a file, specified by an
offset within a file, and a length. The main drawback of this model is the difficulty
in cache management due to the variable length data for different access requests.
The Cambridge File Server [Dion 1980, Mitchell and Dion 1982, Needham and
Herbert 1982] uses this model. • Record level transfer mode : The three file data
transfer models described above are commonly used with unstructured file models.
The record level transfer model is suitable for use with those file models in which
file contents are structured in the form of records. In this model, file data transfers
across the network between a client and a server take place in units of records. The
Research Storage System (RSS) [Gray 1978 Gray et al. 1981], which supports
complex access methods to structured and indexed files, uses the record level
transfer mode.
Q13. Explain File Models in Distributed System.
Ans - • Different file systems use different conceptual models of a file. The two most
commonly used criteria for file modeling are structure and modifiability. File models
based on these criteria are described below :
• Unstructured and Structured Files : According to the simplest model, a file is an
unstructured sequence of data. In this model, there is no substructure known to the
of each file of the file system appears to the file server as an uninterrupted sequence
of bytes. The operating system is not interested in the information stored in the files,
the interpretation of the meaning and structure of the data stored in the files are
entirely up to the application programs. UNIX and MS-DOS use this fie model.
• Another file model that is rarely used nowadays is the structured file model. In this
model, a file appears to the file server as an ordered sequence of records. Records of
different files of the same file system can be of different size. Therefore, many types
of files exist in a file system, each having different properties. In this model a record
is the smallest unit of file data that can be accessed, and the files system read or write
operations are carried out on a set of records.
• Structured files are again of two types– files with nonindexed records and files with
indexed records. In the former model, a file record is accessed by specifying its
position within the file, for example, the fifth record from the beginning of the file
or the second record from the end of the file. In the latter model, records have one
or more key fields and can be addressed by specifying the values of the key fields.
In file systems that allow indexed records, a file is maintained as a B-tree or other
suitable data structure or a hash able is used to locate records quickly.
• Most modern operating systems use the unstructured file model. This is mainly
because sharing of a file by different applications is easier with the unstructured file
model as compared to the structured file model. Since a file has no structure in the
unstructured model, different applications can interpret the contents of a file m
different ways
• In addition to data items, files also normally have attributes. A file’s attributes are
information describing that file. Each attribute has a name and a value. For example,
typical attributes of a file may contain information such as owner, size, access
permissions, date of creation, date of last modification, and date of last access. Users
can read and update some of the attribute values using the primitives provided by
the file system. Notice, however, that although a user may update the value of any
attribute, not all attributes are user modifiable. For example, a user may update the
value of the access permission attribute, but he or she cannot change the value of the
size or date of creation attributes. The types of attributes that can be associated with
a file are normally fixed by the file system. However, a file system may be designed
to provide the flexibility to create and manipulate user defined attributes in addition
to those supported by the file system.
• File attributes are normally maintained and used by the directory service because
they are subject to different access controls than the file they describe. Notice that
although file attributes are maintained and used by the directory service, they are
store with the corresponding file rather than with the file name in the directory. This
is mainly because many directory systems allow files to be referenced by more than
one name.
• Mutable and Immutable Files : According to the modifiability criteria, files are of
two types– mutable and immutable. Most existing operating systems use the mutable
file model. In this model, an update performed on a file overwrites on its old contents
to produce the new contents. That is, a file is represented as a single stored sequence
that is altered by each update operation.
• On the other hand, some more recent file systems, such as the Cedar File System
(CFS), use the immutable file model. In this model, a file cannot be modified once
it has been created except to be deleted. The file versioning approach is normally
used to implement file updates, and each file is represented by a history of immutable
versions. That is, rather than updating the same file, a new version of the file is
created each time a change is made to the file contents and the old version is retained
unchanged. In practice, the use of storage space may be reduced by keeping only a
record of the differences between the old and new versions rather than creating the
entire file once again.
• Gifford et al. emphasized that sharing only immutable files makes it easy to support
consistent sharing. Due to this feature, it is much easier to support file caching and
replication in a distributed system with the immutable file model because it
eliminates all the problems associated with keeping multiple copies of a file
consistent. However, due to the need to keep multiple versions of a file, the
immutable file mode, suffers from two potential problems– increased use of disk
space and increased disk allocation activity. Some mechanism is normally used to
prevent the desk space from filling instantaneously.
Q 14. Explain File Replication in Distributed System.
Ans - • Replication in distributed systems involves creating duplicate copies of data
or services across multiple nodes. This redundancy enhances system reliability,
availability, and performance by ensuring continuous access to resources despite
failures or increased demand. • Replication in distributed systems refers to the
process of creating and maintaining multiple copies (replicas) of data, resources, or
services across different nodes (computers or servers) within a network. The primary
goal of replication is to enhance system reliability, availability, and performance by
ensuring that data or services are accessible even if some nodes fail or become
unavailable. • Importance of Replication in Distributed Systems: Replication plays
a crucial role in distributed systems due to several important reasons: • Enhanced
Availability: • By replicating data or services across multiple nodes in a distributed
system, you ensure that even if some nodes fail or become unreachable, the system
as a whole remains available. • Users can still access data or services from other
healthy replicas, thereby improving overall system availability. • Improved
Reliability: • Replication increases reliability by reducing the likelihood of a single
point of failure. • If one replica fails, others can continue to serve requests,
maintaining system operations without interruption. • This redundancy ensures that
critical data or services are consistently accessible. • Reduced Latency: • Replicating
data closer to users or clients can reduce latency, or the delay in data transmission. •
This is particularly important in distributed systems serving users across different
geographic locations. • Users can access data or services from replicas located nearer
to them, improving response times and user experience. • Scalability: • Replication
supports scalability by distributing the workload across multiple nodes. • As
thedemand for resources or services increases, additional replicas can be deployed
to handle increased traffic or data processing requirements. • This elasticity ensures
that distributed systems can efficiently handle varying workloads.