Unit -4

1.Demonstrate the Distributed File Systems requirements?

DISTRIBUTED FILE SYSTEMS A file system is responsible for the organization, storage, retrieval,
naming, sharing, and protection of files. File systems provide directory services, which convert a file
name (possibly a hierarchical one) into an internal identifier (e.g. inode, FAT index). They contain a
representation of the file data itself and methods for accessing it (read/write). The file system is
responsible for controlling access to the data and for performing low-level operations such as
buffering frequently used data and issuing disk I/O requests.

DFS has two components in its services, and these are as follows:
1. Local Transparency
2. Redundancy

Local Transparency

It is achieved via the namespace component.

Redundancy

It is achieved via a file replication component.

Related requirements in distributed file systems are:

1. Transparency

2. Concurrent file updates

3. File Replication

4. Hardware & Operating system Heterogeneity

5. Fault tolerance

6. Consistency

7. Security

8. Efficiency

A distributed file system is to present certain degrees of transparency to the user and the system:
Access transparency: Clients are unaware that files are distributed and can access them in the same
way as local files are accessed.

Location transparency: A consistent name space exists encompassing local as well as remote files.
The name of a file does not give it location.
Concurrency transparency: All clients have the same view of the state of the file system. This means
that if one process is modifying a file, any other processes on the same system or remote systems
that are accessing the files will see the modifications in a coherent manner.

Failure transparency: The client and client programs should operate correctly after a server failure.
Heterogeneity: File service should be provided across different hardware and operating system
platforms.

Scalability: The file system should work well in small environments (1 machine, a dozen machines)
and also scale gracefully to huge ones (hundreds through tens of thousands of systems).

Replication transparency: To support scalability, we may wish to replicate files across multiple
servers. Clients should be unaware of this.

Migration transparency: Files should be able to move around without the client's knowledge.
Support fine-grained distribution of data: To optimize performance, we may wish to locate Page |
130 individual objects near the processes that use them.

Tolerance for network partitioning: The entire network or certain segments of it may be
unavailable to a client during certain periods (e.g. disconnected operation of a laptop). The file
system should be tolerant of this.

2. Formulate about the file service architecture?

File service architecture

• This is an abstract architectural model that underpins both NFS and AFS. It is based upon a division
of responsibilities between three modules – a client module that emulates a conventional file system
interface for application programs, and server modules, that perform operations for clients on
directories and on files. The architecture is designed to enable a stateless implementation of the
server module.

SUN NFS • Sun Microsystems’s Network File System (NFS) has been widely adopted in industry and
in academic environments since its introduction in 1985.

Andrew File System

• Andrew is a distributed computing environment developed at Carnegie Mellon University (CMU)

for use as a campus computing and information system. The design of the Andrew File System
(henceforth abbreviated AFS) reflects an intention to support information sharing on a large scale
by minimizing client-server communication. This is achieved by transferring whole files between
server and client computers and caching them at clients until the server receives a more up-to-date
version.

A file system is a system where data is stored persistently. In this article, we will see the concept of
File service architecture in distributed systems. The access control mechanism is used for sharing of
data between multiple users. Furthermore, concurrent access is provided certainly for read-only
access.

The following modules are the part of the file system:

Directory module: This module gives the relation to file names by connecting them to their
corresponding file IDs.

File module: This module serves the purpose of relating file IDs to specific files.
Access control module: This module provides the controlling feature by validating the requested
operation.

File access module: This module refers to the reading and writing of file data or attributes.

Block module: This module accesses and allocates the disk block.

Device module: This module refers to the disk I/O and buffering.

File Service Architecture  An architecture that offers a clear separation of the main concerns in
providing access to files is obtained by structuring the file service as three components:

File Service Architecture is an architecture that provides the facility of file accessing by designing the
file service as the following three components:

• A client module

• A flat file service

• A directory service

The implementation of exported interfaces by the client module is carried out by flat-file and
directory services on the server-side.

Let’s discuss the functions of these components in file service architecture in detail.

1. Flat file service: A flat file service is used to perform operations on the contents of a file. The
Unique File Identifiers (UFIDs) are associated with each file in this service. For that long sequence of
bits is used to uniquely identify each file among all of the available files in the distributed system.
When a request is received by the Flat file service for the creation of a new file then it generates a
new UFID and returns it to the requester.
Flat File Service Model Operations:

Read(FileId, i, n) -> Data: Reads up to n items from a file starting at item ‘i’ and returns it in Data.

Write(FileId, i, Data): Write a sequence of Data to a file, starting at item I and extending the file if
necessary.

Create() -> FileId: Creates a new file with length 0 and assigns it a UFID.

Delete(FileId): The file is removed from the file store.

GetAttributes(FileId) -> Attr: Returns the file’s file characteristics.

SetAttributes(FileId, Attr): Sets the attributes of the file.

