UNIT -4

What is DFS (Distributed File System)

A Distributed File System (DFS) is a file system that is distributed on multiple file servers or
multiple locations. It allows programs to access or store isolated files as they do with the local
ones, allowing programmers to access files from any network or computer. In this article, we will
discuss everything about Distributed File System.
(OR)
A distributed file system (DFS) is a networked architecture that allows multiple users and
applications to access and manage files across various machines as if they were on a local
storage device. Instead of storing data on a single server, a DFS spreads files across multiple
locations, enhancing redundancy and reliability.
• This setup not only improves performance by enabling parallel access but also simplifies
data sharing and collaboration among users.
• By abstracting the complexities of the underlying hardware, a distributed file system
provides a seamless experience for file operations, making it easier to manage large
volumes of data in a scalable manner.
Components of DFS
• Location Transparency: Location Transparency achieves through the namespace
component.
• Redundancy: Redundancy is done through a file replication component.
In the case of failure and heavy load, these components together improve data availability by
allowing the sharing of data in different locations to be logically grouped under one folder, which
is known as the “DFS root”. It is not necessary to use both the two components of DFS together, it
is possible to use the namespace component without using the file replication component and it
is perfectly possible to use the file replication component without using the namespace
component between servers.
Distributed File System Replication
Early iterations of DFS made use of Microsoft’s File Replication Service (FRS), which allowed for
straightforward file replication between servers. The most recent iterations of the whole file are
distributed to all servers by FRS, which recognises new or updated files. “DFS Replication” was
developed by Windows Server 2003 R2 (DFSR). By only copying the portions of files that have
changed and minimising network traffic with data compression, it helps to improve FRS.
Additionally, it provides users with flexible configuration options to manage network traffic on a
configurable schedule.
Features of DFS
• Transparency
o Structure transparency: There is no need for the client to know about the number
or locations of file servers and the storage devices. Multiple file servers should be
provided for performance, adaptability, and dependability.
 UNIT -4
o Access transparency: Both local and remote files should be accessible in the same
manner. The file system should be automatically located on the accessed file and
send it to the client’s side.
o Naming transparency: There should not be any hint in the name of the file to the
location of the file. Once a name is given to the file, it should not be changed during
transferring from one node to another.
o Replication transparency: If a file is copied on multiple nodes, both the copies of
the file and their locations should be hidden from one node to another.
• User mobility: It will automatically bring the user’s home directory to the node where the
user logs in.
• Performance: Performance is based on the average amount of time needed to convince
the client requests. This time covers the CPU time + time taken to access secondary
storage + network access time. It is advisable that the performance of the Distributed File
System be similar to that of a centralized file system.
• Simplicity and ease of use: The user interface of a file system should be simple and the
number of commands in the file should be small.
• High availability: A Distributed File System should be able to continue in case of any
partial failures like a link failure, a node failure, or a storage drive crash.
A high authentic and adaptable distributed file system should have different and
independent file servers for controlling different and independent storage devices.
• Scalability: Since growing the network by adding new machines or joining two networks
together is routine, the distributed system will inevitably grow over time. As a result, a good
distributed file system should be built to scale quickly as the number of nodes and users in
the system grows. Service should not be substantially disrupted as the number of nodes
and users grows.
• Data integrity: Multiple users frequently share a file system. The integrity of data saved in a
shared file must be guaranteed by the file system. That is, concurrent access requests
from many users who are competing for access to the same file must be correctly
synchronized using a concurrency control method. Atomic transactions are a high-level
concurrency management mechanism for data integrity that is frequently offered to users
by a file system.
• Security: A distributed file system should be secure so that its users may trust that their
data will be kept private. To safeguard the information contained in the file system from
unwanted & unauthorized access, security mechanisms must be implemented.
Applications of DFS
• NFS: NFS stands for Network File System. It is a client-server architecture that allows a
computer user to view, store, and update files remotely. The protocol of NFS is one of the
several distributed file system standards for Network-Attached Storage (NAS).
• CIFS: CIFS stands for Common Internet File System. CIFS is an accent of SMB. That is,
CIFS is an application of SIMB protocol, designed by Microsoft.
 UNIT -4
• SMB: SMB stands for Server Message Block. It is a protocol for sharing a file and was
invented by IBM. The SMB protocol was created to allow computers to perform read and
write operations on files to a remote host over a Local Area Network (LAN). The directories
present in the remote host can be accessed via SMB and are called as “shares”.
• Hadoop: Hadoop is a group of open-source software services. It gives a software
framework for distributed storage and operating of big data using the MapReduce
programming model. The core of Hadoop contains a storage part, known as Hadoop
Distributed File System (HDFS), and an operating part which is a MapReduce programming
model.
• NetWare: NetWare is an abandon computer network operating system developed by
Novell, Inc. It primarily used combined multitasking to run different services on a personal
computer, using the IPX network protocol.
Working of DFS
There are two ways in which DFS can be implemented:
• Standalone DFS namespace: It allows only for those DFS roots that exist on the local
computer and are not using Active Directory. A Standalone DFS can only be acquired on
those computers on which it is created. It does not provide any fault liberation and cannot
be linked to any other DFS. Standalone DFS roots are rarely come across because of their
limited advantage.
• Domain-based DFS namespace: It stores the configuration of DFS in Active Directory,
creating the DFS namespace root accessible
at \\<domainname>\<dfsroot> or \\<FQDN>\<dfsroot>

Advantages of Distributed File System(DFS)

• DFS allows multiple user to access or store the data.
• It allows the data to be share remotely.
• It improved the availability of file, access time, and network efficiency.
• Improved the capacity to change the size of the data and also improves the ability to
exchange the data.
 UNIT -4
• Distributed File System provides transparency of data even if server or disk fails.
Disadvantages of Distributed File System(DFS)
• In Distributed File System nodes and connections needs to be secured therefore we can
say that security is at stake.
• There is a possibility of lose of messages and data in the network while movement from
one node to another.
• Database connection in case of Distributed File System is complicated.
• Also handling of the database is not easy in Distributed File System as compared to a
single user system.
• There are chances that overloading will take place if all nodes tries to send data at once.
File Service Architecture
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.

Model for File Service Architecture

Let’s discuss the functions of these components in file service architecture in detail.
 UNIT -4
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.
File Access Protocols
 UNIT -4
