Module 4

1. Key features of global scheduling algorithm in distributed systems

A global scheduling algorithm in distributed systems is responsible for deciding the alloca on of
processes to appropriate processors/nodes across the en re system. Unlike local scheduling, it takes
a system-wide view and aims to achieve op mal resource u liza on, performance, and fairness.
According to the notes, a good global scheduling algorithm must possess the following desirable
features:

1. Fault Tolerance: The algorithm should not stop func oning when system nodes crash or
become temporarily unavailable. It must con nue to operate correctly even if the nodes are
separated by mul ple network hops. This ensures the scheduling service remains available
despite par al system failures.

2. Scalability: The algorithm should work efficiently even as the number of nodes in the system
increases significantly. It queries the workload of all categories in the system and selects the
node with the least configura on load. Load sharing (alloca ng resources among nodes un l
tasks are unaffected) is preferred over strict load balancing.

3. No apriori knowledge about the processes: The algorithm should require minimal prior
informa on from the user about the characteris cs and resource requirements of processes.
Requiring detailed prior knowledge puts extra overhead on users; hence, a good global
scheduler minimizes this dependency.

4. Quick decision-making capability: Scheduling decisions must be made very fast. The algorithm
should provide the best possible (near-op mal) decision in the least amount of me. Heuris c
methods that require less computa onal effort are preferred over exhaus ve mathema cal
programming solu ons, which are too slow for real- me use.

5. Stability: The algorithm must prevent useless migra on of processes. For example, if node N1
is idle and nodes N2 and N3 are overloaded, sending processes to N1 should not cause N1 to
become overloaded and trigger further migra ons back to other nodes. Such ping-pong
migra ons create unnecessary system overhead.

6. Dynamic in nature: Process alloca ons must be made based on the current load of the system
rather than on any pre-planned or sta c condi ons. The scheduler should be able to
dynamically move (migrate) processes from one node to another so that the distribu on
always reflects the real- me system load.
2. Difference between Load balancing and Load Sharing
Aspect Load Balancing Load Sharing

Defini on Evenly distribu ng incoming traffic/tasks Coopera ve distribu on of

across mul ple resources to op mize tasks/workloads among nodes for
u liza on and performance. parallel processing benefits.

Objec ve Op mize resource use, maximize Achieve parallel task execu on,
throughput, minimize response me, improve scalability, enhance
prevent overload. performance via collabora on.

Focus Resource alloca on and management Task execu on and parallelism

among nodes. among nodes.

Methodology Uses algorithms (e.g., Round Robin, Task par oning + coopera ve
Least Connec ons) based on current execu on to split and process tasks
load metrics (CPU, memory, network). in parallel.

Implementa on Uses load balancers to distribute Breaks tasks into smaller units,
requests based on predefined distributes them, and coordinates
algorithms. concurrent processing.

Examples Web servers distribu ng HTTP requests; Hadoop MapReduce; scien fic

cloud VMs. simula ons.

Benefit Enhances reliability, scalability, Improves throughput, accelerates

responsiveness by avoiding bo lenecks. comple on, scales horizontally via
parallelism.

Key Difference Focuses on op mizing resource Emphasizes parallel task execu on

u liza on and avoiding overload. and collabora ve processing.

3. Process migra on
Process migra on is a key mechanism in distributed systems where a process (along with its execu on
state) is transferred from one node (source) to another node (des na on) in the network. It is defined
as the transfer of a process or its execu on state from one computer/server to another within the
network.

Working of Process Migra on: The process is halted on the source node, its complete state (memory
contents, register values, program counter, open files, etc.) is captured and transferred, and execu on
is resumed on the des na on node.

Reasons / Why use Process Migra on

 Dynamic load balancing – moves processes from overloaded to underloaded nodes.

 Accessibility – moves processes away from defec ve or failed nodes.

 System administra on – allows migra on during node maintenance.

 Locality of data – moves the process closer to required data or special resources.
  Mobility – e.g., transferring a process from a hand-held device to a server before
disconnec on.

 Recovery of faults – helps in transac on-based applica ons by stopping, transpor ng, and
resuming the process.

Types of Process Migra on

1. Non Pre-emp ve Migra on: The process is migrated before it starts execu on on the source
node.

2. Pre-emp ve Migra on: The process is migrated a er it has already begun execu on. This is
more costly as the OS must save the en re state (process ID, open files, program counter,
priority, etc.) in the Process Control Block (PCB).

3. Sta c Migra on: The en re process state is moved at once and execu on starts from the point
of suspension.

4. Dynamic / Incremental Migra on: The process state is transferred in stages while the process
is s ll running, reducing down me.