2. Directory Service: The directory service serves the purpose of relating file text names with their
UFIDs (Unique File Identifiers). The fetching of UFID can be made by providing the text name of the
file to the directory service by the client. The directory service provides operations for creating
directories and adding new files to existing directories.

Directory Service Model Operations:

Lookup(Dir, Name) -> FileId : Returns the relevant UFID after finding the text name in the directory.
Throws an exception if Name is not found in the directory.

AddName(Dir, Name, File): Adds(Name, File) to the directory and modifies the file’s attribute record
if Name is not in the directory. If a name already exists in the directory, an exception is thrown.

UnName(Dir, Name): If Name is in the directory, the directory entry containing Name is removed. An
exception is thrown if the Name is not found in the directory.

GetNames(Dir, Pattern) -> NameSeq: Returns all the text names that match the regular expression
Pattern in the directory.

3. Client Module: The client module executes on each computer and delivers an integrated service
(flat file and directory services) to application programs with the help of a single API. It stores
information about the network locations of flat files and directory server processes. Here, recently
used file blocks hold in a cache at the client-side, thus, resulting in improved performance.

3. Illustrate the Sun Network File System Architecture?

Network File System (NFS)

Last Updated : 06 Feb, 2023
The advent of distributed computing was marked by the introduction of distributed file
systems. Such systems involved multiple client machines and one or a few servers. The
server stores data on its disks and the clients may request data through some protocol
messages. Advantages of a distributed file system.
Allows easy sharing of data among clients.
Provides centralized administration.
Provides security, i.e. one must only secure the servers to secure data.
Distributed File System Architecture:
Even a simple client/server architecture involves more components than the physical file
systems discussed previously in OS. The architecture consists of a client-side file system and
a server-side file system. A client application issues a system call (e.g. read(), write(), open(),
close() etc.) to access files on the client-side file system, which in turn retrieves files from the
server. It is interesting to note that to a client application, the process seems no different than
requesting data from a physical disk, since there is no special API required to do so. This
phenomenon is known as transparency in terms of file access. It is the client-side file system
that executes commands to service these system calls. For instance, assume that a client
application issues the read() system call. The client-side file system then messages the server-
side file system to read a block from the server’s disk and return the data back to the client.
Finally, it buffers this data into the read() buffer and completes the system call. The server-
side file system is also simply called the file server.
Message Description
NFSPROC_GETATTR Given a file handle, returns file attributes.
NFSPROC_SETATTR Sets/updates file attributes.
NFSPROC_LOOKUP Given file handle and name of the file to look up, returns file
handle.
NFSPROC_READ Given file handle, offset, count data and attributes, reads the
data.
NFSPROC_WRITE Given file handle, offset, count data and attributes, writes data
into the file.
NFSPROC_CREATE Given the directory handle, name of file and attributes, creates
a file.
NFSPROC_REMOVE Given the directory handle and name of file, deletes the file.
NFSPROC_MKDIR Given directory handle, name of directory and attributes,
creates a new directory.
SUN NFS • Sun Microsystems’s Network File System (NFS) has been widely adopted in industry and
in academic environments since its introduction in 1985. The design and development of NFS were
undertaken by staff at Sun Microsystems in 1984. Although several distributed file services had
already been developed and used in universities and research laboratories, NFS was the first file
service that was designed as a product. The design and implementation of NFS have achieved
success both technically and commercially.
NFS access control and authentication  The NFS server is stateless server, so the user's identity and
access rights must be checked by the server on each request.  In the local file system they are
checked only on the file’s access permission attribute. Every client request is accompanied by the
userID and groupID  It is not shown in the because they are inserted by the RPC system. 
Kerberos has been integrated with NFS to provide a stronger and more comprehensive security
solution. 

Mount service  Mount operation: mount(remote host, remote directory, local directory) Server
maintains a table of clients who have mounted filesystems at that server. Each client maintains a
table of mounted file systems holding: < IP address, port number, file handle ,Remote file systems
may be hard-mounted or soft-mounted in a client computer. illustrates a Client with two remotely
mounted file stores.

Sun’s Network File System (NFS) One of the first uses of distributed client/server computing was in
the realm of distributed file systems. In such an environment, there are a number of client machines
and one server (or a few); the server stores the data on its disks, and clients request data through
well-formed protocol messages. Figure 49.1 depicts the basic setup. Client 0 Client 1 Client 2 Client 3
Server RAID Network Figure 49.1: A Generic Client/Server System As you can see from the picture,
the server has the disks, and clients send messages across a network to access their directories and
files on those disks. Why do we bother with this arrangement? (i.e., why don’t we just let clients use
their local disks?) Well, primarily this setup allows for easy sharing of data across clients. Thus, if you
access a file on one machine (Client 0) and then later use another (Client 2), you will have the same
view of the file system. Your data is naturally shared across these different machines. A secondary
benefit is centralized administration; for example, backing up files can be done from the few server
machines instead of from the multitude of clients. Another advantage could be security; having all
servers in a locked machine room prevents certain types of problems from arising.
4. Explain in details about the Andrew file system?