Below are some of the File Access Protocols:
• NFS (Network File System)
o Definition: A distributed file system protocol allowing a user on a client computer to
access files over a network in a manner similar to how local storage is accessed.
o Components: NFS server, NFS client.
o Use Cases: Widely used in UNIX/Linux environments for sharing directories and
files across networks.
o Advantages: Transparent file access, central management.
o Disadvantages: Performance can degrade with high loads, security vulnerabilities if
not configured properly.
• FTP (File Transfer Protocol)
o Definition: A standard network protocol used to transfer files from one host to
another over a TCP-based network, such as the Internet.
o Components: FTP server, FTP client.
o Use Cases: File transfers between systems, website management.
o Advantages: Simple to implement, widely supported.
o Disadvantages: Data is not encrypted by default, leading to security risks.
• SFTP (SSH File Transfer Protocol)
o Definition: A secure version of FTP that uses SSH to encrypt all data transfers.
o Components: SFTP server, SFTP client.
o Use Cases: Secure file transfers over untrusted networks, remote server
management.
o Advantages: Secure, robust authentication methods.
o Disadvantages: Slightly more complex to set up than FTP.
• HDFS (Hadoop Distributed File System)
o Definition: A distributed file system designed to run on commodity hardware, part
of the Hadoop ecosystem.
o Components: NameNode, DataNodes, client.
o Use Cases: Big data storage and processing, high-throughput data applications.
o Advantages: Scalable, fault-tolerant.
o Disadvantages: High latency for small files, complex setup.
Napster and its Legacy
 UNIT -4
Napster is often seen as a revolutionary technology because it was one of the first peer-to-peer
(P2P) file-sharing networks, letting users share music directly with each other over the internet.
Though it was mainly known for allowing people to download music for free, Napster’s design
sparked huge changes in distributed systems and internet technology.
Here’s a breakdown of what made Napster special, how it worked, and why its ideas are still
relevant today.

What Was Napster, and How Did It Work?

Before Napster, if you wanted to share files online, you usually had to upload them to a
centralized server (like a website) where others could download them. This method was slow,
expensive, and limited by the storage and bandwidth of the central server.
Napster introduced a new approach with these key elements:
• Peer-to-Peer (P2P) Sharing: Instead of storing music files on a central server, Napster’s
network allowed people to store files on their own computers and share them directly with
each other.
• Central Directory Server: Napster still had a central server that kept a list of all the songs
that users were sharing, along with information on who had each song. This way, if you
wanted a song, Napster would direct you to a user who had it.
For example, if you wanted to download a song, you would:
1. Connect to Napster’s central directory server.
2. Search for the song title.
3. Napster’s server would tell you which users had the file and could connect you to them.
4. You’d download the song directly from that user’s computer.
This model was groundbreaking because, by keeping only a list of available files and not the files
themselves, Napster saved on costs and allowed files to be quickly shared between users.

Why Was Napster So Important?

Napster was important because it proved that a P2P network could share large amounts of data
without needing centralized storage or massive internet infrastructure. This inspired several new
developments in distributed systems.
1. Decentralization: Napster’s structure made people see the benefits of decentralized file-
sharing, where the responsibility for storing and sharing files is spread across all users.
Napster’s design, however, had one weakness: its central directory server was still a single
point of failure (and a legal target).
Later systems, like Gnutella and BitTorrent, adopted a fully decentralized approach. They spread
out the directory functions so there was no central server, making it harder to shut down the
network and more resilient to failures.
 UNIT -4
2. Resource Sharing and Efficiency: Napster demonstrated how P2P could make better use
of available resources. Instead of investing in costly storage servers, Napster used the
storage space and internet connections of its users. This idea spread to other distributed
systems, like content delivery networks (CDNs), which deliver content from servers closer
to the user for faster access.
3. Inspiration for New Technologies: Napster showed that people were interested in sharing
files over P2P networks. This idea has influenced distributed systems in many areas:
o Blockchain and Cryptocurrencies: Like Napster, blockchain networks are
decentralized. Blockchain operates on a P2P network where transactions are
verified and stored across many computers, not just one central server.
o Edge Computing: Napster’s model inspired the idea of using devices at the "edge"
(closer to the user) to handle data processing, which reduces the need for
centralized data centers and makes systems more efficient.
4. Legal and Social Impact: Napster’s rise and fall also highlighted the need for lawful ways
to distribute content online, pushing the music industry toward legal digital downloads and
streaming. Services like iTunes and Spotify owe some of their early success to Napster’s
impact on how people accessed music.

Napster’s Long-Term Legacy

Napster changed the way people thought about sharing data and accessing content. Its influence
is seen today in distributed systems that:
• Don’t rely on a central authority (like in blockchains).
• Use users' resources (like in edge computing or torrenting).
• Distribute workloads for greater efficiency and resiliency (as seen in modern content
delivery networks).
Though Napster itself was short-lived, it marked the beginning of a new era of internet-based
sharing and laid the groundwork for modern, decentralized technology that continues to shape
digital systems.
Peer-to-Peer Middleware in distributed systems
Peer-to-Peer (P2P) middleware is a crucial layer in distributed systems that facilitates direct
communication and resource sharing among distributed nodes (or peers) without needing a
central server. It allows users to share data, resources, and services seamlessly, enabling a
variety of applications, from file sharing to collaborative work.

Key Characteristics of P2P Middleware

1. Decentralization: Unlike traditional client-server models, where a central server handles
requests, P2P middleware enables each peer to act both as a client and a server. This
decentralization enhances resilience and reduces bottlenecks.
 UNIT -4
2. Resource Sharing: P2P middleware allows nodes to share resources, such as processing
power, storage, and bandwidth. Each peer can contribute its resources, creating a more
efficient and scalable network.
3. Dynamic Network Topology: P2P networks can adapt to changes in the network, such as
peers joining or leaving. This dynamic nature is crucial for maintaining connectivity and
resource availability.
4. Scalability: P2P middleware can efficiently scale as more peers join the network. Each
new peer can contribute resources, improving overall performance and capacity.
5. Fault Tolerance: By distributing data and processes across multiple peers, P2P systems
can continue functioning even if some peers fail. This redundancy enhances reliability.
Components of P2P Middleware
1. Discovery Services: These allow peers to find each other in the network. Discovery can be
done through:
o Centralized Directories: A central server maintains a list of peers and resources
(like early versions of Napster).
o Decentralized Discovery: Peers can query each other to find resources, improving
resilience and reducing reliance on a central point.
2. Communication Protocols: P2P middleware includes protocols for data transmission
between peers. Common protocols include:
o BitTorrent Protocol: Efficiently transfers files by breaking them into pieces and
allowing multiple peers to download and upload simultaneously.
o Distributed Hash Tables (DHT): A method for storing and retrieving data across
distributed networks efficiently, often used in systems like BitTorrent and Kademlia.
3. Data Management: P2P middleware must manage how data is stored, retrieved, and
synchronized among peers. This includes techniques for:
o Replication: Storing copies of data across multiple peers to enhance availability.
o Consistency: Ensuring that changes made by one peer are reflected across others,
even in the face of concurrent updates.
4. Security Mechanisms: Security is vital in P2P systems due to the open nature of the
network. Middleware may include:
o Authentication: Verifying the identity of peers to prevent unauthorized access.
o Encryption: Protecting data during transmission to ensure confidentiality and
integrity.
Applications of P2P Middleware
1. File Sharing: Systems like BitTorrent use P2P middleware to distribute large files efficiently
by breaking them into smaller pieces and allowing multiple peers to upload and download
simultaneously.
 UNIT -4