Key Concepts

 Process State, Checkpoin ng, Migra on Overhead, Consistency, Transparency, and Fault
Tolerance.

Steps involved in Process Migra on

1. Selec on of Process for Migra on – Iden fy the process based on load, resource usage, or
fault tolerance needs.

2. Choosing the Des na on Node – Select the best target node considering available resources,
network latency, and current load.

3. Migra ng the Process – Save state, transfer it to the des na on, and resume execu on.

4. Code migra on
Code migra on in distributed systems is the process of transferring so ware code (or part of an
applica on) from one environment/node/server to another. It is analogous to moving belongings from
one house to another and is vital for managing, upda ng, and op mizing applica ons that run across
mul ple interconnected nodes.

Need for Code Migra on

 Dynamic Environment: Allows the system to adapt to frequent changes by moving code as
needed.

 Resource Op miza on: Moves code to nodes with excess capacity for be er workload
balancing.

 System Maintenance and Updates: Enables seamless deployment of updates without major
interrup ons.
  Scaling: Supports dynamic resource alloca on to handle increased traffic and workload.

 Fault Tolerance and Resilience: Helps in quick recovery by migra ng code to healthy nodes.

Types of Code Migra on

1. Pre-emp ve vs Reac ve Migra on

o Pre-emp ve: Code is moved proac vely based on an cipated events (e.g., before
expected peak-hour overload).

o Reac ve: Code is moved in response to actual events (e.g., sudden traffic spike).

2. Horizontal vs Ver cal Migra on

o Horizontal: Code moves between similar nodes/roles (same capabili es).

o Ver cal: Code moves between nodes with different capabili es (e.g., from a less
powerful to a more powerful server).

3. Stateless vs Stateful Migra on

o Stateless: Code has no dependency on previous system state and can be moved easily.

o Stateful: Code depends on current system state/context; requires careful

synchroniza on of state across nodes.

4. Live vs Offline Migra on

o Live: Code is transferred while the system is running and serving requests (minimal
down me but complex).

o Offline: System or component is temporarily shut down before migra on (simpler but
causes service interrup on).

Challenges in Code Migra on

 Complexity of managing heterogeneous distributed environments and ensuring compa bility.

 Maintaining consistency and coherence of shared resources and distributed transac ons.

 Handling par al failures and network par ons with robust error handling and recovery.

 Difficult debugging and troubleshoo ng due to lack of centralized monitoring (relies on

distributed logging).
Module 5

5. Distributed shared memory design issues (any 2)

 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 u lize the es ma on of the block size as words/phrases. The block size might be different
for the various networks.

 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 applica ons that the
DSM system is intended to support.

 Memory coherence and access synchroniza on:

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 u lize some synchroniza on primi ves, semaphores, event count, and so
on.

 Data loca on 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 seman cs being u lized.

 Replacement strategy:
In the local memory of the node is full, a cache miss at the node implies not just a get of the
go en to informa on 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 posi on subs tu on
methodology is addi onally vital in the design of a DSM system.

 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 rela ng 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 u lize an approach to keep away from a situa on generally known as
thrashing.

 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.
6. Replica on, working of replica on and types of replica ons.
Replica on in distributed systems refers to the process of crea ng and maintaining mul ple copies
(replicas) of data, resources, or services across different nodes (computers or servers) within a
network. The primary goal of replica on is to enhance system reliability, availability, and performance
by ensuring that data or services remain accessible even if some nodes fail or become unavailable.

Working of Replica on: When a write/update occurs on one replica, the system automa cally
propagates the changes to other replicas using push-based or pull-based mechanisms. Reads can be
served from any replica (usually the nearest or least-loaded one) to reduce latency. The DSM layer or
replica on manager handles mapping, communica on, and consistency transparently.

Types of Replica ons in Distributed Systems

1. Primary-Backup Replica on (Ac ve-Passive) One primary replica handles all updates (writes),
while backup replicas (passive) maintain copies and synchronize with the primary.

Advantages: Strong consistency; if the primary fails, a backup is promoted to become the new
primary (fault tolerance).

2. Mul -Primary Replica on Mul ple replicas can independently accept updates. Each replica
acts as both client (accep ng updates) and server (propaga ng updates).

Advantages: Increased write throughput, lower write latency, and con nued opera on even
if one replica fails.

3. Chain Replica on Data is replicated sequen ally through a chain of nodes. Each node forwards
updates to the next node in the chain.

Advantages: Strong consistency (updates propagate linearly); fault tolerance as long as

enough nodes remain opera onal.

4. Distributed Replica on Replicas are distributed across nodes in a less structured manner
(geographically or logically). This provides flexibility in large-scale systems.