Andrew File System • Andrew is a distributed computing environment developed at Carnegie

Mellon University (CMU) for use as a campus computing and information system. The design of the
Andrew File System (henceforth abbreviated AFS) reflects Page | 133 an intention to support
information sharing on a large scale by minimizing client-server communication. This is achieved by
transferring whole files between server and client computers and caching them at clients until the
server receives a more up-to-date version.

Morris et al. 1986 created a distributed computing environment for use as a campus computer and
information system at Carnegie Mellon University (CMU). An AFS is used by businesses to make it
easier for AFS client workstations in different locations to access stored server files. It presents a
homogeneous, location-independent file namespace to all client workstations via a group of
trustworthy servers. After login onto workstations that communicate inside the Distributed
Computing Infrastructure, users exchange data and programs (DCI). The goal is to facilitate large-
scale information exchange by reducing client-server communication. This is accomplished by
moving whole files between server and client computers and caching them until the servers get a
more recent version. An AFS uses a local cache to improve speed and minimize effort in dispersed
networks. A server, for example, replies to a workstation request by storing data in the workstation’s
local cache.

Andrew File System Architecture:

Vice: The Andrew File System provides a homogeneous, location-transparent file namespace to all
client workstations by utilizing a group of trustworthy servers known as Vice. The Berkeley Software
Distribution of the Unix operating system is used on both clients and servers. Each workstation’s
operating system intercepts file system calls and redirects them to a user-level process on that
workstation.

Venus: This mechanism, known as Venus, caches files from Vice and returns updated versions of
those files to the servers from which they originated. Only when a file is opened or closed does
Venus communicate with Vice; individual bytes of a file are read and written directly on the cached
copy, skipping Venus

This file system architecture was largely inspired by the need for scalability. To increase the number
of clients a server can service, Venus performs as much work as possible rather than Vice. Vice only
keeps the functionalities that are necessary for the file system’s integrity, availability, and security.
The servers are set up as a loose confederacy with little connectivity between them.
The following are the server and client components used in AFS networks:

Any computer that creates requests for AFS server files hosted on a network qualifies as a client.

The file is saved in the client machine’s local cache and shown to the user once a server responds
and transmits a requested file.

When a user visits the AFS, the client sends all modifications to the server via a callback mechanism.
The client machine’s local cache stores frequently used files for rapid access.

AFS implementation:

Client processes communicate with a UNIX kernel via standard system calls.

The kernel is tweaked significantly to identify references to Vice files in relevant activities and route
requests to the workstation’s Venus client process.

If a volume is missing from this cache, Venus contacts any server it already has a connection with,
asks for the location information, and enters it into the mapping cache. Venus makes a new
connection to the server unless it already has one. The file or directory is then retrieved using this
connection.

Authentication and security need the establishing of a connection. A copy of the target file is made
on the local disc when it is located and cached.

Venus then returns to the kernel, which opens the cached copy and gives the client process the
handle to it. Both AFS servers and clients use the UNIX file system as a low-level storage system. On
the workstation’s disc, the client cache is a local directory. This directory contains files with
placeholder names for cache entries.

Both Venus and server processes use the latter’s modes to access UNIX files directly, avoiding the
costly path-name-to-inode conversion method.

When a file is deleted from the cache, Venus informs the relevant server that the callback for that
file has been removed.

5. Describe the Name Services and the Domain Name System in DS?
In a Distributed System, a Naming Service is a specific service whose aim is to provide a consistent
and uniform naming of resources, thus allowing other programs or services to localize them and
obtain the required metadata for interacting with them.

• names: used to refer to shared resource

o computers

o services

o remote objects

o files

o users

• names are needed to request a computer system act on a specific, chosen resource

• processes need to be able to name resources to share them

• users need to be able to name each other to directly communicate

• sometimes descriptive attributes of a resource uniquely identify it

• human-readable names: e.g. /etc/passwd, http://www.registermachine.com

• identifier: not usually human-readable, e.g. remote object references, NFS file handles

o more efficiently stored and processed by software

• attribute: value of a property associated with an object

• address: value identifying the location of the object, rather than the object itself

o attribute of an object

o efficient for accessing objects

o cannot be used as a name, because the object may change its address

• pure name: contains no information about the object itself.

o Must be looked up to obtain an address before the named resource can be accessed

o e.g. names of people are pure names

o uninterpreted bit patterns

o address is the opposite extreme

• non-pure name contains some information about the object, typically location information

• a name is resolved when it is translated to data about the named resource

• binding: association between a name and an object

o names are bound to object attributes, rather than the objects themselves

o DNS maps human readable domain names to IP addresses/other attributes

o X500 directory service: can map a person’s name onto attributes e.g. email address, phone
number
Domain Name System (DNS) is a hostname for IP address translation service. DNS is a distributed
database implemented in a hierarchy of name servers. It is an application layer protocol for message
exchange between clients and servers. It is required for the functioning of the Internet.

What is the Need of DNS?