2. Streaming Services: P2P can support live streaming by allowing users to share portions of
the stream with each other, reducing server load and improving scalability.
3. Collaborative Work: P2P middleware enables collaborative applications, where multiple
users can work together in real-time on shared documents or projects without relying on a
central server.
4. Blockchain Technologies: Many blockchain networks operate on P2P middleware, where
each node maintains a copy of the ledger, facilitating decentralized and secure
transactions.
5. Distributed Computing: P2P middleware supports distributed computing platforms,
where computational tasks are distributed across multiple nodes, allowing for efficient
resource utilization (e.g., SETI@home).
Challenges in P2P Middleware
1. Network Management: Managing a dynamic and potentially volatile network of peers can
be complex. Issues like peer churn (frequent joining and leaving of peers) can disrupt
connectivity and resource availability.
2. Security Risks: The open nature of P2P networks makes them vulnerable to various
attacks, including data interception, impersonation, and denial-of-service (DoS) attacks.
3. Quality of Service (QoS): Ensuring a consistent level of performance (e.g., latency,
bandwidth) in a P2P environment can be challenging due to the varying capabilities and
availability of peers.
4. Data Consistency: Maintaining consistency across distributed peers can be complicated,
especially in scenarios involving concurrent updates or failures.
Routing Overlays. Coordination and Agreement: Introduction, in distributed systems
Routing overlays, coordination, and agreement are essential concepts in distributed systems,
addressing how nodes communicate, share resources, and maintain consistency across a
decentralized environment. Here’s a detailed introduction to these topics:
1. Routing Overlays
Definition: Routing overlays are virtual networks built on top of existing physical networks. They
provide a structured way to connect nodes (or peers) and facilitate communication among them,
often using specific algorithms and protocols.
Key Characteristics:
• Virtual Topology: Overlays create a logical network that may differ from the physical
connections. This abstraction allows for more flexible routing strategies and improved fault
tolerance.
• Decentralization: Overlays typically operate in a decentralized manner, with no single
point of control. Each node can make independent decisions about routing, enhancing
resilience.
 UNIT -4
• Efficiency: By leveraging various routing algorithms (e.g., DHTs, random walks), overlays
can efficiently manage data location, retrieval, and network traffic.
Types of Routing Overlays:
1. Structured Overlays: Use a specific topology (e.g., Chord, Pastry) that maintains a
consistent organization of nodes, allowing for predictable routing and efficient lookups.
o Example: Chord employs a consistent hashing technique to distribute keys
uniformly across nodes, facilitating efficient lookups.
2. Unstructured Overlays: Have a more ad-hoc organization where nodes are
interconnected in a less predictable manner, often relying on random walks for resource
discovery.
o Example: Gnutella utilizes unstructured overlays, allowing any node to connect with
any other node, leading to flexible yet potentially less efficient searches.
Applications:
• File Sharing: Overlays enable efficient distribution of files in P2P networks (e.g.,
BitTorrent).
• Content Delivery: Enhance performance in CDNs by optimizing routes based on user
proximity and resource availability.
• Distributed Hash Tables (DHTs): Serve as the backbone for decentralized resource
location and retrieval.

2. Coordination in Distributed Systems

Definition: Coordination refers to the processes and mechanisms that ensure the consistent
operation of distributed nodes. It involves managing dependencies, synchronizing actions, and
facilitating communication among distributed components.
Key Concepts:
• Synchronization: Ensuring that distributed processes operate in a coordinated manner,
often requiring the use of locks, semaphores, or consensus algorithms.
• Consistency Models: Define the expected behavior of data in distributed systems, such
as:
o Strong Consistency: All nodes reflect the most recent write before any read occurs.
o Eventual Consistency: Nodes may not immediately reflect updates, but they will
converge to a consistent state over time.
Techniques for Coordination:
1. Consensus Algorithms: Protocols that ensure all nodes agree on a single value or state.
Examples include:
 UNIT -4
o Paxos: A classic consensus algorithm that operates under certain conditions to
achieve agreement among distributed nodes.
o Raft: A more understandable alternative to Paxos, providing a mechanism for leader
election and log replication.
2. Leader Election: A process where nodes select a coordinator or leader to streamline
decision-making and resource management.
3. Distributed Transactions: Techniques like two-phase commit (2PC) ensure all
participants in a transaction either commit or rollback changes, maintaining consistency.

3. Agreement in Distributed Systems

Definition: Agreement in distributed systems refers to the process through which distributed
nodes reach a common decision or state, despite potential failures or network partitions. It is a
fundamental requirement for ensuring consistency and reliability in distributed applications.
Key Challenges:
• Network Partitions: Nodes may become isolated from each other due to network failures,
making it challenging to achieve agreement.
• Fault Tolerance: The system must handle node failures and recover without losing
consistency or availability.
Models of Agreement:
1. Byzantine Agreement: Deals with scenarios where nodes may fail or behave maliciously.
The algorithm must reach a consensus despite some nodes providing incorrect
information.
2. Atomic Broadcast: Guarantees that messages sent by one node are delivered to all others
in the same order, essential for maintaining consistency in distributed applications.
Importance of Agreement:
• Consistency: Agreement protocols ensure that all nodes reflect the same data state,
crucial for applications requiring high data integrity (e.g., banking systems).
• Reliability: Ensuring agreement contributes to system reliability, allowing applications to
function correctly even in the face of network failures or node malfunctions.
Distributed Mutual Exclusion
Distributed mutual exclusion (DME) is a crucial concept in distributed systems that addresses the
challenge of coordinating access to shared resources among distributed processes or nodes. In a
distributed environment, multiple processes may attempt to access a shared resource
concurrently, leading to potential conflicts and inconsistencies. DME ensures that only one
process can access a critical section of code or resource at any given time, preventing race
conditions and ensuring data integrity.
Requirements of Mutual exclusion Algorithm:
 UNIT -4