5. Synchronous vs. Asynchronous Replica on

o Synchronous: Updates are commi ed to all replicas before acknowledging the write
to the client (strong consistency but higher latency).

o Asynchronous: Updates are acknowledged immediately to the client and propagated

later (lower latency but may lead to temporary inconsistencies).

7. Fault tolerance, failure models

Fault tolerance is the ability of a distributed system to con nue func oning correctly even when some
components fail. The goal is to maintain reliability, availability, and correctness despite failures.

Need for Fault Tolerance Distributed systems face failures due to network issues, hardware crashes,
so ware bugs, or power outages. Without fault tolerance, the system may crash, lose data, or become
unavailable. It is achieved through redundancy, replica on, error detec on, and recovery.
Types of Fault Tolerance

1. Hardware Fault Tolerance Deals with failures in physical components (CPU, memory, disk,
network devices). It uses backup hardware so that if one component fails, a duplicate takes
over. Example: RAID systems (mul ple disks), backup servers.

2. So ware Fault Tolerance Handles errors in so ware such as bugs, incorrect outputs, or
run me failures. It uses techniques like checkpoin ng, rollback recovery, and excep on
handling. Example: If a program crashes, the system restores the last saved state and
con nues.

3. System Fault Tolerance A complete system-level approach that combines both hardware and
so ware fault tolerance. It monitors the en re system, stores memory states and program
checkpoints, and automa cally detects and recovers from failures. Example: Cloud systems
that detect failure, switch workload, and recover automa cally.

Process Resilience in Distributed Systems: Process resilience ensures processes con nue execu on
a er failures.

Key concepts:

 Redundancy: Mul ple copies of a process are maintained.

 Process Replica on: A process is duplicated across nodes (Ac ve: all replicas execute
simultaneously; Passive: one primary + backups).

 Failure Detec on: Uses heartbeats and meouts.

 Restart Mechanism: Failed processes are automa cally restarted or replaced.

Recovery in Fault Tolerance Recovery brings the system back to a correct and consistent state a er
failure.

1. Backward Recovery (Rollback Recovery): Rolls back to a previous safe state using checkpoints
(undoes incorrect opera ons).

2. Forward Recovery: Moves forward to a new correct state using error correc on and excep on
handling (no rollback needed).

3. Checkpoin ng: Saves system state at regular intervals (coordinated or uncoordinated).

4. Message Logging: Logs messages exchanged between processes to reconstruct state by

replaying messages.

Failure Models (Types of Failures) The notes imply the following failure models based on the sources
of failures:

 Hardware Failure Model: Physical component crashes (CPU, disk, network).

 So ware Failure Model: Bugs, incorrect outputs, or run me errors in programs.

 Network/Communica on Failure Model: Issues in message passing or connec vity.

 System-Level Failure Model: Combina on of the above, affec ng the en re node or

distributed service.
Module 6

8. Distributed file system, features of distributed file system

A Distributed File System (DFS) is a networked architecture that allows mul ple users and applica ons
to access and manage files across various machines as if they were stored on a local device. Instead of
keeping data on a single server, DFS spreads files across mul ple nodes, improving redundancy,
reliability, and performance through parallel access and simplified data sharing.

Components of DFS

 Loca on Transparency: Achieved through the namespace component (files appear under one
logical “DFS root”).

 Redundancy: Achieved through the file replica on component (mul ple copies of data).

These components together improve data availability during failures and heavy load. (Note: Both
components are not mandatory; they can be used independently.)

Features of Distributed File System

1. Transparency

o Structure transparency: Client need not know the number or loca on of file servers
and storage devices.

o Access transparency: Local and remote files are accessed in exactly the same way.

o Naming transparency: File name gives no hint of its loca on and remains unchanged
even when moved.

o Replica on transparency: Mul ple copies and their loca ons are completely hidden
from the user.

2. User Mobility

o Automa cally brings the user’s home directory to the node where the user logs in.

o This enables users to work seamlessly from any node in the system without manual
file copying or reconfigura on.

3. Performance

o Should be comparable to a centralized file system (includes CPU me + secondary

storage access + network access me).

o Mul ple file servers are provided to achieve high performance, adaptability, and
dependability under varying loads.

4. Simplicity and Ease of Use

o User interface should be simple with a small number of commands.

o This reduces the learning curve and makes file opera ons intui ve even for non-
technical users.
 5. High Availability

o Con nues working despite par al failures (link failure, node failure, or storage drive
crash).

o Achieved by using different and independent file servers for controlling independent
storage devices.

6. Scalability

o Easily grows when new machines are added or networks are joined, without
substan al service disrup on.