Every host is identified by the IP address but remembering numbers is very difficult for people also
the IP addresses are not static therefore a mapping is required to change the domain name to the IP
address. So DNS is used to convert the domain name of the websites to their numerical IP address.

Types of Domain

There are various kinds of domain:

1. Generic domains: .com(commercial), .edu(educational), .mil(military), .org(nonprofit

organization), .net(similar to commercial) all these are generic domains.

2. Country domain: .in (India) .us .uk

3. Inverse domain: if we want to know what is the domain name of the website. Ip to domain
name mapping.

Organization of Domain

It is very difficult to find out the IP address associated with a website because there are millions of
websites and with all those websites we should be able to generate the IP address immediately,
there should not be a lot of delays for that to happen organization of the database is very important.
6. Examine details the case study of X.500 directory services?

X500 Directory Service

X.500 is a directory service used in the same way as a conventional name service, but it is primarily
used to satisfy descriptive queries and is designed to discover the names and attributes of other users or
system resources. Users may have a variety of requirements for searching and browsing in a directory
of network users, organizations and system resources to obtain information about the entities that the
directory contains. The uses for such a service are likely to be quite diverse. They range from enquiries
that are directly analogous to the use of telephone directories, such as a simple ‘white pages’ access to
obtain a user’s electronic mail address or a ‘yellow pages’ query aimed, for example, at obtaining the
names and telephone numbers of garages specializing in the repair of a particular make of car, to the
use of the directory to access personal details such as job roles, dietary habits or even photographic
images of the individuals.

X.500 service architecture

The data stored in X.500 servers is organized in a tree structure with named nodes, as in the case of the
other name servers discussed in this chapter, but in X.500 a wide range of attributes are stored at each
node in the tree, and access is possible not just by name but also by searching for entries with any
required combination of attributes. The X.500 name tree is called the Directory Information Tree (DIT),
and the entire directory structure including the data associated with the nodes, is called the Directory
Information Base (DIB). There is intended to be a single integrated DIB containing information
provided by organizations throughout the world, with portions of the DIB located in individual X.500
servers. Typically, a medium-sized or large organization would provide at least one server. Clients
access the directory by establishing a connection to a server and issuing access requests. Clients can
contact any server with an enquiry. If the data required are not in the segment of the DIB held by the
contacted server, it will either invoke other servers to resolve the query or redirect the client to another
server.

Directory Server Agent (DSA)


Directory User Agent (DUA)

In the terminology of the X.500 standard, servers are Directory Service Agents (DSAs), and their clients
are termed Directory User Agents (DUAs). Each entry in the DIB consists of a name and a set of
attributes. As in other name servers, the full name of an entry corresponds to a path through the DIT
from the root of the tree to the entry. In addition to full or absolute names, a DUA can establish a
context, which includes a base node, and then use shorter relative names that give the path from the
base node to the named entry.

An X.500 DIB Entry

7. Discuss the implementation issues in distributed shared memory?

DSM is a mechanism that manages memory across multiple nodes and makes inter-process
communications transparent to end-users. The applications will think that they are running on
shared memory. DSM is a mechanism of allowing user processes to access shared data without using
inter-process communications. In DSM every node has its own memory and provides memory read
and write services and it provides consistency protocols. The distributed shared memory (DSM)
implements the shared memory model in distributed systems but it doesn’t have physical shared
memory. All the nodes share the virtual address space provided by the shared memory model. The
Data moves between the main memories of different nodes.

Types of Distributed shared memory

On-Chip Memory:

• The data is present in the CPU portion of the chip.

• Memory is directly connected to address lines.

• On-Chip Memory DSM is expensive and complex.

Bus-Based Multiprocessors:

• A set of parallel wires called a bus acts as a connection between CPU and memory.

• accessing of same memory simultaneously by multiple CPUs is prevented by using some

algorithms

• Cache memory is used to reduce network traffic.

Ring-Based Multiprocessors:

• There is no global centralized memory present in Ring-based DSM.

• All nodes are connected via a token passing ring.

Design and Implementation Issue of Distributed Shared Memory

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.

2.Structure 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.
8.Explain Sequential Consistency and IVY?

(a)System Model
(b) Write Invalidation
(C) Invalidation Protocols

What is consistency?

In a single computer, we can guarantee that the system stores the most recently updated data. However,
in a distributed system, data is shared and replicated across many computing nodes.

Consistency is a property of the distributed system which says that every node/replica has the same
view of data at a given point in time. This is irrespective of whichever client has updated the data. Strong
consistency would mean that the distributed system converges on a single value and the client always
reads the latest data.

Consistency models

A consistency model is a contract between a distributed system and the applications that run on it. This
model is a set of guarantees made by the distributed system. Different distributed systems employ
various consistency models.

Examples include linearizability, serializability, causal consistency, and eventual consistency. We will talk
about sequential consistency in this shot.

Sequential consistency