• No Deadlock: Two or more site should not endlessly wait for any message that will never
arrive.
• No Starvation: Every site who wants to execute critical section should get an opportunity
to execute it in finite time. Any site should not wait indefinitely to execute critical section
while other site are repeatedly executing critical section
• Fairness: Each site should get a fair chance to execute critical section. Any request to
execute critical section must be executed in the order they are made i.e Critical section
execution requests should be executed in the order of their arrival in the system.
• Fault Tolerance: In case of failure, it should be able to recognize it by itself in order to
continue functioning without any disruption.
Some points are need to be taken in consideration to understand mutual exclusion fully :
1) It is an issue/problem which frequently arises when concurrent access to shared resources by
several sites is involved. For example, directory management where updates and reads to a
directory must be done atomically to ensure correctness.
2) It is a fundamental issue in the design of distributed systems.
3) Mutual exclusion for a single computer is not applicable for the shared resources since it
involves resource distribution, transmission delays, and lack of global information.

Solution to distributed mutual exclusion: As we know shared variables or a local kernel can not
be used to implement mutual exclusion in distributed systems. Message passing is a way to
implement mutual exclusion. Below are the three approaches based on message passing to
implement mutual exclusion in distributed systems:
1. Token Based Algorithm:
• A unique token is shared among all the sites.
• If a site possesses the unique token, it is allowed to enter its critical section
• This approach uses sequence number to order requests for the critical section.
• Each requests for critical section contains a sequence number. This sequence number is
used to distinguish old and current requests.
• This approach insures Mutual exclusion as the token is unique
Example : Suzuki–Kasami Algorithm
2. Non-token based approach:
• A site communicates with other sites in order to determine which sites should execute
critical section next. This requires exchange of two or more successive round of messages
among sites.
• This approach use timestamps instead of sequence number to order requests for the
critical section.
 UNIT -4
• When ever a site make request for critical section, it gets a timestamp. Timestamp is also
used to resolve any conflict between critical section requests.
• All algorithm which follows non-token based approach maintains a logical clock. Logical
clocks get updated according to Lamport’s scheme
Example : Ricart–Agrawala Algorithm
3. Quorum based approach:
• Instead of requesting permission to execute the critical section from all other sites, Each
site requests only a subset of sites which is called a quorum.
• Any two subsets of sites or Quorum contains a common site.
• This common site is responsible to ensure mutual exclusion
Example : Maekawa’s Algorithm
Election algorithm
An election algorithm in distributed systems is a method used to select a coordinator or leader
among a group of distributed processes or nodes. This coordinator is responsible for managing
certain tasks, making decisions, or facilitating communication among the nodes. Election
algorithms ensure that there is one active leader at any given time, which helps maintain
consistency and coordination in distributed systems.
Why Election Algorithms Are Needed
In distributed systems, there may not be a central authority or single point of control. Nodes
operate independently and can fail, so an election algorithm is necessary to:
• Determine which node will act as the leader.
• Recover from failures when the current leader becomes unavailable.
• Ensure that all nodes agree on who the leader is.
Key Properties of Election Algorithms
1. Uniqueness: Only one leader should be elected at a time.
2. Termination: The algorithm must eventually complete and elect a leader.
3. Fault Tolerance: The system should be able to elect a new leader if the current leader fails.
4. Fairness: Every process that wants to become a leader should eventually get the
opportunity to do so.
Common Election Algorithms
Several algorithms are commonly used for electing a leader in distributed systems. Here are a few
well-known ones:
1. Bully Algorithm
How It Works:
 UNIT -4
• Each node in the system has a unique identifier (ID).
• When a node detects that the current leader has failed (e.g., through timeouts), it initiates
an election.
• The initiating node sends an election message to all nodes with higher IDs.
• If a node with a higher ID responds, the election is canceled; otherwise, the initiating node
becomes the leader.
Steps:
1. A node detects that the leader is down.
2. It sends an "election" message to all nodes with higher IDs.
3. If no one responds, the initiating node declares itself the leader and sends a "leader"
message to all nodes.
4. If a higher-ID node responds, it will initiate its election process, and the lower-ID nodes will
stop their election attempts.
Example:
• Nodes A (ID 1), B (ID 2), and C (ID 3) are in the system.
• If node A detects that C (the leader) has failed, it sends an election message to B.
• If B doesn’t respond, A declares itself the leader; if B responds, it starts its own election.
2. Ring Algorithm
How It Works:
• Nodes are arranged in a logical ring, and each node knows its neighbors.
• When a node wants to start an election, it sends an election message around the ring.
• Each node that receives the message compares its ID with the ID in the message. If its ID is
higher, it replaces the ID in the message and forwards it.
• When the message comes back to the original sender, the node with the highest ID is
declared the leader.
Steps:
1. A node starts the election by sending an election message with its ID.
2. Each node compares its ID with the received ID:
o If its ID is higher, it replaces the ID and forwards the message.
o If its ID is lower, it simply forwards the message.
3. The message circulates the ring until it returns to the initiating node.
4. The highest ID is declared the leader.
Example:
 UNIT -4
• Nodes A (ID 1), B (ID 2), and C (ID 3) are in a ring.
• If A starts an election with ID 1, it sends the message around:
o B sees ID 1, replaces it with 2, and sends it to C.
o C sees ID 2, replaces it with 3, and sends it back to A.
• When A receives the message, it knows that C is the leader (ID 3).
3. Leader Election Using Randomized Algorithms
How It Works:
• Each node generates a random number when an election is needed.
• Nodes then communicate with each other, and the one with the highest random number
becomes the leader.
Steps:
1. Nodes generate random numbers and share them with others.
2. Each node keeps track of the highest number received.
3. When a node identifies it has the highest number, it declares itself the leader.
Example:
• Nodes A, B, and C generate random numbers: A (3), B (7), C (5).
• B has the highest number, so it becomes the leader.
Challenges in Election Algorithms
1. Network Partitions: If the network is partitioned, multiple nodes might think they are the
leader. Algorithms need to handle such cases to prevent conflicts.
2. Message Delays: Delays in message passing can cause nodes to misinterpret the state of
the system, affecting election results.
3. Failure Handling: Algorithms must be robust enough to handle node failures gracefully and
elect a new leader when needed.
4. Scalability: As the number of nodes increases, the efficiency of the election algorithm
becomes crucial to prevent excessive messaging and delays.
 UNIT -4