o The system is designed to handle increasing numbers of nodes and users efficiently as
the network expands over me.

7. Data Integrity

o Ensures concurrent access by mul ple users is properly synchronized using

concurrency control and atomic transac ons.

o Prevents data corrup on or inconsistency when many users compete for the same
shared file.

8. Security

o Protects data from unauthorized and unwanted access.

o Users can fully trust that their private informa on remains confiden al through
implemented security mechanisms.

9. File caching
File Caching in Distributed File Systems is a technique that temporarily stores frequently accessed files
(or parts of files) in main memory or local disks of clients/servers. This greatly improves I/O
performance because repeated requests for the same file are served locally, elimina ng network
transfer and reducing disk access. Caching performance depends on the locality of file access pa erns
and also helps in reliability and scalability.

Types of File Caching Implementa on

1. Client-side Caching: The client machine stores a local copy of frequently accessed files and
checks if the local copy is up-to-date before using it.

This approach is highly effec ve for users who repeatedly access the same files from the same
client machine, greatly minimizing repeated network calls.

2. Server-side Caching: The server stores frequently accessed files in memory or on local disks
and serves requests directly from cache instead of accessing the disk.

It is par cularly useful when mul ple clients access the same popular files, as the server can
serve them quickly without repeated disk I/O.
 3. Distributed Caching: The file cache is spread across mul ple servers or nodes; the system
checks the cache and returns the file from the nearest server.

This provides be er scalability and fault tolerance by distribu ng load across caches and
reducing dependency on a single server.

Advantages of File Caching

1. Improved Performance: By reducing network traffic and minimizing disk access, file caching
can significantly improve the performance of distributed file systems.

2. Reduced Latency: File caching can reduce latency by allowing files to be accessed more quickly
without the need for network access or disk access.

3. Be er Resource U liza on: File caching allows frequently accessed files to be stored in
memory or on local disks, reducing the need for network or disk access and improving resource
u liza on.

9. A global e-commerce pla orm like Amazon needs to manage petabytes of

product data, user ac vity logs, and transac on records across distributed data
centres. The system must tolerate frequent hardware failures, scale seamlessly
with increasing demand, and provide fast access to data for users across
different regions. Using the concept of scalable distributed file systems, Apply
the concept of scalable file systems to discuss the support provided by the
Google File System (GFS) for such requirements. (Similar ques on but different
scenario)

A global e-commerce pla orm like Amazon handles petabytes of product data, user logs, and
transac on records across distributed data centres. It requires a scalable distributed file system that
tolerates frequent hardware failures, scales seamlessly, and provides fast regional access. The Google
File System (GFS) is an excellent example that fully supports these requirements.

1. High Availability & Fault Tolerance (Handling Frequent Hardware Failures)

GFS is explicitly designed for environments where hardware failures are common (commodity
hardware).

 It uses redundancy through automa c file replica on (typically 3 replicas of each 64 MB

chunk stored on different chunkservers).

 If a chunkserver or disk fails, the master server detects it and triggers re-replica on from
surviving replicas.

 This matches the high availability feature of DFS: the system con nues opera ng despite
link, node, or storage failures.
  Replica on transparency ensures users and applica ons never see which replicas are being
used or when re-replica on occurs.

2. Scalability (Seamless Scaling with Increasing Demand)

GFS was built to handle petabyte-scale data and thousands of clients.

 New chunkservers can be added dynamically without disrup ng service, suppor ng the
scalability feature of DFS.

 Files are divided into fixed-size chunks stored across many independent chunkservers,
allowing linear scaling simply by adding more machines.

 The master server maintains only metadata (not data), so it does not become a bo leneck
even as the system grows to thousands of nodes.

 This enables the e-commerce pla orm to scale storage and processing capacity effortlessly
as traffic and data volume increase.

3. Performance & Fast Access (Low-Latency Access Across Regions)

GFS delivers high throughput for large sequen al reads and writes, which is ideal for logs and
analy cs.

 Performance is comparable to (or be er than) centralized systems because of intelligent

client-side and server-side file caching.

 Clients cache frequently accessed chunks locally, reducing network traffic and latency for
repeated reads.

 Chunk replicas are placed considering network topology, so users in different regions are
o en served from the nearest replica (access transparency and loca on transparency).

 The system hides distribu on complexity, giving the illusion of a single fast file system.

4. Other Suppor ng DFS Features in GFS

 Transparency (structure, naming, replica on): Users access files via a simple namespace
without knowing physical loca ons or replica details.

 Data Integrity: GFS uses checksums and version numbers to detect and handle corrupted or
stale chunks.

 Security: It supports authen ca on and access control to protect sensi ve transac on and
user data.