Sequential consistency implies that operations appear to take place in some total order. This order has
to be consistent with the order of operations on each individual process.

Therefore, reads may be stable in terms of real-time, but not in logical time. However, writes are totally
ordered according to logical time across all replicas.

A key difference between sequential consistency and linearizability is that linearizability may not
preserve real-time ordering.

Example of Sequential Consistency

Sequential Consistency Example

Let us consider a distributive system here for four different processes, P1, P2, P3, and P4. Here,
several different operations are occurring simultaneously, such as W(X, A) updating the value of X to
be A, and R(X) reading the value of X.

Now, if we follow the given global order of operations, we get a sequentially consistent system.

W(X,A), R(X) = A, W(Y,B), R(Y) = B

Types of Distributed Computing System Models

Physical Model

A physical model is basically a representation of the underlying hardware elements of a distributed

system. It encompasses the hardware composition of a distributed system in terms of computers
and other devices and their interconnectionsNodes – Nodes are the end devices that have the ability
of processing data, executing tasks and communicating with the other nodes. These end devices are
generally the computers at the user end or can be servers, workstations etc.

• Links – Links are the communication channels between different nodes and
intermediate devices.

• Broadcast links – It enables a single node to transmit data to multiple nodes

simultaneously.

• Multi-Access links – Multiple nodes share the same communication channel to

transfer data. Requires protocols to avoid interference while transmission.

• Middleware – These are the softwares installed and executed on the nodes. By running
middleware on each node It handles various tasks like communication with other nodes,
resource management, fault tolerance, synchronisation of different nodes and security to
prevent malicious and unauthorised access.

• Network Topology – This defines the arrangement of nodes and links in the distributed
computing system. The most common network topologies that are implemented are bus,
star, mesh, ring or hybrid. Choice of topology is done by determining the exact use cases and
the requirements.

• Communication Protocols – Communication protocols are the set rules and procedures for
transmitting data from in the links. Examples of these protocols include TCP, UDP, HTTPS,
MQTT etc. These allow the nodes to communicate and interpret the data.
Architectural Model

Architectural model in distributed computing system is the overall design and structure of the
system, and how its different components are organised to interact with each other and provide the
desired functionalities.

Client-Server model – It is a centralised approach in which the clients initiate requests for services
and severs respond by providing those services. It mainly works on the request-response model
where the client sends a request to the server and the server processes it, and responds to the client
accordingly etc.

• Peer-to-peer model – It is a decentralised approach in which all the distributed computing

nodes, known as peers, are all the same in terms of computing capabilities and can both
request as well as provide services to other peers The communication is directly done
amongst the peers without any intermediaries according to some set rules and procedures
defined in the P2P networks.
 • Layered model – It involves organising the system into multiple layers, where each layer will
provision a specific service. Each layer communicated with the adjacent layers using certain
well-defined protocols without affecting the integrity of the system. A hierarchical structure
is obtained where each layer abstracts the underlying complexity of lower layers.

Fundamental Model

The fundamental model in a distributed computing system is a broad conceptual framework that
helps in understanding the key aspects of the distributed systems. These are concerned with more
formal description of properties that are generally common in all architectural models.

Interaction Model – Distributed computing systems are full of many processes interacting with each
other in highly complex ways. Interaction model provides a framework to understand the
mechanisms and patterns that are used for communication and coordination among various
processes. Different components that are important in this model are –

• Message Passing

• Publish/Subscribe Systems

• Remote Procedure Call (RPC)

• Failure Model
 • Security Model – Distributed computing systems may suffer malicious attacks, unauthorised
access and data breaches. Security model provides a framework for understanding the
security requirements, threats, vulnerabilities, and mechanisms to safeguard the system and
its resources. Various aspects that are vital in the security model are –

• Data Integrity – Data integrity mechanisms protect against unauthorised modifications or

tampering of data. They ensure that data remains unchanged during storage, transmission,
or processing. Data integrity mechanisms include:

• Hash functions – Generating a hash value or checksum from data to verify its
integrity.

• Digital signatures – Using cryptographic techniques to sign data and verify its
authenticity and integrity.

Write Invalidation

In distributed systems, invalidation refers to the process of recognizing and managing outdated or
stale data across multiple nodes or components within the system. Here's a concise 10-mark answer
outlining the key points:

1. **Definition**: Invalidation in distributed systems involves the identification and handling of

obsolete data to ensure data consistency and accuracy across the system.

2. **Purpose**: The primary objective of invalidation mechanisms is to maintain data coherence by

promptly updating or removing outdated information, thereby preventing inconsistencies and
ensuring that all nodes access the most recent data.

3. **Concurrency Control**: Invalidation plays a crucial role in managing concurrent access to

shared data. By invalidating outdated copies, it helps avoid conflicts and ensures that all nodes
operate on the latest version of data.

4. **Cache Management**: In distributed caching systems, invalidation is essential for maintaining

cache coherence. When data is modified in the primary storage, invalidation messages are sent to
relevant cache nodes to ensure that they update or evict cached entries accordingly.