What is a Distributed Transaction?
A distributed transaction spans multiple systems, ensuring all operations either succeed or fail
together, crucial for maintaining data integrity and consistency across diverse and geographically
separated resources in modern computing environments.
What is the need for a Distributed Transaction?
The need for distributed transactions arises from the requirements to ensure data
consistency and reliability across multiple independent systems or resources in a distributed
computing environment. Specifically:
• Consistency: Ensuring that all changes made as part of a transaction are committed or
rolled back atomically, maintaining data integrity.
• Isolation: Guaranteeing that concurrent transactions do not interfere with each other,
preserving data integrity and preventing conflicts.
• Durability: Confirming that committed transactions persist even in the event of system
failures, ensuring reliability.
• Atomicity: Ensuring that either all operations within a transaction are completed
successfully or none of them are, avoiding partial updates that could lead to
inconsistencies.
Working of Distributed Transactions
The working of Distributed Transactions is the same as that of simple transactions but the
challenge is to implement them upon multiple databases. Due to the use of multiple nodes or
database systems, there arises certain problems such as network failure, to maintain the
availability of extra hardware servers and database servers. For a successful distributed
transaction the available resources are coordinated by transaction managers.
 UNIT -4

Working of Distributed Transactions

Below are some steps to understand how distributed transactions work:
Step 1: Application to Resource – Issues Distributed Transaction
The first step is to issue that distributed transaction. The application initiates the transaction by
sending the request to the available resources. The request consists of details such as operations
that are to be performed by each resource in the given transaction.
Step 2: Resource 1 to Resource 2 – Ask Resource 2 to Prepare to Commit
Once the resource receives the transaction request, resource 1 contacts resource 2 and asks
resource 2 to prepare the commit. This step makes sure that both the available resources are able
to perform the dedicated tasks and successfully complete the given transaction.
Step 3: Resource 2 to Resource 1 – Resource 2 Acknowledges Preparation
After the second step, Resource 2 receives the request from Resource 1, it prepares for the
commit. Resource 2 makes a response to resource 1 with an acknowledgment and confirms that
it is ready to go ahead with the allocated transaction.
Step 4: Resource 1 to Resource 2 – Ask Resource 2 to Commit
Once Resource 1 receives an acknowledgment from Resource 2, it sends a request to Resource 2
and provides an instruction to commit the transaction. This step makes sure that Resource 1 has
completed its task in the given transaction and now it is ready for Resource 2 to finalize the
operation.
Step 5: Resource 2 to Resource 1 – Resource 2 Acknowledges Commit
 UNIT -4
When Resource 2 receives the commit request from Resource 1, it provides Resource 1 with a
response and makes an acknowledgment that it has successfully committed the transaction it
was assigned to. This step ensures that Resource 2 has completed its task from the operation and
makes sure that both the resources have synchronized their states.
Step 6: Resource 1 to Application – Receives Transaction Acknowledgement
Once Resource 1 receives an acknowledgment from Resource 2, Resource 1 then sends an
acknowledgment of the transaction back to the application. This acknowledgment confirms that
the transaction that was carried out among multiple resources has been completed successfully.
Types of Distributed Transactions
Distributed transactions involve coordinating actions across multiple nodes or resources to
ensure atomicity, consistency, isolation, and durability (ACID properties). Here are some common
types and protocols:
1. Two-Phase Commit Protocol (2PC)
This is a classic protocol used to achieve atomicity in distributed transactions.
• It involves two phases: a prepare phase where all participants agree to commit or abort the
transaction, and a commit phase where the decision is executed synchronously across all
participants.
• 2PC ensures that either all involved resources commit the transaction or none do, thereby
maintaining atomicity.
2. Three-Phase Commit Protocol (3PC)
3PC extends 2PC by adding an extra phase (pre-commit phase) to address certain failure
scenarios that could lead to indefinite blocking in 2PC.
• In 3PC, participants first agree to prepare to commit, then to commit, and finally to
complete or abort the transaction.
• This protocol aims to reduce the risk of blocking seen in 2PC by introducing an additional
decision-making phase.
3. XA Transactions
XA (eXtended Architecture) Transactions are a standard defined by The Open Group for
coordinating transactions across heterogeneous resources (e.g., databases, message queues).
• XA specifies interfaces between a global transaction manager (TM) and resource managers
(RMs).
• The TM coordinates the transaction’s lifecycle, ensuring that all participating RMs either
commit or rollback the transaction atomically.
Implementing Distributed Transactions
Below is how distributed transactions is implemented:
• Transaction Managers (TM):
 UNIT -4
o Transaction Managers are responsible for coordinating and managing transactions
across multiple resource managers (e.g., databases, message queues).
o TMs ensure that transactions adhere to ACID properties (Atomicity, Consistency,
Isolation, Durability) even when involving disparate resources.
• Resource Managers (RM):
o Resource Managers are responsible for managing individual resources (e.g.,
databases, file systems) involved in a distributed transaction.
o RMs interact with the TM to prepare for committing or rolling back transactions
based on the TM’s coordination.
• Coordination Protocols:
o Implementations of distributed transactions often rely on coordination protocols
like 2PC, 3PC, or variants such as Paxos and Raft for consensus.
o These protocols ensure that all participants in a transaction reach a consistent
decision regarding commit or rollback.
Advantages of Distributed Transactions
Below are the advantages of distributed transaction:
• Data Consistency: Data Consistency is being provided across multiple resources by
distributed transactions. Various Operations are being coordinated across multiple
database resources. This makes sure that system remains in a consistent state even in
case of any type of failure.
• Fault Tolerance: Distributed systems can handle faults and ensure proper transactions. If
the participating resource fails during the execution of the transaction the transaction can
be then rolled back on alternate resources and completed successfully.
• Guarantees Transactions: Distributed systems guarantee the transaction. It provides
features such as durability and isolation. The durability makes sure that if any transaction
is committed, the changes last even if any failures occur.
Applications Distributed Transactions
Below are the applications of Distributed Transaction:
• Enterprise Resource Planning (ERP) Systems: ERP systems consist of departments
within one organization. Therefore distributed transactions are used here in order to
maintain transactions from various modules such as sales, inventory, finance, and human
resources management.
• Cloud Computing: Distributed transactions are being used in cloud-based applications.
Transactions can be done with the help of multiple data sources and ensure that data
updates and operations that are performed consistently.
• Healthcare Systems: Healthcare systems make use of Distributed transactions when
coordinating patient records, scheduling appointments for patients, and managing the
 UNIT -4
billing systems. Distributed transactions maintain data consistency and performance in
healthcare systems.
What is Group Communication in Distributed Systems?
Group communication in distributed systems refers to the process where multiple nodes or
entities communicate with each other as a group.
• Instead of sending messages to individual recipients, group communication allows a
sender to transmit information to all members of a group simultaneously.
• This method is essential for coordinating actions, sharing data, and ensuring that all
participants in the system are informed and synchronized. It’s particularly useful in
scenarios like collaborative applications and real-time updates.
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
 UNIT -4
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.
 UNIT -4