5. **Consistency Models**: Different consistency models, such as eventual consistency or strong

consistency, rely on invalidation strategies to enforce their respective semantics. For example,
strong consistency models may require immediate invalidation to ensure all nodes see the same
data version at all times.
6. **Invalidation Techniques**: Various invalidation techniques exist, including write-invalidate and
read-invalidate protocols. In write-invalidate, updating a data item invalidates copies of that item in
other nodes. In read-invalidate, reading an item invalidates outdated copies before fetching the
latest version.

7. **Communication Overhead**: While invalidation is crucial for data consistency, it introduces

communication overhead. Systems must carefully balance the frequency and granularity of
invalidation messages to minimize overhead while ensuring timely updates.

8. **Scalability Considerations**: In large-scale distributed systems, efficient invalidation

mechanisms are vital for scalability. As the system grows, managing invalidation efficiently becomes
more challenging due to increased communication and coordination overhead.

9. **Failure Handling**: Invalidation mechanisms must handle node failures and network partitions
gracefully. Strategies like quorum-based techniques or consensus algorithms help ensure that
invalidation messages are reliably propagated even in the presence of failures.

10. **Evaluation and Optimization**: Continuous evaluation and optimization of invalidation

strategies are necessary to adapt to changing system conditions and workload patterns. Techniques
such as adaptive invalidation policies or dynamic adjustment of invalidation parameters can enhance
system performance and resilience.

Invalidation Protocols

By addressing these points, one can provide a comprehensive understanding of invalidation in

distributed systems and its significance in ensuring data consistency and system reliability.

There are different types of invalidation protocols, including:

1. **Write-invalidate protocol**: In this protocol, when a node modifies a data item, it invalidates all
copies of that item held by other nodes. This means that any subsequent access to the data in other
nodes will require fetching the updated value from the node that made the modification.

2. **Read-invalidate protocol**: Similar to the write-invalidate protocol, but invalidation occurs only
when a node reads a data item that has been modified elsewhere. This ensures that nodes always
have the latest version of the data when they access it.

3. **Timestamp-based invalidation**: Each data item is associated with a timestamp indicating

when it was last modified. When a node requests a data item, it checks the timestamp to determine
if it has the latest version. If not, it fetches the updated version from another node.

4. **Version-based invalidation**: Similar to timestamp-based invalidation, but instead of

timestamps, each data item is associated with a version number. Nodes compare version numbers
to determine if they have the latest version of the data.

Invalidation protocols are essential for maintaining data consistency in distributed systems, but they
can introduce overhead in terms of network communication and coordination between nodes. The
choice of invalidation protocol depends on factors such as the consistency requirements of the
system, the frequency of data updates, and the network latency.

9.Describe a Dynamic Distributed Manager Algorithm?

A Dynamic Distributed Manager (DDM) algorithm in distributed systems is designed to dynamically

manage resources, tasks, or nodes in response to changing conditions within the system. The primary
objective of a DDM algorithm is to optimize system performance, resource utilization, fault tolerance,
or other relevant metrics while adapting to fluctuations in load, network conditions, or system
configuration. Here's an outline of a Dynamic Distributed Manager algorithm:

1. **System Monitoring**: The DDM algorithm continuously monitors the state of the distributed
system. This includes collecting data on the status of individual nodes, resource utilization metrics
(such as CPU, memory, and network bandwidth), task execution times, network latency, and any
other relevant parameters. Monitoring can be performed through periodic probes, heartbeat messages,
or other communication mechanisms.

2. **State Analysis**: Based on the collected monitoring data, the DDM algorithm analyzes the
current state of the system. It identifies any anomalies or deviations from expected behavior, such as
overloaded nodes, underutilized resources, network congestion, or performance bottlenecks. The
analysis phase may involve statistical modeling, machine learning techniques, or rule-based reasoning
to interpret the monitoring data and derive insights about the system's behavior.

3. **Decision Making**: Using the results of the state analysis, the DDM algorithm makes decisions
on how to dynamically reconfigure the system to improve its performance or adapt to changing
conditions. This may involve actions such as load balancing, resource reallocation, task migration,
replica placement, or node scaling. The decisions should be guided by predefined optimization
objectives or policies, such as minimizing response time, maximizing throughput, or ensuring fault
tolerance.

4. **Action Execution**: Once decisions are made, the DDM algorithm initiates actions to implement
the planned changes across the distributed system. This may involve coordinating with individual
nodes or components to perform tasks such as migrating virtual machines, reallocating resources,
adjusting configuration parameters, or rerouting network traffic. The execution phase should be
orchestrated to ensure that changes are applied smoothly and without disrupting the normal operation
of the system.

5. **Feedback and Adaptation**: After executing the planned actions, the DDM algorithm collects
feedback from the system to evaluate the effectiveness of the changes. This feedback may include
performance metrics, error rates, user feedback, or other indicators of system behavior. Based on the
feedback, the algorithm iteratively adjusts its decisions and actions to adapt to evolving conditions,
creating a closed-loop control mechanism that continuously improves system performance and
responsiveness over time.