• 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.
Concurrency Control in Distributed Transactions
Concurrency control mechanisms provide us with various concepts & implementations to ensure
the execution of any transaction across any node doesn’t violate ACID or BASE (depending on
database) properties causing inconsistency & mixup of data in the distributed systems.
 UNIT -4
Transactions in the distributed system are executed in “sets“, every set consists of various sub-
transactions. These sub-transactions across every node must be executed serially to maintain
data integrity & the concurrency control mechanisms do this serial execution.
Types of Concurrency Control Mechanisms
There are 2 types of concurrency control mechanisms as shown below diagram:

Types of Concurrency Control Mechanism

Pessimistic Concurrency Control (PCC)
The Pessimistic Concurrency Control Mechanisms proceeds on assumption that, most of
the transactions will try to access the same resource simultaneously. It’s basically used to
prevent concurrent access to a shared resource and provide a system of acquiring a Lock on the
data item before performing any operation.
Optimistic Concurrency Control (OCC)
The problem with pessimistic concurrency control systems is that, if a transaction acquires a
lock on a resource so that no other transactions can access it. This will result in reducing
concurrency of the overall system.
The Optimistic Concurrency control techniques proceeds on the basis of assumption that, 0 or
very few transactions will try to access a certain resource simultaneously. We can describe a
system as FULLY OPTIMISTIC, if it uses No-Locks at all & checks for conflicts at commit time. It
has following 4-phases of operation:
• Read Phase: When a transaction begins, it reads the data while also logging the time-
stamp at which data is read to verify for conflicts during the validation phase.
• Execution Phase: In this phase, the transaction executes all its operation like create, read,
update or delete etc.
 UNIT -4
• Validation Phase: Before committing a transaction, a validation check is performed to
ensure consistency by checking the last_updated timestamp with the one recorded
at read_phase. If the timestamp matches, then the transaction will be allowed to be
committed and hence proceed with the commit phase.
• Commit phase: During this phase, the transactions will either be committed or aborted,
depending on the validation check performed during previous phase. If the timestamp
matches, then transactions are committed else they’re aborted.
Pessimistic Concurrency Control Methods
Following are the four Pessimistic Concurrency Control Methods:
Isolation Level
The isolation levels are defined as a degree to which the data residing in Database must be
isolated by transactions for modification. Because, if some transactions are operating on some
data let’s say transaction – T1 & there comes another transaction – T2 and modifies it further
while it was under operation by transaction T1 this will cause unwanted inconsistency problems.
Methods provided in this are: Read-Uncomitted, Read-Comitted, Repeatable Read & Serializable.
Two-Phase Locking Protocol
The two-phase locking protocol is a concurrency technique used to manage locks on data items
in database. This technique consists of 2 phases:
Growing Phase: The transaction acquires all the locks on the data items that’ll be required to
execute the transaction successfully. No locks will be realease in this phase.
Shrinking Phase: All the locks acquired in previous phase will be released one by one and No New
locks will be acquired in this phase.
Distributed Lock Manager
A distributed lock a critical component in the distributed transaction system, which co-ordinates
the lock acquiring, and releasing operations in the transactions. It helps in synchronizing the
transaction and their operation so that data integrity is maintained.

Distributed Lock Manager (DLM)

Multiple Granularity Lock
A lock can be acquired at various granular level like: table level, row/record level, page level or
any other resource’s level. In transaction system a transaction can lock a whole table, or a
 UNIT -4
specific row while performing some changes on it. This lock acquiring when done by various
transactions simultaneously, this phenomena is called as multiple granularity locking.
Optimistic Concurrency Control Methods
Below are four Optimistic Concurrency Control Methods:
Timestamp Based (OCC)
In a timestamp based concurrency technique, each transaction in the system is assigned a
unique timestamp which is taken as soon as the transaction begins, and its verified again during
the commit phase. If there’s new updated timestamp from a different transaction then based on
some policy defined by the System Adminstrator the transaction will either be restarted or
aborted. But if the times stamp is same & never modified by any other transaction then it will be
committed.
Example: Let’s say we have two transaction T1 and T2, they operate on data item – A. The
Timestamp concurrency technique will keep track of the timestamp when the data was accessed
by transaction T1 first time.
Data item and Initial_timestamp of
Transaction operation Most_recent_Timestamp data item (A)

T1 Read(A) 12:00PM 12:00PM

T2 Write(A) 12:15PM 12:00PM

T1 Write(A) 12:30PM 12:00PM

Now, let’s say this transaction T1 is about to commit, before committing, it will check the initial
timestamp with the most recent timestamp. In our case, the transaction T1 won’t be committed
because a write operations by transaction T2 was performed.

Distributed System – Types of Distributed Deadlock

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

Deadlock
 UNIT -4
A Distributed System is a Network of Machines that can exchange information with each other
through Message-passing. It can be very useful as it helps in resource sharing. In such an
environment, if the sequence of resource allocation to processes is not controlled, a deadlock
may occur. In principle, deadlocks in distributed systems are similar to deadlocks in
centralized systems. Therefore, the description of deadlocks presented above holds good both for
centralized and distributed systems. However, handling of deadlocks in distributed systems is
more complex than in centralized systems because the resources, the processes, and other
relevant information are scattered on different nodes of the system.
Three commonly used strategies to handle deadlocks are as follows:
• Avoidance: Resources are carefully allocated to avoid deadlocks.
• Prevention: Constraints are imposed on the ways in which processes request resources in
order to prevent deadlocks.
• Detection and recovery: Deadlocks are allowed to occur and a detection algorithm is
used to detect them. After a deadlock is detected, it is resolved by certain means.
Types of Distributed Deadlock:
There are two types of Deadlocks in Distributed System:
Resource Deadlock: A resource deadlock occurs when two or more processes wait permanently
for resources held by each other.
• A process that requires certain resources for its execution, and cannot proceed until it has
acquired all those resources.
• It will only proceed to its execution when it has acquired all required resources.
• It can also be represented using AND condition as the process will execute only if it has all
the required resources.
• Example: Process 1 has R1, R2, and requests resources R3. It will not execute if any one of
them is missing. It will proceed only when it acquires all requested resources i.e. R1, R2,
and R3.
 UNIT -4

figure 1: Resource Deadlock