Designing an effective Dynamic Distributed Manager algorithm requires careful consideration of

factors such as scalability, efficiency, fault tolerance, responsiveness, and adaptability. The algorithm
should be able to handle large-scale distributed systems with diverse workloads and changing
environments while optimizing system performance and resource utilization in a cost-effective
manner. Additionally, it should be resilient to failures, network partitions, and other disruptions,
ensuring that the system remains operational and responsive under adverse conditions.

10. Discuss the Release Consistency and MUNIN?

Release consistency and MUNIN are two concepts related to maintaining consistency in distributed
systems. Let's discuss each of them:

1. **Release Consistency**:

- **Definition**: Release consistency is a consistency model used in distributed shared-memory

systems. It defines the behavior of memory accesses by different processes or threads in a
distributed environment.

- **Principle**: In release consistency, a program execution is divided into a sequence of phases,

where each phase consists of a series of memory accesses by one or more processes or threads.
Within each phase, memory accesses can be performed in any order, allowing for maximum
concurrency.

- **Synchronization**: To ensure consistency, processes or threads must explicitly delineate the

boundaries between phases using synchronization primitives such as release and acquire operations.
The release operation indicates the end of a phase, and the acquire operation indicates the
beginning of the next phase.

- **Consistency Guarantees**: Release consistency guarantees that memory accesses within a

phase are consistent with the order specified by the synchronization operations. However, it does
not provide any guarantees across phases, allowing for relaxed consistency and increased
parallelism.

2. **MUNIN**:

- **Definition**: MUNIN is a software-based distributed shared memory (DSM) system that

implements release consistency in distributed systems. It was developed at Cornell University as part
of the Munin project.

- **Architecture**: MUNIN consists of a distributed runtime system that manages shared memory
across multiple nodes in a cluster or network. It provides a programming interface that allows
applications to access shared data structures as if they were local.

- **Release Consistency Protocol**: MUNIN implements release consistency using a protocol

known as lazy release consistency (LRC). In LRC, updates to shared data are delayed until the end of
a phase, allowing for increased concurrency and reduced communication overhead.

- **Synchronization**: MUNIN provides synchronization primitives such as release and acquire

operations to enforce consistency between phases. These primitives allow applications to
coordinate access to shared data and ensure that memory accesses are performed in the correct
order.

- **Performance**: MUNIN aims to provide high performance and scalability for parallel and
distributed applications by leveraging release consistency to maximize concurrency and minimize
synchronization overhead. It achieves this through a combination of runtime optimizations,
communication protocols, and memory management techniques.

In summary, release consistency is a consistency model used in distributed shared-memory systems,

while MUNIN is a specific implementation of release consistency in a software-based distributed
shared memory system. MUNIN provides a programming interface and runtime system that
supports release consistency, allowing distributed applications to efficiently share and access data
across multiple nodes in a network.

11. Illustrate Other Consistency Models ?

There are several consistency models beyond release consistency. Each consistency model defines
the ordering and visibility of operations across multiple processes or threads in a distributed system.
Here are some common consistency models:

1. **Sequential Consistency**:- In sequential consistency, the execution of operations appears as if

they occur in a single, global total order that is consistent with the program order of each
process/thread.

- All processes observe the same order of operations, ensuring that the behavior of the distributed
system is consistent with a single, coherent state.
 - Synchronization primitives like barriers or locks are used to enforce orderings between
operations.

2. **Causal Consistency**:

- Causal consistency preserves causality between operations. If operation A causally precedes

operation B (i.e., A influences B), then all processes must observe A before B.

- However, concurrent operations may appear in different orders on different processes as long as
there is no causal relationship between them.

- This model allows for greater concurrency than sequential consistency while still maintaining
causal dependencies.

3. **Linearizability (Atomic Consistency)**:

- Linearizability ensures that operations appear to occur instantaneously at a single point in time
between their invocation and response.

- This model provides the strongest consistency guarantee by guaranteeing that all operations
appear to take effect instantaneously at some point between their invocation and response.

- Achieving linearizability often requires coordination mechanisms like distributed locks or

consensus algorithms.

4. **Eventual Consistency**:

- Eventual consistency relaxes the consistency requirements by allowing replicas to diverge

temporarily but guarantees that they will converge to a consistent state eventually.

- Updates are propagated asynchronously, and replicas may temporarily be inconsistent with each
other.
 - Systems implementing eventual consistency often use techniques like version vectors, conflict
resolution, or anti-entropy mechanisms to reconcile divergent replicas over time.

5. **Read-your-Writes Consistency**:

- Read-your-writes consistency guarantees that once a process has performed a write operation,
any subsequent read operation by the same process will observe the effects of that write.

- This model is commonly used in distributed storage systems to provide strong consistency
guarantees for data accesses made by the same client.