Communication Deadlock: On the other hand, a communication deadlock occurs among a set
of processes when they are blocked waiting for messages from other processes in the set in order
to start execution but there are no messages in transit between them. When there are no
messages in transit between any pair of processes in the set, none of the processes will ever
receive a message. This implies that all processes in the set are deadlocked. Communication
deadlocks can be easily modeled by using WFGs to indicate which processes are waiting to
receive messages from which other processes. Hence, the detection of communication
deadlocks can be done in the same manner as that for systems having only one unit of each
resource type.
• In Communication Model, a Process requires resources for its execution and proceeds
when it has acquired at least one of the resources it has requested for.
• Here resource stands for a process to communicate with.
• Here, a Process waits for communicating with another process in a set of processes. In a
situation where each process in a set, is waiting to communicate with another process
which itself is waiting to communicate with some other process, this situation is called
communication deadlock.
• For 2 processes to communicate, each one should be in the unblocked state.
• It can be represented using OR conditions as it requires at least one of the resources to
continue its Process.
• Example: In a Distributed System network, Process 1 is trying to communicate with
Process 2, Process 2 is trying to communicate with Process 3 and Process 3 is trying to
 UNIT -4
communicate with Process 1. In this situation, none of the processes will get unblocked
and a communication deadlock occurs.

figure 2: Communication Deadlock

Deadlock handling strategies in distributed systems

Deadlock handling in distributed systems is a critical aspect of concurrency control. A deadlock
occurs when two or more processes are unable to proceed because each is waiting for resources
held by the other. This situation can severely impact the performance and reliability of distributed
systems. To address deadlocks, various strategies can be employed. Below are the primary
deadlock handling strategies used in distributed systems:
1. Deadlock Prevention
Deadlock prevention aims to ensure that the system never enters a deadlock state by making
certain that at least one of the necessary conditions for deadlock cannot hold. These conditions
are:
• Mutual Exclusion: At least one resource must be held in a non-shareable mode.
• Hold and Wait: A process holding at least one resource is waiting to acquire additional
resources.
• No Preemption: Resources cannot be forcibly taken from a process holding them.
• Circular Wait: A circular chain of processes exists, where each process is waiting for a
resource held by the next process in the chain.
Prevention Strategies:
• Eliminating Mutual Exclusion: Making resources sharable where possible.
 UNIT -4
• Eliminating Hold and Wait: Requiring processes to request all needed resources at once.
• Allowing Preemption: Allowing resources to be preempted from processes under certain
conditions.
• Eliminating Circular Wait: Imposing a total order on resource types and requiring
processes to request resources in that order.
2. Deadlock Avoidance
Deadlock avoidance strategies ensure that the system will never enter a deadlock state by
analyzing the resource allocation and making decisions based on the current state of the system.
Key Techniques:
• Banker’s Algorithm: This algorithm checks if granting a resource request will leave the
system in a safe state (i.e., a state where all processes can complete without entering a
deadlock). If it is safe, the request is granted; otherwise, it is denied until it can be safely
allocated.
• Resource Allocation Graph: In this approach, a directed graph is maintained where nodes
represent processes and resources, and edges represent requests and allocations. A
deadlock is detected if there is a cycle in the graph. The system can grant resource
requests only if it does not create a cycle.
3. Deadlock Detection
In deadlock detection, the system allows deadlocks to occur but has mechanisms to detect and
resolve them.
Deadlock Detection Algorithms:
• Wait-for Graph: This graph-based method tracks which processes are waiting for which
resources. If a cycle is detected in the wait-for graph, a deadlock exists.
• Resource Allocation Graph: Similar to the above, but it represents the allocation of
resources. If a cycle is found, processes involved in the cycle are in a deadlock.
Resolution: Once a deadlock is detected, the system needs to resolve it, often through one of the
following methods:
• Process Termination: Terminate one or more processes involved in the deadlock. This can
be done based on various criteria (e.g., priority, how long the process has been running, or
resource consumption).
• Resource Preemption: Forcefully take resources from one or more processes and
allocate them to others to resolve the deadlock. This approach can lead to a situation
where resources are repeatedly preempted, causing starvation.
4. Deadlock Recovery
Deadlock recovery involves actions taken after a deadlock has been detected to restore the
system to a normal state.
Recovery Techniques:
 UNIT -4
• Rollback: In this technique, affected processes are rolled back to a previously saved state
(checkpoint) to allow them to restart without holding resources that contribute to the
deadlock.
• Process Restart: Processes involved in a deadlock are restarted, allowing them to re-
execute and hopefully avoid the same deadlock scenario.

Transaction recovery in distributed systems

Transaction recovery in distributed systems is essential for ensuring data integrity and
consistency in the face of failures, such as crashes, network issues, or hardware malfunctions.
When a transaction is executed in a distributed environment, it often spans multiple nodes or
databases. If a failure occurs during its execution, it is crucial to restore the system to a
consistent state. This process is guided by the ACID properties (Atomicity, Consistency, Isolation,
Durability) of transactions.
Key Concepts of Transaction Recovery
1. Atomicity: Transactions must be all-or-nothing. If a transaction fails, all changes made
during its execution must be undone.
2. Durability: Once a transaction is committed, its effects are permanent, even in the event
of a system failure.
3. Log File: A persistent record of all transactions is maintained to facilitate recovery. This log
helps to track the changes made by transactions, including both committed and
uncommitted changes.
Types of Failures
1. Transaction Failures: Occur when a transaction cannot complete due to errors, such as
data validation failures.
2. System Failures: Result from hardware or software malfunctions that cause the system to
crash.
3. Media Failures: Involve the loss of data due to issues like disk failures, leading to data
corruption.
Recovery Techniques
1. Undo/Redo Logging
o Log Structure: Each transaction writes its actions to a log before modifying the
database. The log contains entries for both undo (to roll back changes) and redo (to
reapply changes) operations.
o Recovery Process:
▪ Undo Phase: For transactions that were active (not committed) when the
failure occurred, their changes are rolled back to restore the previous state.
 UNIT -4