- Synchronization mechanisms like session tokens or client-specific metadata are used to enforce
this consistency guarantee.

These consistency models represent a spectrum of trade-offs between consistency, availability, and
partition tolerance in distributed systems. The choice of a consistency model depends on the specific
requirements and constraints of the application and the underlying distributed environment.

12. What are Naming Services?

Naming services in distributed systems provide a mechanism for assigning and resolving names to
resources, such as files, services, or network addresses, in a distributed environment. They abstract
the underlying complexity of locating and accessing resources distributed across multiple nodes in a
network. Here's a deeper look at naming services:

1. **Name Assignment**: Naming services assign unique names or identifiers to resources within
the distributed system. These names are typically human-readable and provide a convenient way for
users or applications to refer to resources without needing to know their physical locations or
network addresses.

2. **Name Resolution**: When a user or application needs to access a resource, they use its name
to query the naming service for its location or network address. The naming service resolves the
name to the appropriate resource location, allowing the requester to establish communication or
access the resource directly.

3. **Decentralization**: In decentralized naming services, the mapping between names and

resources is distributed across multiple nodes in the network. Each node may be responsible for a
subset of the namespace, and the naming service must provide mechanisms for resolving names
across these distributed nodes.

4. **Scalability**: Naming services should be designed to scale efficiently as the size of the
distributed system grows. This may involve techniques such as hierarchical naming structures,
distributed hash tables (DHTs), or partitioning the namespace across multiple nodes to distribute the
load evenly.

5. **Fault Tolerance**: Distributed naming services must be resilient to failures, such as node
crashes or network partitions, to ensure continuous availability and reliability. This may involve
replicating naming information across multiple nodes and employing techniques such as quorum-
based protocols or consensus algorithms to maintain consistency and handle failures.

6. **Consistency**: Consistency is crucial in naming services to ensure that all nodes in the
distributed system have a consistent view of the namespace. This may involve enforcing consistency
constraints, such as atomicity and durability, when updating naming information and resolving
conflicts between concurrent updates.
Examples of naming services in distributed systems include:

- **Domain Name System (DNS)**: A widely used naming service on the internet that translates
domain names (e.g., example.com) into IP addresses and vice versa.

- **Directory Services**: Services like Lightweight Directory Access Protocol (LDAP) provide
centralized repositories for storing and querying information about network resources, such as
users, groups, and devices.

- **Service Discovery Systems**: Systems like Apache ZooKeeper, Consul, or etcd enable dynamic
service discovery and configuration in distributed environments by providing a centralized registry of
available services and their locations.

Overall, naming services play a crucial role in simplifying the management and access of resources in
distributed systems by providing a unified interface for naming and locating resources across the
network.

13. Explain about Distributed Shared Memory?

DSM is a mechanism that manages memory across multiple nodes and makes inter-process
communications transparent to end-users. The applications will think that they are running on
shared memory. DSM is a mechanism of allowing user processes to access shared data without using
inter-process communications. In DSM every node has its own memory and provides memory read
and write services and it provides consistency protocols. The distributed shared memory (DSM)
implements the shared memory model in distributed systems but it doesn’t have physical shared
memory. All the nodes share the virtual address space provided by the shared memory model. The
Data moves between the main memories of different nodes.

Types of Distributed shared memory

On-Chip Memory:

• The data is present in the CPU portion of the chip.

 • Memory is directly connected to address lines.

• On-Chip Memory DSM is expensive and complex.

Bus-Based Multiprocessors:

• A set of parallel wires called a bus acts as a connection between CPU and memory.

• accessing of same memory simultaneously by multiple CPUs is prevented by using some

algorithms

• Cache memory is used to reduce network traffic.

Ring-Based Multiprocessors:

• There is no global centralized memory present in Ring-based DSM.

• All nodes are connected via a token passing ring.

• In ring-bases DSM a single address line is divided into the shared area.

Advantages of Distributed shared memory

• Simpler abstraction: Programmer need not concern about data movement, As the address
space is the same it is easier to implement than RPC.

• Easier portability: The access protocols used in DSM allow for a natural transition from
sequential to distributed systems. DSM programs are portable as they use a common
programming interface.

• locality of data: Data moved in large blocks i.e. data near to the current memory location
that is being fetched, may be needed future so it will be also fetched.

• on-demand data movement: It provided by DSM will eliminate the data exchange phase.

• larger memory space: It provides large virtual memory space, the total memory size is the
sum of the memory size of all the nodes, paging activities are reduced.

• Better Performance: DSM improve performance and efficiency by speeding up access to

data.

• Flexible communication environment: They can join and leave DSM system without
affecting the others as there is no need for sender and receiver to existing,

• process migration simplified: They all share the address space so one process can easily be
moved to a different machine.

Apart from the above-mentioned advantages, DSM has furthermore advantages like:

• Less expensive when compared to using a multiprocessor system.

• No bottlenecks in data access.

• Scalability i.e. Scales are pretty good with a large number of nodes.