▪ Redo Phase: Committed transactions that may not have been fully written to
the database are reapplied based on the log.
o Example:
▪ If Transaction T1 modifies data and then fails, the system will use the log to
undo its changes.
▪ If Transaction T2 commits but the system fails before T2's changes are saved,
the redo phase will apply T2’s changes during recovery.
2. Two-Phase Commit Protocol (2PC)
The Two-Phase Commit protocol is crucial for ensuring atomicity in distributed transactions
involving multiple nodes.
o Phase 1: Prepare Phase:
▪ The coordinator node sends a "prepare" request to all participant nodes.
▪ Each participant node executes the transaction up to the point of
commitment and responds with either "vote commit" or "vote abort."
o Phase 2: Commit Phase:
▪ If all participants vote to commit, the coordinator sends a "commit" message
to all nodes.
▪ If any participant votes to abort, the coordinator sends an "abort" message,
and all nodes roll back to their previous state.
o Failure Handling: The 2PC protocol helps ensure that either all nodes commit or
none do, maintaining atomicity across the distributed system. However, it may
suffer from blocking issues if the coordinator fails.
3. Three-Phase Commit Protocol (3PC)
An extension of the 2PC protocol designed to reduce the chances of blocking.
o Phase 1: Prepare Phase: Similar to 2PC, the coordinator asks participants to
prepare for commitment.
o Phase 2: Pre-Commit Phase: If all participants respond positively, the coordinator
sends a "pre-commit" message.
o Phase 3: Commit Phase: After receiving the "pre-commit," participants finalize their
commit. The coordinator then sends a "commit" message.
o Advantages: 3PC introduces an additional phase that allows participants to decide
whether to commit or abort based on their state, reducing blocking scenarios
compared to 2PC.
4. Checkpointing
Checkpointing involves saving the state of a system at regular intervals. It allows the system to
recover to the last saved state instead of starting from the very beginning after a failure.
 UNIT -4
o Process: During normal operation, the system periodically creates checkpoints,
which include the state of all transactions and resources at that point in time.
o Recovery: In the event of a failure, the system can roll back to the most recent
checkpoint and reprocess transactions that were active after the checkpoint.
5. Distributed Consensus Algorithms
Algorithms like Paxos and Raft are used to achieve consensus among distributed nodes regarding
the state of transactions. These algorithms help ensure that all nodes agree on the outcome of a
transaction, enhancing reliability and consistency.
Summary of Recovery Steps
1. Identify Active Transactions: Determine which transactions were active at the time of
failure using log files.
2. Undo Incomplete Transactions: Roll back the changes made by incomplete transactions
using undo logging.
3. Redo Committed Transactions: Reapply changes from committed transactions that may
not have been saved due to the failure.
4. Use Protocols for Distributed Transactions: Implement Two-Phase Commit or Three-
Phase Commit protocols for coordinating commits across multiple nodes.
5. Leverage Checkpoints: Utilize checkpoints to minimize the recovery time by allowing the
system to roll back to a known good state.
What is Replication in Distributed System?
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.
What is Replication in Distributed Systems?
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:
o 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.
o Users can still access data or services from other healthy replicas, thereby
improving overall system availability.
 UNIT -4
• Improved Reliability:
o Replication increases reliability by reducing the likelihood of a single point of failure.
o If one replica fails, others can continue to serve requests, maintaining system
operations without interruption.
o This redundancy ensures that critical data or services are consistently accessible.
• Reduced Latency:
o Replicating data closer to users or clients can reduce latency, or the delay in data
transmission.
o This is particularly important in distributed systems serving users across different
geographic locations.
o Users can access data or services from replicas located nearer to them, improving
response times and user experience.
• Scalability:
o Replication supports scalability by distributing the workload across multiple nodes.
o As the demand for resources or services increases, additional replicas can be
deployed to handle increased traffic or data processing requirements.
o This elasticity ensures that distributed systems can efficiently handle varying
workloads.
Types of Replication in Distributed Systems
Below are the types of replication in distributed systems:
1. 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.
• Advantages:
o Strong Consistency: Since all updates go through the primary replica, read
operations can be served with strong consistency guarantees.
o Fault Tolerance: If the primary replica fails, one of the backup replicas can be
promoted to become the new primary, ensuring continuous availability.
• Disadvantages:
o Latency for Reads: Read operations might experience latency because they might
need to wait for updates to propagate from the primary to the backup replicas.
o Resource Utilization: Backup replicas are often idle unless a failover occurs, which
can be seen as inefficient resource utilization.
• Use Cases:
 UNIT -4
o Primary-Backup replication is commonly used in scenarios where strong
consistency and fault tolerance are critical, such as in relational databases where
data integrity and availability are paramount.
2. 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).
• Advantages:
o Increased Write Throughput: Multiple replicas can handle write requests
concurrently, improving overall system throughput.
o Lower Write Latency: Writes can be processed locally at each replica, reducing the
latency compared to centralized primary-backup models.
o Fault Tolerance: Even if one replica fails, other replicas can continue to accept
writes and serve read operations.
• Disadvantages:
o Conflict Resolution: Concurrent updates across multiple primaries can lead to
conflicts that need to be resolved, typically using techniques like conflict detection
and resolution algorithms (e.g., timestamp ordering or version vectors).
o Consistency Management: Ensuring consistency across all replicas can be
complex, especially in distributed environments with network partitions or
communication delays.
• Use Cases:
o Multi-Primary replication is suitable for applications requiring high write throughput
and low latency, such as collaborative editing systems or distributed databases
supporting globally distributed applications.
3. 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.
• Advantages:
o Strong Consistency: Chain replication can provide strong consistency guarantees
because updates propagate linearly through the chain.
o Fault Tolerance: If a node fails, the chain can still operate as long as there are
enough operational nodes to maintain the chain structure.
• Disadvantages:
o Performance Bottlenecks: The overall performance of the system can be limited by
the slowest node in the chain, as each update must traverse through every node in
sequence.
 UNIT -4
o Latency: The length of the chain and the propagation time between nodes can
introduce latency for updates.
• Use Cases:
o Chain replication is often used in systems where strong consistency and fault
tolerance are critical, such as in distributed databases or replicated state machines
where linearizability is required.
4. 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.
• Advantages:
o Scalability: Distributed replication supports horizontal scalability by allowing
replicas to be added or removed dynamically as workload demands change.
o Fault Tolerance: Redundancy across distributed replicas enhances fault tolerance
and system reliability.
• Disadvantages:
o Consistency Challenges: Ensuring consistency across distributed replicas can be
challenging, especially in environments with high network latency or partition
scenarios.
o Complexity: Managing distributed replicas requires robust synchronization
mechanisms and conflict resolution strategies to maintain data integrity.
• Use Cases:
o Distributed replication is commonly used in large-scale distributed systems, cloud
computing environments, and content delivery networks (CDNs) to improve
scalability, fault tolerance, and performance.
5. Synchronous vs. Asynchronous Replication
• Description:
o 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.
o 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.
• Advantages and Disadvantages:
 UNIT -4
o Synchronous: Provides strong consistency and ensures that all replicas are up-to-
date, but can increase latency and vulnerability to failures.
o Asynchronous: Reduces latency and improves performance but sacrifices
immediate consistency and may require additional mechanisms to handle potential
data inconsistencies.
• Use Cases:
o Synchronous replication is suitable for applications where strong consistency and
data integrity are paramount, such as financial transactions or critical database
operations.
o Asynchronous replication is often used in scenarios where lower latency and higher
throughput are prioritized, such as in content distribution or non-critical data
replication.